{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:02Z","timestamp":1753889702490,"version":"3.41.2"},"reference-count":29,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2006,7,19]],"date-time":"2006-07-19T00:00:00Z","timestamp":1153267200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/assumed-1991-2003"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We investigate families of infinite automata for context-sensitive languages. An infinite automaton is an infinite labeled graph with two sets of initial and final vertices. Its language is the set of all words labelling a path from an initial vertex to a final vertex. In 2001, Morvan and Stirling proved that rational graphs accept the context-sensitive languages between rational sets of initial and final vertices. This result was later extended to sub-families of rational graphs defined by more restricted classes of transducers. languages.&lt;br&gt;&lt;br&gt; Our contribution is to provide syntactical and self-contained proofs of the above results, when earlier constructions relied on a non-trivial normal form of context-sensitive grammars defined by Penttonen in the 1970's. These new proof techniques enable us to summarize and refine these results by considering several sub-families defined by restrictions on the type of transducers, the degree of the graph or the size of the set of initial vertices.<\/jats:p>","DOI":"10.2168\/lmcs-2(2:6)2006","type":"journal-article","created":{"date-parts":[[2006,11,23]],"date-time":"2006-11-23T09:27:32Z","timestamp":1164274052000},"source":"Crossref","is-referenced-by-count":8,"title":["Context-Sensitive Languages, Rational Graphs and Determinism"],"prefix":"10.46298","volume":"Volume 2, Issue 2","author":[{"given":"Arnaud","family":"Carayol","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Antoine","family":"Meyer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2006,7,19]]},"reference":[{"key":"10.2168\/LMCS-2(2:6)2006_Berstel79","doi-asserted-by":"crossref","unstructured":"J. Berstel.Transductions and Context-Free Languages. Teubner Verlag, 1979.","DOI":"10.1007\/978-3-663-09367-1"},{"key":"10.2168\/LMCS-2(2:6)2006_Blumensath00","doi-asserted-by":"crossref","unstructured":"A. Blumensath and E. Gr\u00e4del. Automatic structures. InProceedings of the 15th IEEE Symposium on Logic in Computer Science (LICS 2000), pages 51-62. IEEE, 2000.","DOI":"10.1109\/LICS.2000.855755"},{"key":"10.2168\/LMCS-2(2:6)2006_Caucal96","doi-asserted-by":"crossref","unstructured":"D. Caucal. On infinite transition graphs having a decidable monadic theory. InICALP, pages 194-205, 1996.","DOI":"10.1007\/3-540-61440-0_128"},{"key":"10.2168\/LMCS-2(2:6)2006_Caucal03pr","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0304-3975(01)00089-5","volume":"290","author":"D. Caucal","year":"2003","journal-title":"Theoretical Computer Science"},{"key":"10.2168\/LMCS-2(2:6)2006_Caucal03tm","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0304-3975(02)00655-2","volume":"296","author":"D. Caucal","year":"2003","journal-title":"Theoretical Computer Science"},{"key":"10.2168\/LMCS-2(2:6)2006_Chomsky59","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","volume":"2","author":"N. Chomsky","year":"1959","journal-title":"Information and Control"},{"key":"10.2168\/LMCS-2(2:6)2006_Caucal02","doi-asserted-by":"crossref","unstructured":"D. Caucal and T. Knapik. A Chomsky-like hierarchy of infinite graphs. InMathematical Foundations of Computer Science 2002, 27th International Symposium (MFCS 2002), volume 2420 ofLecture Notes in Computer Science, pages 177-187, 2002.","DOI":"10.1007\/3-540-45687-2_14"},{"key":"10.2168\/LMCS-2(2:6)2006_CarayolM05","doi-asserted-by":"crossref","unstructured":"A. Carayol and A. Meyer. Linearly bounded infinite graphs. InMathematical Foundations of Computer Science 2005, 30th International Symposium (MFCS 2005), volume 3618 ofLecture Notes in Computer Science, pages 180-191. Springer Verlag, 2005. Long version to appear in \\sl Acta Informatica.","DOI":"10.1007\/11549345_17"},{"key":"10.2168\/LMCS-2(2:6)2006_Elgot65","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1147\/rd.91.0047","volume":"9","author":"C. Elgot and J. Mezei","year":"1965","journal-title":"IBM Journal of Research and Development"},{"key":"10.2168\/LMCS-2(2:6)2006_Fortnow00","first-page":"102","volume":"71","author":"L. Fortnow","year":"2000","journal-title":"{\\em Bulletin of the European Association for Theoretical Computer Science}, 71:102-112, 2000"},{"key":"10.2168\/LMCS-2(2:6)2006_Giammarresi96","doi-asserted-by":"crossref","unstructured":"D. Giammarresi and A. Restivo.Handbook of Formal Languages, volume 3, chapter Two-dimensional languages. Springer Verlag, 1996.","DOI":"10.1007\/978-3-642-59126-6_4"},{"key":"10.2168\/LMCS-2(2:6)2006_Hopcroft79","unstructured":"J. Hopcroft and J. Ullman.Introduction to Automata Theory, Languages and Computation. Addison-Wesley, 1979."},{"key":"10.2168\/LMCS-2(2:6)2006_Kobayashi69","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/S0019-9958(69)90651-2","volume":"15","author":"K. Kobayashi","year":"1969","journal-title":"Information and Control"},{"key":"10.2168\/LMCS-2(2:6)2006_Knapik99","doi-asserted-by":"crossref","unstructured":"T. Knapik and \u00c9. Payet. Synchronized product of linear bounded machines. InFundamentals of Computation Theory, 12th International Symposium (FCT 1999), volume 1684 ofLecture Notes in Computer Science, pages 362-373, 1999.","DOI":"10.1007\/3-540-48321-7_30"},{"issue":"2","key":"10.2168\/LMCS-2(2:6)2006_Kuroda64","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","volume":"7","author":"S. Kuroda","year":"1964","journal-title":"Information and Control"},{"issue":"2","key":"10.2168\/LMCS-2(2:6)2006_Latteux97","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1006\/inco.1997.2659","volume":"138","author":"M. Latteux and D. Simplot","year":"1997","journal-title":"Information and Computation"},{"issue":"1-2","key":"10.2168\/LMCS-2(2:6)2006_LS97","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1016\/S0304-3975(96)00283-6","volume":"178","author":"M. Latteux and D. Simplot","year":"1997","journal-title":"Theoretical Computer Science"},{"key":"10.2168\/LMCS-2(2:6)2006_Morvan00","doi-asserted-by":"crossref","unstructured":"C. Morvan. On rational graphs. InFoundations of Software Science and Computation Structures, Third International Conference (FoSSaCS 2000), volume 1784 ofLecture Notes in Computer Science, pages 252-266, 2000.","DOI":"10.1007\/3-540-46432-8_17"},{"key":"10.2168\/LMCS-2(2:6)2006_Morvan01b","unstructured":"C. Morvan.Les graphes rationnels. PhD thesis, IFSIC, Universit\u00e9 de Rennes 1, 2001."},{"key":"10.2168\/LMCS-2(2:6)2006_Morvan04","doi-asserted-by":"crossref","unstructured":"C. Morvan and C. Rispal. Families of automata characterizing context-sensitive languages.to appear in Acta Informatica, 2004.","DOI":"10.1007\/s00236-004-0160-0"},{"key":"10.2168\/LMCS-2(2:6)2006_Morvan01a","doi-asserted-by":"crossref","unstructured":"C. Morvan and C. Stirling. Rational graphs trace context-sensitive languages. InMathematical Foundations of Computer Science 2001, 26th International Symposium (MFCS 2001), volume 2136 ofLecture Notes in Computer Science, pages 548-559, 2001.","DOI":"10.1007\/3-540-44683-4_48"},{"key":"10.2168\/LMCS-2(2:6)2006_Payet00","doi-asserted-by":"crossref","unstructured":"E. Payet.Thue Specifications, Infinite Graphs and Synchronized Product. PhD thesis, Universit\u00e9 de la R\u00e9union, 2000.","DOI":"10.3233\/FUN-2000-44303"},{"issue":"4","key":"10.2168\/LMCS-2(2:6)2006_Penttonen74","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0019-9958(74)91049-3","volume":"25","author":"M. Penttonen","year":"1974","journal-title":"Information and Control"},{"key":"10.2168\/LMCS-2(2:6)2006_Prieur00","unstructured":"Ch. Prieur.Fonctions rationnelles de mots infinis et continuit\u00e9. PhD thesis, Universit\u00e9 de Paris 7, 2000."},{"key":"10.2168\/LMCS-2(2:6)2006_Rispal02","doi-asserted-by":"crossref","unstructured":"C. Rispal. The synchronized graphs trace the context-sensitive languages. In4th International Workshop on Verification of Infinite-State Systems (Infinity 2002), volume 68 ofElectronic Notes in Theoretical Computer Science, 2002.","DOI":"10.1016\/S1571-0661(04)80533-4"},{"key":"10.2168\/LMCS-2(2:6)2006_Sakarovitch03","unstructured":"J. Sakarovitch.\u00c9l\u00e9ments de th\u00e9orie des automates. \u00c9ditions Vuibert, 2003."},{"key":"10.2168\/LMCS-2(2:6)2006_Thomas01","doi-asserted-by":"crossref","unstructured":"W. Thomas. A short introduction to infinite automata. InDevelopments in Language Theory, 5th International Conference (DLT 2001), volume 2295 ofLecture Notes in Computer Science, pages 130-144, 2001.","DOI":"10.1007\/3-540-46011-X_10"},{"key":"10.2168\/LMCS-2(2:6)2006_Melkebeek04","doi-asserted-by":"crossref","unstructured":"D. van Melkebeek. Time-space lower bounds for NP-complete problems.Current Trends in Theoretical Computer Science, pages 265-291, 2004.","DOI":"10.1142\/9789812562494_0015"},{"issue":"5","key":"10.2168\/LMCS-2(2:6)2006_Weber96","first-page":"379","volume":"30","author":"A. Weber","year":"1996","journal-title":"Informatique Th\u00e9orique et Applications 30(5):379-413, 1996"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/2254\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/2254\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,12]],"date-time":"2025-01-12T02:18:19Z","timestamp":1736648299000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/2254"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,7,19]]},"references-count":29,"URL":"https:\/\/doi.org\/10.2168\/lmcs-2(2:6)2006","relation":{"is-same-as":[{"id-type":"arxiv","id":"cs\/0606053","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.cs\/0606053","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2006,7,19]]},"article-number":"2254"}}