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 : 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},
     mrnumber = {2434038},
     zbl = {1149.68395},
     language = {en},
     url = {http://archive.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
SP  - 615
EP  - 630
VL  - 42
IS  - 3
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita:2008018/
DO  - 10.1051/ita:2008018
LA  - en
ID  - ITA_2008__42_3_615_0
ER  - 
%0 Journal Article
%A Meyer, Antoine
%T Traces of term-automatic graphs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2008
%P 615-630
%V 42
%N 3
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita:2008018/
%R 10.1051/ita:2008018
%G en
%F 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) no. 3, pp. 615-630. doi : 10.1051/ita:2008018. http://archive.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

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

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

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

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

[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

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

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

[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 | Zbl

[10] C. Morvan and C. Rispal, Families of automata characterizing context-sensitive languages. Acta Informatica 41 (2005) 293-314. | MR | Zbl

[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 | Zbl

[12] M. Penttonen, One-sided and two-sided context in formal grammars. Inform. Control 25 (1974) 371-392. | MR | Zbl

[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 :