{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:42Z","timestamp":1759638162112},"publisher-location":"Berlin\/Heidelberg","reference-count":52,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"3540167838"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0016231","type":"book-chapter","created":{"date-parts":[[2005,11,13]],"date-time":"2005-11-13T05:39:17Z","timestamp":1131860357000},"page":"15-28","source":"Crossref","is-referenced-by-count":11,"title":["Recent results in the theory of rational sets"],"prefix":"10.1007","author":[{"given":"Jean","family":"Berstel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jacques","family":"Sakarovitch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"2_CR1","unstructured":"Aalbersberg IJ. J. and E. Welzl, Trace languages defined by regular string languages. To appear in RAIRO Inform. Th\u00e9or."},{"key":"2_CR2","unstructured":"Aalbersberg IJ. J. and G. Rozenberg, Theory of traces. Tech. Rep. 85-16, Univ. Leiden."},{"key":"2_CR3","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1016\/S0019-9958(65)90275-5","volume":"8","author":"V. Amar","year":"1965","unstructured":"Amar V. and G. Putzolu, Generalization of regular events. Inform. and Control 8 (1965), 56\u201363.","journal-title":"Inform. and Control"},{"key":"2_CR4","unstructured":"Anisimov A. V. and D. Knuth, Inhomogeneous sorting. Unpublished manuscript."},{"key":"2_CR5","first-page":"695","volume":"11","author":"A. V. Anisimov","year":"1975","unstructured":"Anisimov A. V. and F. D. Seifert, Zur algebraischen Charakteristik der durch kontextfreie Sprachen definierten Gruppen, E.I.K. 11, (1975), 695\u2013702.","journal-title":"E.I.K."},{"key":"2_CR6","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/0304-3975(79)90049-5","volume":"8","author":"A. Arnold","year":"1979","unstructured":"Arnold A. and M. Latteux, A new proof of two theorems about rational transductions. Theor. Comput. Sci. 8 (1979), 261\u2013263.","journal-title":"Theor. Comput. Sci."},{"key":"2_CR7","first-page":"1188","volume":"269","author":"M. Benois","year":"1969","unstructured":"Benois M., Parties rationnelles du groupe libre, C.R. Acad. Sci. Paris, Ser. A, 269 (1969), 1188\u20131190.","journal-title":"C.R. Acad. Sci. Paris, Ser. A"},{"key":"2_CR8","doi-asserted-by":"crossref","unstructured":"Berstel J., Transductions and Context-Free Languages, Teubner, 1979.","DOI":"10.1007\/978-3-663-09367-1"},{"key":"2_CR9","unstructured":"Bertoni A., Mauri G. and N. Sabadini, Unambiguous regular trace languages. In: Algebra, Combinatorics, and Logic in Computer Science (J. Demetrovics, G. Katona, and A. Salomaa, eds.), Colloquia Mathematica Soc. J. Boyai 42, North Holland (1985)."},{"key":"2_CR10","doi-asserted-by":"crossref","unstructured":"Cartier P. and D. Foata, Probl\u00e8mes combinatoires de commutations et r\u00e9arrangements. Lecture Notes in Math. 85, Springer, 1969.","DOI":"10.1007\/BFb0079468"},{"key":"2_CR11","first-page":"213","volume":"210","author":"C. Choffrut","year":"1986","unstructured":"Choffrut Ch. and M. P. Sch\u00fctzenberger, D\u00e9composition de fonctions rationnelles. In: Proc. 3rd Symp. Theor. Aspects Comput. Sci. (B. Monien, G. Vidal-Naquet eds.), Lect. Notes Comput. Sci. 210 (1986), 213\u2013226.","journal-title":"Proc. 3rd Symp. Theor. Aspects Comput. Sci."},{"key":"2_CR12","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1016\/0304-3975(77)90049-4","volume":"5","author":"C. Choffrut","year":"1977","unstructured":"Choffrut Ch., Une caract\u00e9risation des fonctions s\u00e9quentielles et des fonctions sous-s\u00e9quentielles en tant que relations rationnelles. Theor. Comput. Sci. 5 (1977), 325\u2013338.","journal-title":"Theor. Comput. Sci."},{"key":"2_CR13","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1051\/ita\/1985190100211","volume":"19","author":"R. Cori","year":"1985","unstructured":"Cori R. and D. Perrin, Automates et commutations partielles. RAIRO Inform. Th\u00e9or. 19 (1985), 21\u201332.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/0304-3975(85)90013-1","volume":"35","author":"R. Cori","year":"1985","unstructured":"Cori R. and Y. M\u00e9tivier, Recognizable subsets of some partially abelian monoids. Theor. Comput. Sci. 35 (1985), 179\u2013189.","journal-title":"Theor. Comput. Sci."},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0166-218X(82)90072-5","volume":"4","author":"K. \u010culik II","year":"1982","unstructured":"\u010culik II K., E. Fich and A. Salomaa, A homomorphic characterization of regular languages. Discrete Appl. Math. 4 (1982), 149\u2013152.","journal-title":"Discrete Appl. Math."},{"key":"2_CR16","unstructured":"Duboc Ch., On some equations in free partially commutative monoids. To appear in Theor. Comput. Sci."},{"key":"2_CR17","first-page":"344","volume":"13","author":"S. Eilenberg","year":"1969","unstructured":"Eilenberg S. and M. P. Sch\u00fctzenberger, Rational sets in commutative monoids. J. of Algebra 13 (1969), 344\u2013353.","journal-title":"J. of Algebra"},{"key":"2_CR18","unstructured":"Eilenberg S., Automata, Languages and Machines, Vol. A. Academic Press, 1974."},{"key":"2_CR19","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1147\/rd.91.0047","volume":"9","author":"C. Elgot","year":"1965","unstructured":"Elgot C. and G. Mezei, On relations defined by generalized finite automata. IBM J. of Res. Dev. 9 (1965), 47\u201365.","journal-title":"IBM J. of Res. Dev."},{"key":"2_CR20","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1016\/S0022-0000(68)80006-6","volume":"2","author":"P. Fischer","year":"1968","unstructured":"Fischer P. and A. Rosenberg, Multitape one-way nonwriting automata. J. Comput. and Syst. Sci. 2 (1968), 88\u2013101.","journal-title":"J. Comput. and Syst. Sci."},{"key":"2_CR21","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(85)90206-3","volume":"38","author":"M. P. Fl\u00e9","year":"1985","unstructured":"Fl\u00e9 M. P. and G. Roucairol, Maximal serializability of iterated transactions. Theor. Comput. Sci. 38 (1985), 1\u201316.","journal-title":"Theor. Comput. Sci."},{"key":"2_CR22","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1016\/0021-8693(71)90094-9","volume":"19","author":"M. Fliess","year":"1971","unstructured":"Fliess M., Deux applications de la repr\u00e9sentation matricielle d'une s\u00e9rie rationnelle non commutative. J. of Algebra 19 (1971), 344\u2013353.","journal-title":"J. of Algebra"},{"key":"2_CR23","first-page":"197","volume":"53","author":"M. Fliess","year":"1974","unstructured":"Fliess M., Matrices de Hankel. J. Math. pures et appl. 53 (1974), 197\u2013224.","journal-title":"J. Math. pures et appl."},{"key":"2_CR24","unstructured":"Frougny Ch., J. Sakarovitch and P. Schupp, Finiteness conditions on subgroups and formal language theory. Tech. Rep. Litp 85-66."},{"key":"2_CR25","unstructured":"Frougny Ch., Fibonacci numeration systems and rational functions. This volume."},{"key":"2_CR26","first-page":"333","volume":"113","author":"S. Ginsburg","year":"1964","unstructured":"Ginsburg S. and E. H. Spanier, Bounded ALGOL-like languages. Trans. Am. Math. Soc. 113 (1964), 333\u2013368.","journal-title":"Trans. Am. Math. Soc."},{"key":"2_CR27","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1966.16.285","volume":"16","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg S. and E. H. Spanier, Semigroups, Presburger formulas, and languages. Pacif. J. Math. 16 (1966), 285\u2013296.","journal-title":"Pacif. J. Math."},{"key":"2_CR28","doi-asserted-by":"crossref","first-page":"381","DOI":"10.4153\/CJM-1966-040-3","volume":"18","author":"S. Ginsburg","year":"1966","unstructured":"Ginsburg S. and G. Rose, A characterization of machine mappings. Can. J. of Math. 18 (1966), 381\u2013388.","journal-title":"Can. J. of Math."},{"key":"2_CR29","doi-asserted-by":"crossref","unstructured":"Gohon Ph., An algorithm to decide whether a rational subset of N k is recognizable. Theor. Comput. Sci. 41 (1986).","DOI":"10.1016\/0304-3975(85)90059-3"},{"key":"2_CR30","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1007\/BFb0015755","volume":"194","author":"J. Johnson","year":"1985","unstructured":"Johnson J., Do rational equivalence relations have regular cross-section? Proc. 12th Intern. Conf. Automata, Languages and Programming, Lect. Notes Comput. Sci. 194 (1985), 300\u2013309.","journal-title":"Lect. Notes Comput. Sci."},{"key":"2_CR31","unstructured":"Johnson J., A Rational Equivalence Relation Hierarchiy. Tech. Rep. University of Waterloo, November 1985."},{"key":"2_CR32","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0166-218X(83)90045-8","volume":"5","author":"J. Karhumaki","year":"1983","unstructured":"Karhumaki J. and M. Linna, A note on morphic characterization of languages. Discrete Appl. Math. 5 (1983), 243\u2013246.","journal-title":"Discrete Appl. Math."},{"key":"2_CR33","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0019-9958(69)90651-2","volume":"15","author":"K. Kobayashi","year":"1969","unstructured":"Kobayashi K., Classification of formal languages by functional binary transductions, nform. and Control 15 (1969), 95\u2013109.","journal-title":"nform. and Control"},{"key":"2_CR34","unstructured":"Latteux M., and P. Turakainen, A new normal form for compositions of morphisms and inverse morphisms. Tech. Rep. IT-66-84, Universit\u00e9 Lille I, July 1984."},{"key":"2_CR35","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1007\/BFb0036926","volume":"154","author":"M. Latteux","year":"1983","unstructured":"Latteux M. and J. Leguy, On the composition of morphisms and inverse morphisms. Lect. Notes Comput. Sci. 154 (1983), 420\u2013432.","journal-title":"Lect. Notes Comput. Sci."},{"key":"2_CR36","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1051\/ita\/1981150201411","volume":"15","author":"J. Leguy","year":"1981","unstructured":"Leguy J., Transductions rationnelles d\u00e9croissantes. RAIRO Inform. Th\u00e9or. 15 (1981), 141\u2013148.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"2_CR37","unstructured":"Lothaire M., Combinatorics on Words. Encyclop. of Math. 17, Addison-Wesley, 1983."},{"key":"2_CR38","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1016\/0021-8693(69)90015-5","volume":"12","author":"J. D. McKnight Jr.","year":"1968","unstructured":"McKnight Jr. J. D. and A. J. Storey, Equidivisible semigroups. J. of Algebra 12 (1968), 24\u201348.","journal-title":"J. of Algebra"},{"key":"2_CR39","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/BFb0030293","volume":"176","author":"A. Mazurkiewicz","year":"1984","unstructured":"Mazurkiewicz A., Traces, histories, and graphs: instances of a process monoid. Proc. of Math. Foundations Comput. Sci. 84, Lect. Notes Comput. Sci. 176, (1984), 115\u2013133.","journal-title":"Lect. Notes Comput. Sci."},{"key":"2_CR40","unstructured":"M\u00e9tivier Y., Une condition suffisante de reconaissabilit\u00e9 dans un mono\u00efde partiellement commutatif. To appear in RAIRO Inform. Th\u00e9or."},{"key":"2_CR41","unstructured":"Ochmanski E., Regular behaviour of concurrent systems. Bull. European Assoc. Theor. Comput. Sci., October 1985."},{"key":"2_CR42","unstructured":"Pelletier M. and J. Sakarovitch, Easy Multiplications II. Extensions of rational monoids. In preparation."},{"key":"2_CR43","unstructured":"Perrin D., Words over a partially commutative alphabet. Tech. Rep. Litp 84-59."},{"key":"2_CR44","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1051\/ita\/1985190302811","volume":"19","author":"C. Reutenauer","year":"1985","unstructured":"Reutenauer Ch., Sur les semi-groupes v\u00e9rifiant le th\u00e9or\u00e8me de Kleene. RAIRO Inform. Th\u00e9or. 19 (1985), 281\u2013291.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"2_CR45","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1051\/ita\/1983170100231","volume":"17","author":"J. Sakarovitch","year":"1983","unstructured":"Sakarovitch J., Deux remarques sur un th\u00e9or\u00e8me de S. Eilenberg. RAIRO Inform. Th\u00e9or. 17 (1983), 23\u201348.","journal-title":"RAIRO Inform. Th\u00e9or."},{"key":"2_CR46","unstructured":"Sakarovitch J., On regular trace languages. To appear."},{"key":"2_CR47","unstructured":"Sakarovitch J., Easy Multiplications. I. The realm of Kleene's Theorem. To appear in Inform. and Control."},{"key":"2_CR48","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/0304-3975(77)90055-X","volume":"4","author":"M. P. Sch\u00fctzenberger","year":"1977","unstructured":"Sch\u00fctzenberger M. P., Sur une variante des fonctions s\u00e9quentielles. Theor. Comput. Sci. 4 (1977), 47\u201357.","journal-title":"Theor. Comput. Sci."},{"key":"2_CR49","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1016\/0304-3975(76)90026-8","volume":"3","author":"M. P. Sch\u00fctzenberger","year":"1976","unstructured":"Sch\u00fctzenberger M. P., Sur les relations rationnelles entre monol'des libres. Theor. Comput. Sci. 3 (1976), 243\u2013259.","journal-title":"Theor. Comput. Sci."},{"key":"2_CR50","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/3-540-07407-4_22","volume":"33","author":"M. P. Sch\u00fctzenberger","year":"1975","unstructured":"Sch\u00fctzenberger M. P., Sur les relations fonctionnelles. In: Automata Theory and Formal Languages, 2nd GI Conference (H. Brakhage ed.), Lect. Notes Comput. Sci. 33 (1975), 209\u2013213.","journal-title":"Lect. Notes Comput. Sci."},{"key":"2_CR51","unstructured":"S\u00e9nizergues G., Solution of a conjecture about rational subsets of the free group. Tech. Rep. Litp 86-3."},{"key":"2_CR52","unstructured":"Ullman J., Principles of Database Systems, Computer Science Press, 1980."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1986"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BFb0016231.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,12,9]],"date-time":"2020-12-09T21:35:29Z","timestamp":1607549729000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0016231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["3540167838"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/bfb0016231","relation":{},"subject":[]}}