Carayol, Arnaud and Meyer, Antoine - Context-Sensitive Languages, Rational Graphs and Determinism

lmcs:2254 - Logical Methods in Computer Science, July 19, 2006, Volume 2, Issue 2
Context-Sensitive Languages, Rational Graphs and Determinism

Authors: Carayol, Arnaud and Meyer, Antoine

We investigate families of infinite automata for context-sensitive languages. An infinite automaton is an infinite labeled graph with two sets of initial and final vertices. Its language is the set of all words labelling a path from an initial vertex to a final vertex. In 2001, Morvan and Stirling proved that rational graphs accept the context-sensitive languages between rational sets of initial and final vertices. This result was later extended to sub-families of rational graphs defined by more restricted classes of transducers. languages.<br><br> Our contribution is to provide syntactical and self-contained proofs of the above results, when earlier constructions relied on a non-trivial normal form of context-sensitive grammars defined by Penttonen in the 1970's. These new proof techniques enable us to summarize and refine these results by considering several sub-families defined by restrictions on the type of transducers, the degree of the graph or the size of the set of initial vertices.


Source : oai:arXiv.org:cs/0606053
DOI : 10.2168/LMCS-2(2:6)2006
Volume: Volume 2, Issue 2
Published on: July 19, 2006
Submitted on: January 31, 2005
Keywords: Computer Science - Logic in Computer Science,F.4.3


Share

Consultation statistics

This page has been seen 53 times.
This article's PDF has been downloaded 9 times.