Traces of term-automatic graphs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 615-630.

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.

DOI : https://doi.org/10.1051/ita:2008018
Classification : 68Q45,  68Q05
Mots clés : languages, infinite automata, terms, tiling systems, complexity
@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},
     pages = {615--630},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     year = {2008},
     doi = {10.1051/ita:2008018},
     zbl = {1149.68395},
     mrnumber = {2434038},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2008018/}
}
TY  - JOUR
AU  - Meyer, Antoine
TI  - Traces of term-automatic graphs
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2008
DA  - 2008///
SP  - 615
EP  - 630
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2008018/
UR  - https://zbmath.org/?q=an%3A1149.68395
UR  - https://www.ams.org/mathscinet-getitem?mr=2434038
UR  - https://doi.org/10.1051/ita:2008018
DO  - 10.1051/ita:2008018
LA  - en
ID  - ITA_2008__42_3_615_0
ER  - 
Meyer, Antoine. Traces of term-automatic graphs. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 42 (2008) no. 3, pp. 615-630. doi : 10.1051/ita:2008018. http://www.numdam.org/articles/10.1051/ita:2008018/

[1] A. Blumensath and E. Grädel, Automatic structures, in Proceedings of the 15th IEEE Symposium on Logic in Computer Science (LICS 2000), IEEE (2000) 51-62. | MR 1946085

[2] N. Chomsky, On certain formal properties of grammars. Inform. Control 2 (1959) 137-167. | MR 105365 | Zbl 0088.10801

[3] A. Chandra, D. Kozen and L. Stockmeyer, Alternation. J. ACM 28 (1981) 114-133. | MR 603186 | Zbl 0473.68043

[4] A. Carayol and A. Meyer, Context-sensitive languages, rational graphs and determinism. Log. Meth. Comput. Sci. 2 (2006). | MR 2295771 | Zbl 1126.68049

[5] D. Giammarresi and A. Restivo, Handbook of Formal Languages, Vol. 3, Chap. Two-dimensional languages. Springer (1996). | MR 1470021

[6] B. Khoussainov and A. Nerode, Automatic presentations of structures, in International Workshop on Logical and Computational Complexity (LCC '94), Springer (1995) 367-392. | MR 1449670

[7] S. Kuroda, Classes of languages and linear-bounded automata. Inform. Control 7 (1964) 207-223. | MR 169724 | Zbl 0199.04002

[8] M. Latteux and D. Simplot, Context-sensitive string languages and recognizable picture languages. Inform. Comput. 138 (1997) 160-169. | MR 1479320 | Zbl 0895.68083

[9] C. Morvan, 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] C. Morvan and C. Rispal, Families of automata characterizing context-sensitive languages. Acta Informatica 41 (2005) 293-314. | MR 2129796 | Zbl 1067.68086

[11] C. Morvan and C. Stirling, 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] M. Penttonen, One-sided and two-sided context in formal grammars. Inform. Control 25 (1974) 371-392. | MR 356593 | Zbl 0282.68035

[13] C. Rispal, 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).

Cité par Sources :