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. 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. |
Year | DOI | Venue |
---|---|---|
2006 | 10.2168/LMCS-2(2:6)2006 | LOGICAL METHODS IN COMPUTER SCIENCE |
Keywords | DocType | Volume |
language theory,infinite graphs,automata,determinism | Journal | 2 |
Issue | ISSN | Citations |
2 | 1860-5974 | 5 |
PageRank | References | Authors |
0.49 | 17 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
arnaud carayol | 1 | 216 | 20.22 |
Antoine Meyer | 2 | 79 | 4.69 |