| |
VOLUME 2, ISSUE 2, PAPER 6
|
Context-Sensitive Languages, Rational Graphs and Determinism
|
©Arnaud Carayol, IRISA
©Antoine Meyer, IRISA
|
Abstract
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.
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.
|
Publication date: July 19, 2006
Full Text: PDF | PostScript
DOI: 10.2168/LMCS-2(2:6)2006
Hit Counts: 3911 |
 Creative Commons | |
