×

zbMATH — the first resource for mathematics

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
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Adjan, S.I., Burnside groups of odd exponent and irreducible systems of group identities, (), 19-38 · Zbl 0264.20027
[2] Adjan, S.I., The Burnside problem and identities in groups, (1979), Springer Berlin · Zbl 0417.20001
[3] Autebert, J.M.; Beauquier, J.; Boasson, L.; Latteux, M., Very small families of algebraic nonrational languages, (), 89-108
[4] 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 Stuttgart · Zbl 0424.68040
[6] 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 Paris · Zbl 0573.68037
[8] Blattner, M.; Latteux, M., Parikh-bounded languages, (), 316-323
[9] Boasson, L., Un critère de rationalité des langages algébriques, (), 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, (), 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., ()
[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 xr = x, (), 35-40 · Zbl 0046.01903
[21] Hall, M., Solution of the Burnside problem for exponent 6, (), 751-753 · Zbl 0079.03003
[22] Harrison, M., Introduction to formal language theory, (1978), 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)
[24] Herstein, I.N., Non commutative rings, () · 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. · Zbl 0617.68069
[28] Lallement, G., Semigroups and combinatorial applications, (1979), 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, (), 255-261 · Zbl 0496.68051
[31] M. Latteux and G. Rozenberg, Commutative one-counter languages are regular, J. Comput. System Sci., to appear. · 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 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, () · 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)
[41] Novikov, P.S.; Adjan, S.I.; Novikov, P.S.; Adjan, S.I.; Novikov, P.S.; Adjan, S.I.; Novikov, P.S.; Adjan, S.I.; Novikov, P.S.; Adjan, S.I.; Novikov, P.S.; Adjan, S.I., On infinite periodic groups, Izv. akad. nauk SSSR, ser. mat., Izv. akad. nauk SSSR, ser. mat., Izv. akad. nauk SSSR, ser. mat., Math. USSR izv., Math. USSR izv., Math. USSR izv., 2, 665-685, (1968), translated in · Zbl 0194.03301
[42] Ol’shanskii, A.U.; Ol’shanskii, A.U.; Ol’shanskii, A.U., The Novikov-adjan theorem, Mat. sb. (N.S.), Mat. sb. (N.S.), Math. reviews, 83, 160, 287-235, (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, (), 414-422
[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, (), 391-396
[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, () · Zbl 0444.68075
[52] Reutenauer, C., A new characterization of the regular languages, (), 177-183
[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 New York · Zbl 0461.16001
[55] Sakarovitch, J., Monoïdes syntactiques et langages algébriques, () · Zbl 0362.68108
[56] Salomaa, A.; Soittola, M., Automata theoretic aspects of formal power series, (1978), 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, (), 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, (), 279-295
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.