Computer Science – Logic in Computer Science
Scientific paper
2006-06-12
LMCS 2 (2:6) 2006
Computer Science
Logic in Computer Science
Scientific paper
10.2168/LMCS-2(2:6)2006
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.
Carayol Arnaud
Meyer Antoine
No associations
LandOfFree
Context-Sensitive Languages, Rational Graphs and Determinism does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Context-Sensitive Languages, Rational Graphs and Determinism, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Context-Sensitive Languages, Rational Graphs and Determinism will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-647778