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

Voir la notice de l'article provenant de la source Numdam

MR EuDML Zbl

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
Keywords: languages, infinite automata, terms, tiling systems, complexity 
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
@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},
     year = {2008},
     publisher = {EDP-Sciences},
     volume = {42},
     number = {3},
     doi = {10.1051/ita:2008018},
     mrnumber = {2434038},
     zbl = {1149.68395},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.1051/ita:2008018/
%R 10.1051/ita:2008018
%G en
%F ITA_2008__42_3_615_0

Cité par Sources :