In formal language theory, many families of languages are defined using either grammars or finite acceptors. For instance, context-sensitive languages are the languages generated by growing grammars, or equivalently those accepted by Turing machines whose work tape's size is proportional to that of their input. A few years ago, a new characterisation of context-sensitive languages as the sets of traces, or path labels, of rational graphs (infinite graphs defined by sets of finite-state transducers) was established. We investigate a similar characterisation in the more general framework of graphs defined by term transducers. In particular, we show that the languages of term-automatic graphs between regular sets of vertices coincide with the languages accepted by alternating linearly bounded Turing machines. As a technical tool, we also introduce an arborescent variant of tiling systems, which provides yet another characterisation of these languages.
@article{ITA_2008__42_3_615_0,
author = {Meyer, Antoine},
title = {Traces of term-automatic graphs},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {42},
year = {2008},
pages = {615-630},
doi = {10.1051/ita:2008018},
mrnumber = {2434038},
zbl = {1149.68395},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2008__42_3_615_0}
}
Meyer, Antoine. Traces of term-automatic graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) pp. 615-630. doi : 10.1051/ita:2008018. http://gdmltest.u-ga.fr/item/ITA_2008__42_3_615_0/
[1] and , Automatic structures, in Proceedings of the 15th IEEE Symposium on Logic in Computer Science (LICS 2000), IEEE (2000) 51-62. | MR 1946085
[2] , On certain formal properties of grammars. Inform. Control 2 (1959) 137-167. | MR 105365 | Zbl 0088.10801
[3] , and , Alternation. J. ACM 28 (1981) 114-133. | MR 603186 | Zbl 0473.68043
[4] and , Context-sensitive languages, rational graphs and determinism. Log. Meth. Comput. Sci. 2 (2006). | MR 2295771 | Zbl 1126.68049
[5] and , Handbook of Formal Languages, Vol. 3, Chap. Two-dimensional languages. Springer (1996). | MR 1470021
[6] and , Automatic presentations of structures, in International Workshop on Logical and Computational Complexity (LCC '94), Springer (1995) 367-392. | MR 1449670
[7] , Classes of languages and linear-bounded automata. Inform. Control 7 (1964) 207-223. | MR 169724 | Zbl 0199.04002
[8] and , Context-sensitive string languages and recognizable picture languages. Inform. Comput. 138 (1997) 160-169. | MR 1479320 | Zbl 0895.68083
[9] , On rational graphs, in Proceedings of the 3rd International Conference on Foundations of Software Science and Computation Structures (FoSSaCS 2000). Lect. Notes Comput. Sci. 1784 (2000) 252-266. | MR 1798632 | Zbl 0961.68107
[10] and , Families of automata characterizing context-sensitive languages. Acta Informatica 41 (2005) 293-314. | MR 2129796 | Zbl 1067.68086
[11] and , Rational graphs trace context-sensitive languages, in Proceedings of the 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001). Lect. Notes Comput. Sci. 2136 (2001) 548-559. | MR 1907042 | Zbl 0999.68107
[12] , One-sided and two-sided context in formal grammars. Inform. Control 25 (1974) 371-392. | MR 356593 | Zbl 0282.68035
[13] , The synchronized graphs trace the context-sensitive languages, in Proceedings of the 4th International Workshop on Verification of Infinite-State Systems (INFINITY 2002). Elect. Notes Theoret. Comput. Sci. 68 (2002).