×

Representations of language families by homomorphic equality operations and generalized equality sets. (English) Zbl 0638.68069

For any word w over an alphabet \(\Sigma\), let w 1 be w and w R the mirror image of w; if \(h_ 1,..,h_ n\) are monoid homomorphisms defined on \(\Sigma\) * and if \(\rho\) maps \(\{\) 1,...,n\(\}\) into \(\{\) 1,R\(\}\), then \(<h_ 1,...,h_ n>_{\rho}(w)=h_ 1(w)^{\rho (1)}\) when \(h_ 1(w)^{\rho (1)}=...=h_ n(w)^{\rho (n)}\), otherwise \(<h_ 1,...,h_ n>_{\rho}(w)\) is undefined. Such partial functions \(<h_ 1,...,h_ n>_{\rho}\) and their inverses \(<h_ 1,...,h_ n>^{- 1}_{\rho}\) are called homomorphic equalities and inverse homomorphic equalities, respectively; the domains of homomorphic equalities are called generalized equality sets.
Extensively and meticulously the author shows how these notions can be brought to bear in formal language theory, the main section headings being: Generalized equality sets and representations of the regular sets, Trios over generalized equality sets, Homomorphic representations of the recursively enumerable sets, Homomorphic and inverse homomorphic equality operations, Preset machines and equality operations. One conspicuous result is the generation of the recursively enumerable sets from a one- element set by applying an inverse homomorphism, a homomorphic equality of two nonerasing homomorphisms, and one more homomorphism.
Reviewer: M.Armbrust

MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
03D10 Turing machines and related notions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Baker, B. S.; Book, R. V., Reversal bounded multi-pushdown machines, J. Comput. System Sci., 8, 315-332 (1974) · Zbl 0309.68043
[2] Berstel, J., Transductions and Context-Free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[3] Book, R. V., Simple representations of certain classes of languages, J. Assoc. Comput. Mach., 25, 23-31 (1978) · Zbl 0364.68073
[4] Book, R. V.; Brandenburg, F. J., Equality sets and complexity classes, SIAM J. Comput., 9, 729-743 (1980) · Zbl 0446.68040
[5] Book, R. V.; Greibach, S. A., Quasi-realtime languages, Math. Systems Theory, 4, 97-111 (1970) · Zbl 0188.33102
[6] Book, R. V.; Greibach, S. A., The independence of certain operations on semi-AFLs, RAIRO Theoret. Comput. Sci., 12, 369-385 (1978) · Zbl 0388.68068
[7] Book, R. V.; Greibach, S. A.; Wrathall, C., Comparisons and reset machines, (Proc. 5th Internat. Coll. on Automata, Languages and Programming. Proc. 5th Internat. Coll. on Automata, Languages and Programming, Udine 1978. Proc. 5th Internat. Coll. on Automata, Languages and Programming. Proc. 5th Internat. Coll. on Automata, Languages and Programming, Udine 1978, Lecture Notes in Computer Science, 62 (1978), Springer: Springer Berlin), 113-124 · Zbl 0388.03017
[8] Book, R. V.; Greibach, S. A.; Wrathall, C., Reset machines, J. Comput. System Sci., 19, 256-276 (1979) · Zbl 0427.03029
[9] Book, R. V.; Nivat, M., Linear languages and the intersection closures of classes of languages, SIAM J. Comput., 7, 167-177 (1978) · Zbl 0376.68049
[10] Book, R. V.; Nivat, M.; Paterson, M., Reversal-bounded acceptors and intersections of linear languages, SIAM J. Comput., 3, 283-295 (1974) · Zbl 0292.68023
[11] Book, R. V.; Wrathall, C., On languages specified by relative acceptance, Theoret. Comput. Sci., 7, 185-195 (1978) · Zbl 0385.68061
[12] Brandenburg, F. J., Multiple equality sets and Post machines, J. Comput. System Sci., 21, 292-316 (1980) · Zbl 0452.68086
[13] Brandenburg, F. J., Three write heads are as good as \(k\), Math. Systems Theory, 14, 1-13 (1980) · Zbl 0437.68029
[14] Brandenburg, F. J., Unary multiple equality sets: the language of rational matrices, Inform. and Control, 50, 199-227 (1981) · Zbl 0493.68085
[15] Brandenburg, F. J., Analogies of PAL and COPY, (Proc. Fundamentals of Computation Theory. Proc. Fundamentals of Computation Theory, Szeged 1981. Proc. Fundamentals of Computation Theory. Proc. Fundamentals of Computation Theory, Szeged 1981, Lecture Notes in Computer Science, 117 (1981), Springer: Springer Berlin), 61-70 · Zbl 0462.68058
[16] Brandenburg, F. J., Homomorphic equality operations on languages, (Habilitationsschrift (1981), Universität Bonn)
[17] Brandenburg, F. J., Extended Chomsky Schützenberger Theorems, (Proc. 9th Internat. Coll. on Automata, Languages and Programming. Proc. 9th Internat. Coll. on Automata, Languages and Programming, Aarhus 1982. Proc. 9th Internat. Coll. on Automata, Languages and Programming. Proc. 9th Internat. Coll. on Automata, Languages and Programming, Aarhus 1982, Lecture Notes in Computer Science, 140 (1982), Springer: Springer Berlin), 83-93
[18] Brandenburg, F. J., A truely morphic characterization of recursively enumerable sets, (Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 205-213 · Zbl 0551.68061
[19] Culik, K., A purely homomorphic characterization of recursively enumerable sets, J. Assoc. Comput. Mach., 26, 345-350 (1979) · Zbl 0395.68076
[20] Culik, K.; Diamond, N. D., A homomorphic characterization of time and space complexity classes of languages, Internat. J. Comput. Math., 8, 207-222 (1980) · Zbl 0444.68035
[21] Culik, K.; Fich, F.; Salomaa, A., A homomorphic characterization of regular languages, Discrete Appl. Math., 4, 149-152 (1982) · Zbl 0481.68069
[22] Culik, K.; Fris, I., The decidability of the equivalence problem for D0L systems, Inform. and Control, 35, 20-39 (1977) · Zbl 0365.68074
[23] Culik, K.; Harju, T., The \(ω\)-sequence equivalence problem for D0L systems is decidable, Proc. 13th Ann. ACM Symp. on Theory of Computing, 1-6 (1981)
[24] Culik, K.; Karhumäki, J., On the equality sets of homomorphisms on free monoids with two generators, RAIRO Theoret. Inform., 14, 349-369 (1980) · Zbl 0454.20048
[25] Culik, K.; Maurer, H. A., On simple representations of language families, RAIRO Theoret. Inform., 13, 241-250 (1979) · Zbl 0432.68052
[26] Dassow, J., Equality languages and language families, (Proc. Fundamentals of Computation Theory. Proc. Fundamentals of Computation Theory, 1981. Proc. Fundamentals of Computation Theory. Proc. Fundamentals of Computation Theory, 1981, Lecture Notes in Computer Science, 117 (1981), Springer: Springer Berlin), 100-109
[27] Ehrenfeucht, A.; Karhumäki, J.; Rozenberg, G., The (generalized) Post Correspondence Problem with lists of two words is decidable, Theoret. Comput. Sci., 21, 119-144 (1982) · Zbl 0493.68076
[28] Ehrenfeucht, A.; Rozenberg, G., Elementary homomorphisms and a solution to the D0L equivalence problem, Theoret. Comput. Sci., 7, 169-184 (1978) · Zbl 0407.68085
[29] Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K., A morphic representation of complements of recursively enumerables sets, J. Assoc. Comput. Mach., 28, 706-714 (1981) · Zbl 0491.68078
[30] Ehrenfeucht, A.; Rozenberg, G.; Ruohonen, K., A morphic representation of E0L languages and other ET0L languages, Discrete Appl. Math., 12, 115-122 (1985) · Zbl 0579.68046
[31] Engelfriet, J.; Rozenberg, G., Equality languages and fixed-point languages, Inform. and Control, 43, 20-49 (1979) · Zbl 0422.68034
[32] Engelfriet, J.; Rozenberg, G., Fixed-point languages, equality languages and representations of recursively enumerable languages, J. Assoc. Comput. Mach., 27, 499-518 (1980) · Zbl 0475.68047
[33] Ginsburg, S., Algebraic and Automata-theoretic Properties of Formal Languages (1975), North-Holland: North-Holland Amsterdam · Zbl 0325.68002
[34] Ginsburg, S.; Harrison, M. A., On the closure of AFL under reversal, Inform. and Control, 17, 395-409 (1970) · Zbl 0225.68042
[35] Ginsburg, S.; Spanier, E. H., AFL with the semilinear property, J. Comput. System Sci., 5, 365-396 (1971) · Zbl 0235.68029
[36] Greibach, S. A., Checking automata and one-way stack languages, J. Comput. System Sci., 3, 196-217 (1969) · Zbl 0174.02702
[37] Greibach, S. A., Erasing in context-free AFLs, Inform. and Control, 21, 436-465 (1972) · Zbl 0248.68036
[38] Greibach, S. A., Syntatic operators on full semi-AFLs, J. Comput. System Sci., 6, 30-76 (1972)
[39] Greibach, S. A., Control sets on context-free grammar forms, J. Comput. System Sci., 15, 35-98 (1977) · Zbl 0359.68093
[40] Greibach, S. A., One way finite visit automata, Theoret. Comput. Sci., 6, 175-221 (1978) · Zbl 0368.68059
[41] Greibach, S. A., Visits, crosses and reversals for nondeterministic offline machines, Inform. and Control, 36, 174-216 (1978) · Zbl 0375.02027
[42] Greibach, S. A., The strong independence of substitution and homomorphic replication, RAIRO Theoret. Inform., 12, 213-234 (1978) · Zbl 0387.68048
[43] Greibach, S. A., Hierarchy theorems for two-way finite state transducers, Acta Inform., 11, 89-101 (1978) · Zbl 0398.68038
[44] Greibach, S. A., One-counter languages and the chevron operation, RAIRO Theoret. Inform., 13, 189-194 (1979) · Zbl 0441.68081
[45] Greibach, S. A.; Ginsburg, S., Multitape AFA, J. Assoc. Comput. Mach., 19, 193-221 (1972) · Zbl 0241.68031
[46] Greibach, S. A.; Ginsburg, S.; Hopcroft, J. E., Pre-AFL, Memoirs AMS No. 83, 41-51 (1969)
[47] Harrison, M. A., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[48] Hull, R. B., Containment between intersection families of linear and reset languages, (Ph.D. Thesis (1979), University of California: University of California Berkeley)
[49] Ibarra, O. H., Reversal-bounded multicounter machines and their decision problems, J. Assoc. Comput. Mach., 25, 116-133 (1978) · Zbl 0365.68059
[50] Karhumäki, J.; Linna, M., A note on morphic characterization of languages, Discrete Appl. Math., 5, 243-246 (1983) · Zbl 0499.68031
[51] Karhumäki, J.; Simon, I., A note on elementary homomorphisms and the regularity of equality sets, Bulletin of the EATCS No. 9, 16-24 (1979)
[52] Karhumäki, J.; Wood, D., Inverse morphic equivalence on languages, Inform. Process. Lett., 19, 213-218 (1984) · Zbl 0571.68061
[53] Klingenstein, K., Structures of bounded languages in certain families of languages, (Ph.D. Thesis (1975), University of California: University of California Berkeley)
[54] Latteux, M., Cônes rationnels commutatifs, J. Comput. System Sci., 18, 307-333 (1979) · Zbl 0421.68074
[55] Latteux, M.; Leguy, J., On the composition of morphisms and inverse morphisms, (Lecture Notes in Computer Science, 154 (1983), Springer: Springer Berlin), 420-432 · Zbl 0523.68067
[56] Lyndon, R.; Schützenberger, M. P., The equations \(a^M = b^{N\) · Zbl 0106.02204
[57] Pansiot, J. J., A note on Post’s Correspondence Problem, Inform. Process. Lett., 12, 233 (1981) · Zbl 0485.03018
[58] Salomaa, A., Equality sets for homomorphisms of free monoids, Acta Cybernet., 4, 127-139 (1978) · Zbl 0407.68077
[59] Salomaa, A., Morphisms on free monoids and language theory, (Book, R. V., Formal Language Theory, Perspectives and Open Problems (1980), Academic Press: Academic Press New York), 141-166
[60] Salomaa, A., Jewels of Formal Language Theory (1981), Computer Science Press: Computer Science Press Rockville, MD · Zbl 0487.68063
[61] Turakainen, P., A homomorphic characterization of principal semi AFLs without using intersection with regular sets, Inform. Sci., 27, 141-149 (1982) · Zbl 0506.68063
[62] Wrathall, C., Rudimentary predicates and relative computation, SIAM J. Comput., 7, 194-209 (1978) · Zbl 0375.68030
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.