×

Rational languages and the Burnside problem. (English) Zbl 0597.68057

This survey paper is mainly concerned with the following problem: give properties which characterize regularity of formal languages. Since regularity of a language is equivalent to the finiteness of its syntactic monoid, this problem is related to the Burnside problem for monoids: under the assumption that each cyclic submonoid of the monoid M is finite (i.e. M is periodic), when M is finite ? Periodicity is itself related to the classical language-theoretic property of pumping. We consider also bounded and commutative languages in this paper, which ends with similar questions on formal power series: rationality questions, boundedness of the support.

MSC:

68Q45 Formal languages and automata
20M35 Semigroups in automata theory, linguistics, etc.
16W60 Valuations, completions, formal power series and related constructions (associative rings and algebras)
68-02 Research exposition (monographs, survey articles) pertaining to computer science
20-02 Research exposition (monographs, survey articles) pertaining to group theory

Citations:

Zbl 0578.68060
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adjan, S. I., Burnside groups of odd exponent and irreducible systems of group identities, (Boone, W. W.; Cannonito, F. B.; Lyndon, R. C., Word Problems (1973), North-Holland: North-Holland Amsterdam), 19-38 · Zbl 0264.20027
[2] Adjan, S. I., The Burnside Problem and Identities in Groups (1979), Springer: Springer Berlin · Zbl 0417.20001
[3] Autebert, J. M.; Beauquier, J.; Boasson, L.; Latteux, M., Very small families of algebraic nonrational languages, (Book, R., Formal Language Theory, Perspectives and Open Problems (1980), Academic Press: Academic Press New York), 89-108
[4] J. Beauquier, M. Blattner and M. Latteux, On commutative context-free languages, to appear.; J. Beauquier, M. Blattner and M. Latteux, On commutative context-free languages, to appear. · Zbl 0627.68063
[5] Berstel, J., Transductions and Context-free Languages (1979), Teubner: Teubner Stuttgart · Zbl 0424.68040
[6] J. Berstel, Each iterated morphism yields a co-CFL, to appear.; J. Berstel, Each iterated morphism yields a co-CFL, to appear.
[7] Berstel, J.; Reutenauer, C., Les Séries Rationnelles et Leurs Langages (1984), Masson: Masson Paris · Zbl 0573.68037
[8] Blattner, M.; Latteux, M., Parikh-bounded languages, (Lecture Notes in Computer Science, 115 (1981), Springer: Springer Berlin), 316-323 · Zbl 0462.68057
[9] Boasson, L., Un critère de rationalité des langages algébriques, (Nivat, M., Proc. 1st Internat. Coll. on Automata, Languages and Programming (1973), North-Holland: North-Holland Amsterdam), 359-365 · Zbl 0399.68072
[10] Boasson, L.; Restivo, A., Une caractérisation des langages algébriques bornés, RAIRO Inform., 11, 203-205 (1977) · Zbl 0371.68024
[11] Britton, J. L., The existence of infinite Burnside groups, (Boone, W. W.; Cannonito, F. B.; Lyndon, R. C., Word Problems (1973), North-Holland: North-Holland Amsterdam), 67-348 · Zbl 0427.20032
[12] Brzozowski, J. A.; Culik, K.; Gabrielan, A., Classification of non-counting events, J. Comput. System Sci., 5, 41-53 (1971) · Zbl 0241.94050
[13] Burnside, W., On an unsettled question in the theory of discontinuous groups, Quart. J. Pure Appl. Math., 33, 230-238 (1902) · JFM 33.0149.01
[14] Choffrut, C., Sur les transductions reconnaissables, RAIRO Inform., 12, 203-218 (1978) · Zbl 0423.20053
[15] Ehrenfeucht, A.; Haussler, D.; Rozenberg, G., On regularity of context-free languages, Theoret. Comput. Sci., 27, 311-332 (1983) · Zbl 0553.68044
[16] Ehrenfeucht, A.; Parikh, R.; Rozenberg, G., Pumping lemmas for regular sets, SIAM J. Comput., 10, 536-541 (1981) · Zbl 0461.68081
[17] Eilenberg, S., (Automata, Languages and Machines, Vols. A, B (1974), Academic Press: Academic Press New York) · Zbl 0317.94045
[18] Engelfriet, J.; Rozenberg, G., A translational theorem for the class of E0L languages, Inform. and Control, 50, 175-183 (1981) · Zbl 0507.68052
[19] Goldstine, J., Substitution and bounded languages, J. Comput. System Sci., 6, 9-29 (1972) · Zbl 0232.68030
[20] Green, J. A.; Rees, D., On semigroups in which \(x^r = x\), (Proc. Cambridge Philos. Soc., 48 (1952)), 35-40 · Zbl 0046.01903
[21] Hall, M., Solution of the Burnside problem for exponent 6, (Proc. Nat. Acad. Sci. USA, 43 (1957)), 751-753 · Zbl 0079.03003
[22] Harrison, M., Introduction to Formal Language Theory (1978), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0411.68058
[23] Hashigushi, K., A decision procedure for the order of regular events, Theoret. Comput. Sci., 8, 69-72 (1979) · Zbl 0419.68088
[24] Herstein, I. N., Non commutative rings, (Carus Mathematical Monographs (1968), Wiley: Wiley New York) · Zbl 0874.16001
[25] Jacob, G., La finiture des représentations linéaires des semi-groupes est décidable, J. Algebra, 52, 437-459 (1978) · Zbl 0374.20074
[26] Kaplansky, I., Fields and Rings (1965), University of Chicago Press
[27] J. Kortelainen, Every commutative quasi-rational language is regular, to appear.; J. Kortelainen, Every commutative quasi-rational language is regular, to appear. · Zbl 0617.68069
[28] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[29] Latteux, M., Cônes rationnels commutatifs, J. Comput. System Sci., 18, 307-333 (1979) · Zbl 0421.68074
[30] Latteux, M.; Leguy, J., Une propriéte de la famille GRE, (Fundamentals of Computer Science (1979), Akademie Verlag: Akademie Verlag Berlin), 255-261 · Zbl 0496.68051
[31] M. Latteux and G. Rozenberg, Commutative one-counter languages are regular, J. Comput. System Sci.; M. Latteux and G. Rozenberg, Commutative one-counter languages are regular, J. Comput. System Sci. · Zbl 0549.68074
[32] Latteux, M.; Thierrin, G., On bounded context-free languages, Elek. Inf. Kyb., 20, 3-8 (1984) · Zbl 0552.68062
[33] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[34] de Luca, A.; Restivo, A., A finiteness condition for finitely generated semigroups, Semigroup Forum, 28, 123-134 (1984) · Zbl 0529.20044
[35] Main, M. G.; Bucher, W.; Haussler, D., Applications of an infinite co-CFL, (Proc. 12th ICALP (1985)) · Zbl 0602.68060
[36] Mandel, A.; Simon, I., On finite semigroups of matrices, Theoret. Comput. Sci., 5, 101-111 (1977) · Zbl 0368.20049
[37] Maurer, H. A.; Nivat, M., Rational bijection of rational sets, Acta Inform., 13, 365-378 (1980) · Zbl 0432.68051
[38] McNaughton, R.; Zalcstein, I., The Burnside problem for semigroups, J. Algebra, 34, 292-299 (1975) · Zbl 0302.20054
[39] Morse, M.; Hedlund, G., Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J., 11, 1-7 (1944) · Zbl 0063.04115
[40] Novikov, P. S., Dokl. Akad. Nauk SSSR, 127, 749-752 (1959), (in Russian) · Zbl 0119.02202
[41] Novikov, P. S.; Adjan, S. I., Math. USSR Izv., 2, 665-685 (1968) · Zbl 0194.03301
[42] Ol’shanskii, A. U., Math. Reviews, 83 (1983), see also:
[43] Pólya, G., Arithmetische Eigenschaften der Reihenentwicklungen rationaler Funktionen, J. Reine Angew. Math., 151 (1921) · JFM 47.0276.02
[44] Restivo, A., Mots sans répétitions et langages rationnels bornés, RAIRO Inform. Théor., 11, 197-202 (1977) · Zbl 0371.68023
[45] Restivo, A.; Reutenauer, C., Some applications of a theorem of Shirshov to language theory, Inform. and Control, 57, 205-213 (1983) · Zbl 0569.68059
[46] Restivo, A.; Reutenauer, C., Cancellation pumping and permutation in formal languages, (11th ICALP. 11th ICALP, Lecture Notes in Computer Science, 172 (1984), Springer: Springer Berlin), 414-422 · Zbl 0578.68060
[47] Restivo, A.; Reutenauer, C., On the Burnside problem for semigroups, J. Algebra, 89, 102-104 (1984) · Zbl 0545.20051
[48] Restivo, A.; Reutenauer, C., On cancellation properties of languages which are support of rational power series, J. Comput. System. Sci., 29, 153-159 (1984) · Zbl 0578.68061
[49] Reutenauer, C., Sur les séries de Polya en variable noncommutatives, (Fundamentals of Computation Theory, 2 (1979), Akademie Verlag: Akademie Verlag Berlin), 391-396 · Zbl 0421.68079
[50] Reutenauer, C., Séries formelles et algèbras syntactiques, J. Algebra, 66, 448-483 (1980) · Zbl 0444.68075
[51] Reutenauer, C., Séries rationnelles et algèbres syntactiques, (Thèse de Doctorat d’Etat (1980), Université Paris 6) · Zbl 0444.68075
[52] Reutenauer, C., A new characterization of the regular languages, (Lecture Notes in Computer Science, 115 (1981), Springer: Springer Berlin), 177-183 · Zbl 0467.68063
[53] Reutenauer, C., Sur les éléments inversibles de l’algèbre de Hadamard des séries rationnelles, Bull. Soc. Math. France, 110, 225-232 (1982) · Zbl 0517.13010
[54] Rowen, L. H., Polynomial Identities in Ring Theory (1980), Academic Press: Academic Press New York · Zbl 0461.16001
[55] Sakarovitch, J., Monoïdes syntactiques et langages algébriques, (Thèse 3ème cycle (1976), Université Paris 7) · Zbl 0362.68108
[56] Salomaa, A.; Soittola, M., Automata Theoretic Aspects of Formal Power Series (1978), Springer: Springer Berlin · Zbl 0377.68039
[57] Schur, I., Über Gruppen periodischer Substitutionen, Sitzungsber. Preuss. Akad. Wiss. Math.-Natur. Kl., 619-627 (1911) · JFM 42.0155.01
[58] Schützenberger, M. P., On the definition of a family of automata, Inform. and Control, 4, 245-270 (1961) · Zbl 0104.00702
[59] Schützenberger, M. P., Finite counting automata, Inform. Control, 5, 91-107 (1962) · Zbl 0118.12506
[60] Shirshov, A. I., On rings with identity relations, Mat. Sb., 43, 85, 277-283 (1957), (in Russian) · Zbl 0078.02402
[61] Simon, I., Limited subsets of a free monoid, (Proc. 19th Ann. Symp. on Foundations of Computer Science (1978)), 143-150
[62] Simon, I., Conditions de finitude pour des semi-groupes, C.R. Acad. Sci. Paris Sér. A, 290, 1081-1082 (1980) · Zbl 0437.20044
[63] Sontag, E., On some questions of rationality and decidability, J. Comput. System Sci., 11, 375-385 (1975) · Zbl 0357.68064
[64] Straubing, H., The Burnside problem for semigroups of matrices, (Cummings, L. J., Combinatorics on Words, Progress and Perspectives (1983), Academic Press: Academic Press New York), 279-295 · Zbl 0564.20045
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.