# Traces of term-automatic graphs

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 3, page 615-630
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMeyer, Antoine. "Traces of term-automatic graphs." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 615-630. <http://eudml.org/doc/250366>.

@article{Meyer2008,

abstract = {
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.
},

author = {Meyer, Antoine},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Languages; infinite automata; terms; tiling systems; complexity.; graphs defined by term transducers; formal languages},

language = {eng},

month = {6},

number = {3},

pages = {615-630},

publisher = {EDP Sciences},

title = {Traces of term-automatic graphs},

url = {http://eudml.org/doc/250366},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Meyer, Antoine

TI - Traces of term-automatic graphs

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/6//

PB - EDP Sciences

VL - 42

IS - 3

SP - 615

EP - 630

AB -
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.

LA - eng

KW - Languages; infinite automata; terms; tiling systems; complexity.; graphs defined by term transducers; formal languages

UR - http://eudml.org/doc/250366

ER -

## References

top- 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.
- N. Chomsky, On certain formal properties of grammars. Inform. Control2 (1959) 137–167. Zbl0088.10801
- A. Chandra, D. Kozen and L. Stockmeyer, Alternation. J. ACM28 (1981) 114–133. Zbl0473.68043
- A. Carayol and A. Meyer, Context-sensitive languages, rational graphs and determinism. Log. Meth. Comput. Sci.2 (2006). Zbl1126.68049
- D. Giammarresi and A. Restivo, Handbook of Formal Languages, Vol. 3, Chap. Two-dimensional languages. Springer (1996).
- B. Khoussainov and A. Nerode, Automatic presentations of structures, in International Workshop on Logical and Computational Complexity (LCC '94), Springer (1995) 367–392.
- S. Kuroda, Classes of languages and linear-bounded automata. Inform. Control7 (1964) 207–223. Zbl0199.04002
- M. Latteux and D. Simplot, Context-sensitive string languages and recognizable picture languages. Inform. Comput.138 (1997) 160–169. Zbl0895.68083
- 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. Zbl0961.68107
- C. Morvan and C. Rispal, Families of automata characterizing context-sensitive languages. Acta Informatica41 (2005) 293–314. Zbl1067.68086
- 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. Zbl0999.68107
- M. Penttonen, One-sided and two-sided context in formal grammars. Inform. Control25 (1974) 371–392. Zbl0282.68035
- 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).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.