Families of automata characterizing context-sensitive languages. (English) Zbl 1067.68086

Summary: In the hierarchy of infinite graph families, rational graphs are defined by rational transducers with labelled final states. This paper proves that their traces are precisely context-sensitive languages and that this result remains true for synchronized rational graphs.


68Q45 Formal languages and automata
Full Text: DOI Link


[1] Blumensath, A., Grädel, E. (2000) Automatic structures. Proceedings of 15th IEEE Symposium on Logic in Computer Science LICS 2000, pp. 51-62
[2] Carayol, A. (2001) Notions of determinism for rational graphs. Private communication
[3] Caucal, D. (2003) On the transition graphs of Turing machines. Theoretical Computer Science 296(2): 195-223 · Zbl 1044.68054
[4] Caucal, D. (2003) On transition graphs having a decidable monadic theory. Theoretical Computer Science 290(1): 79-115 · Zbl 1019.68066
[5] Chomsky, N. (1956) Three models for the description of language. IRE Transactions on Information Theory 2(3): 113-124 · Zbl 0156.25401
[6] Colcombet, T. (2002) On families of graphs having a decidable first order theory with reachability. Proceedings of the 29th International Conference on Automata, Languages, and Programming, vol. 2380 (Lecture Notes in Computer Science). Springer, Berlin Heidelberg New York · Zbl 1056.68107
[7] Courcelle, B. (1990) Handbook of Theoretical Computer Science, chap. Graph rewriting: an algebraic and logic approach. Elsevier · Zbl 0900.68282
[8] Elgot, C., Mezei, J. (1965) On relations defined by generalized finite automata. IBM 9: 47-68 · Zbl 0135.00704
[9] Epstein, D., Cannon, J.W., Holt, D.F., Levy, S.V.F., Paterson, M.S., Thurston (1992) Word processing in groups. Jones and Barlett publishers
[10] Frougny, C., Sakarovitch, J. (1993) Synchronized rational relations of finite and infinite words. Theoretical Computer Science 108: 45-82 · Zbl 0783.68065
[11] Kleene, S.C. (1956) Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata studies. Princeton, pp. 3-40
[12] Kuroda, S.-Y. (1964) Classes of languages and linear-bounded automata. Information and Control 7(2): 207-223 · Zbl 0199.04002
[13] Meyer, A. (2002) Sur des sous-familles de graphes rationnels. Rapport de DEA, Université de Rennes 1
[14] Morvan, C. (2000) On rational graphs. In: Tiuryn, J. (ed.) Fossacs 00, vol. 1784 (LNCS), pp. 252-266. ETAPS 2000 best theoretical paper Award · Zbl 0961.68107
[15] Morvan, C., Stirling, C. (2001) Rational graphs trace context-sensitive languages. In: Pultr, A., Sgall, J. (eds.) MFCS 01, vol. 2136 (LNCS), pp. 548-559 · Zbl 0999.68107
[16] Muller, D., Schupp, P. (1985) The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science 37: 51-75 · Zbl 0605.03005
[17] Penttonen, M. (1974) One-sided and two-sided context in formal grammars. Information and Control 25(4): 371-392 · Zbl 0282.68035
[18] Rispal, C. (2001) Graphes rationnels synchronisés. Rapport de DEA, Université de Rennes 1
[19] Rispal, C. (2002) Synchronized graphs trace the context-sensitive languages. In: Mayr, R., Kucera, A. (ed.) Infinity 02, vol. 68. (ENTCS) · Zbl 1270.68141
[20] Greibach, S., Ginsburg, S. (1969) Abstract families of languages. Mem. Am. Math. Soc. 87 · Zbl 0194.31402
[21] Sénizergues, G. (1992) Definability in weak monadic second-order logic of some infinite graphs. In: Dagstuhl seminar on Automata theory: Infinite computations, Warden, Germany, vol. 28, p. 16
[22] Urvoy, T. (2002) Abstract families of graphs. In: Toyama, M., Ito, M. (ed.) DLT 02, vol. 2450. (LNCS), pp. 381-392 · Zbl 1015.68090
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.