Voir la notice de l'article provenant de la source Numdam
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.
Keywords: 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://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
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
Cité par Sources :