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
topHow 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.
- A. Chandra, D. Kozen and L. Stockmeyer, Alternation. J. ACM28 (1981) 114–133.
- A. Carayol and A. Meyer, Context-sensitive languages, rational graphs and determinism. Log. Meth. Comput. Sci.2 (2006).
- 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.
- M. Latteux and D. Simplot, Context-sensitive string languages and recognizable picture languages. Inform. Comput.138 (1997) 160–169.
- 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.
- C. Morvan and C. Rispal, Families of automata characterizing context-sensitive languages. Acta Informatica41 (2005) 293–314.
- 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.
- M. Penttonen, One-sided and two-sided context in formal grammars. Inform. Control25 (1974) 371–392.
- 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.