{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T16:40:04Z","timestamp":1736527204417,"version":"3.32.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T00:00:00Z","timestamp":1156464000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2006,10,17]]},"DOI":"10.1007\/s00236-006-0022-z","type":"journal-article","created":{"date-parts":[[2006,8,25]],"date-time":"2006-08-25T17:21:22Z","timestamp":1156526482000},"page":"265-292","source":"Crossref","is-referenced-by-count":1,"title":["Linearly bounded infinite graphs"],"prefix":"10.1007","volume":"43","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":"297","published-online":{"date-parts":[[2006,8,25]]},"reference":[{"key":"22_CR1","unstructured":"Arnold, A., Nivat, M.: Comportements de processus. In: Colloque de l\u2019Association Francaise pour la Cybern\u00e9tique \u00c9conomique et Th\u00e9orique: Les Math\u00e9matiques de l\u2019Informatique (AFCET \u201982), pp. 35\u201368 (1982)"},{"key":"22_CR2","doi-asserted-by":"crossref","unstructured":"Blumensath, A., Gr\u00e4del, E.: Automatic structures. In: Proceedings of the 15th IEEE Symposium on Logic in Computer Science (LICS 2000), pp. 51\u201362. IEEE (2000)","DOI":"10.1109\/LICS.2000.855755"},{"key":"22_CR3","doi-asserted-by":"crossref","unstructured":"Carayol, A., Meyer, A.: Context-sensitive languages, rational graphs and determinism. Logical Methods in Computer Science 2(2) (2006). DOI 10.2168\/LMCS-2(2:6)2006","DOI":"10.2168\/LMCS-2(2:6)2006"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Caucal, D.: On infinite transition graphs having a decidable monadic theory. In: Proceedings of 23rd International Colloquium on Automata, Languages, and Programming (ICALP 1996), Lecture Notes in Computer Science, vol. 1099, pp. 194\u2013205. Springer, Berlin Heidelberg New York (1996)","DOI":"10.1007\/3-540-61440-0_128"},{"key":"22_CR5","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/S0304-3975(01)00089-5","volume":"290","author":"D. Caucal","year":"2003","unstructured":"Caucal D. (2003) On infinite transition graphs having a decidable monadic theory. Theor. Comput. Sci. 290, 79\u2013115","journal-title":"Theor. Comput. Sci."},{"key":"22_CR6","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/S0304-3975(02)00655-2","volume":"296","author":"D. Caucal","year":"2003","unstructured":"Caucal D. (2003) On the transition graphs of Turing machines. Theor. Comput. Sci. 296, 195\u2013223","journal-title":"Theor. Comput. Sci."},{"key":"22_CR7","first-page":"299","volume":"34","author":"D. Caucal","year":"2001","unstructured":"Caucal D., Knapik T. (2001) An internal presentation of regular graphs by prefix-recognizable graphs. Theor. Comput. Sci. 34, 299\u2013336","journal-title":"Theor. Comput. Sci."},{"key":"22_CR8","doi-asserted-by":"crossref","unstructured":"Caucal, D., Knapik, T.: A Chomsky-like hierarchy of infinite graphs. In: Proceedings of the 27th International Symposium on Mathematical Foundations of Computer Science (MFCS 2002). Lecture Notes in Computer Science, vol. 2420, pp. 177\u2013187. Springer Berlin Heidelberg New York (2002)","DOI":"10.1007\/3-540-45687-2_14"},{"key":"22_CR9","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","volume":"2","author":"N. Chomsky","year":"1959","unstructured":"Chomsky N. (1959) On certain formal properties of grammars. Inform Control 2, 137\u2013167","journal-title":"Inform Control"},{"key":"22_CR10","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/BF02088013","volume":"21","author":"B. Courcelle","year":"1989","unstructured":"Courcelle B. (1989) The monadic second-order logic of graphs, II: Infinite graphs of bounded width. Math. Syst. Theory 21, 187\u2013221","journal-title":"Math. Syst. Theory"},{"key":"22_CR11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1147\/rd.91.0047","volume":"9","author":"C. Elgot","year":"1965","unstructured":"Elgot C., Mezei J. (1965) On relations defined by finite automata. IBM J. Res. Developm. 9, 47\u201368","journal-title":"IBM J. Res. Developm."},{"issue":"1","key":"22_CR12","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-3975(93)90230-Q","volume":"108","author":"C. Frougny","year":"1993","unstructured":"Frougny C., Sakarovitch J. (1993) Synchronized rational relations of finite and infinite words. Theor. Comput. Sci. 108(1): 45\u201382","journal-title":"Theor. Comput. Sci."},{"key":"22_CR13","unstructured":"Hopcroft J., Ullman J. Introduction to Automata Theory, Languages and Computation. Addison-Wesley, (1979)"},{"issue":"5","key":"22_CR14","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0217058","volume":"17","author":"N. Immerman","year":"1988","unstructured":"Immerman N. (1988) Nondeterministic space is closed under complementation. SIAM J. Comput. 17(5): 935\u2013938","journal-title":"SIAM J. Comput."},{"key":"22_CR15","doi-asserted-by":"crossref","unstructured":"Khoussainov, B., Nerode, A.: Automatic presentations of structures. In: Selected papers of the 1994 International Workshop on Logic and Computational Complexity. Lecture Notes in Computer Science, vol. 960, pp. 367\u2013392. Springer, Berlin Heidelberg New York (1994)","DOI":"10.1007\/3-540-60178-3_93"},{"key":"22_CR16","doi-asserted-by":"crossref","unstructured":"Knapik, T., Payet, \u00c9.: Synchronized product of linear bounded machines. In: Proceedings of the 12th International Symposium on Fundamentals of Computation Theory, (FCT 1999). Lecture Notes in Computer Science, vol. 1684, pp. 362\u2013373. Springer, Berlin Heidelberg New York (1999)","DOI":"10.1007\/3-540-48321-7_30"},{"issue":"2","key":"22_CR17","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1016\/S0019-9958(64)90120-2","volume":"7","author":"S. Kuroda","year":"1964","unstructured":"Kuroda S. (1964) Classes of languages and linear-bounded automata. Inform. Control 7(2): 207\u2013223","journal-title":"Inform. Control"},{"key":"22_CR18","doi-asserted-by":"crossref","unstructured":"Latteux, M., Simplot, D., Terlutte, A.: Iterated length-preserving rational transductions. In: Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science (MFCS 1998). Lecture Notes in Computer Science, vol. 1450, pp. 286\u2013295. Springer Verlag (1998)","DOI":"10.1007\/BFb0055778"},{"key":"22_CR19","unstructured":"Milner, R.: Communication and Concurrency. Prentice-Hall International (1989)"},{"key":"22_CR20","doi-asserted-by":"crossref","unstructured":"Morvan, C.: On rational graphs. In: Proceedings of the 3rd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2000). Lecture Notes in Computer Science, vol. 1784, pp. 252\u2013266. Springer, Berlin Heidelberg New York (2000)","DOI":"10.1007\/3-540-46432-8_17"},{"key":"22_CR21","doi-asserted-by":"crossref","unstructured":"Morvan, C., Stirling, C.: Rational graphs trace context-sensitive languages. In: Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001). Lecture Notes in Computer Science, vol. 2136, pp. 548\u2013559. Springer, Berlin Heidelberg New York (2001)","DOI":"10.1007\/3-540-44683-4_48"},{"key":"22_CR22","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0304-3975(85)90087-8","volume":"37","author":"D.E. Muller","year":"1985","unstructured":"Muller D.E., Schupp P.E. (1985) The theory of ends, pushdown automata, and second-order logic. Theor. Comput. Sci. 37, 51\u201375","journal-title":"Theor. Comput. Sci."},{"key":"22_CR23","doi-asserted-by":"crossref","unstructured":"Payet, \u00c9.: Thue specifications, infinite graphs and synchronized product. Ph.D. thesis, Universit\u00e9 de la R\u00e9union (2000)","DOI":"10.3233\/FUN-2000-44303"},{"key":"22_CR24","doi-asserted-by":"crossref","unstructured":"Rispal, C.: The synchronized graphs trace the context-sensitive languages. In: Proceedings of the 4th International Workshop on Verification of Infinite-State Systems (INFINITY 2002). Electronic Notes in Theoretical Computer Science, vol. 68 (2002)","DOI":"10.1016\/S1571-0661(04)80533-4"},{"key":"22_CR25","unstructured":"Stirling, C.: Decidability of bisimulation equivalence for pushdown processes. Tech. Rep. EDI-INF-RR-0005, School of Informatics, University of Edinburgh (2000)"},{"key":"22_CR26","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/BF00299636","volume":"26","author":"R. Szelepcsenyi","year":"1988","unstructured":"Szelepcsenyi R. (1988) The method of forced enumeration for nondeterministic automata. Acta Inform. 26, 279\u2013284","journal-title":"Acta Inform."},{"key":"22_CR27","doi-asserted-by":"crossref","unstructured":"Thomas, W.: A short introduction to infinite automata. In: Proceedings of the 5th International Conference on Developments in Language Theory (DLT 2001). Lecture Notes in Computer Science, vol. 2295, pp. 130\u2013144. Springer Berlin Heidelberg New York (2001)","DOI":"10.1007\/3-540-46011-X_10"},{"issue":"5","key":"22_CR28","doi-asserted-by":"crossref","first-page":"379","DOI":"10.1051\/ita\/1996300503791","volume":"30","author":"A. Weber","year":"1996","unstructured":"Weber A. (1996) Decomposing a k-valued transducer into k unambiguous ones. Informatique Th\u00e9or. Appl. 30(5): 379\u2013413","journal-title":"Informatique Th\u00e9or. Appl."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-006-0022-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00236-006-0022-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-006-0022-z","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T16:01:10Z","timestamp":1736524870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00236-006-0022-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,8,25]]},"references-count":28,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10,17]]}},"alternative-id":["22"],"URL":"https:\/\/doi.org\/10.1007\/s00236-006-0022-z","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"type":"print","value":"0001-5903"},{"type":"electronic","value":"1432-0525"}],"subject":[],"published":{"date-parts":[[2006,8,25]]}}}