Carayol, Arnaud; Meyer, Antoine Context-sensitive languages, rational graphs and determinism. (English) Zbl 1126.68049 Log. Methods Comput. Sci. 2, No. 2, Paper 6, 24 p. (2006). Summary: 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. Cited in 5 Documents MSC: 68Q45 Formal languages and automata Keywords:formal languages PDFBibTeX XMLCite \textit{A. Carayol} and \textit{A. Meyer}, Log. Methods Comput. Sci. 2, No. 2, Paper 6, 24 p. (2006; Zbl 1126.68049) Full Text: DOI