Families of automata characterizing context-sensitive languages

Abstract : In the hierarchy of infinite graph families, rational graphs are defined by rational transducers with labelled final states. This paper proves that their traces are precisely context-sensitive languages and that this result remains true for synchronized rational graphs.
Document type :
Journal articles
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal.inria.fr/inria-00525422
Contributor : Christophe Morvan <>
Submitted on : Monday, October 11, 2010 - 5:31:08 PM
Last modification on : Friday, February 8, 2019 - 4:10:03 PM
Long-term archiving on : Wednesday, January 12, 2011 - 3:02:52 AM

File

morvan-rispal.pdf
Files produced by the author(s)

Identifiers

Citation

Christophe Morvan, Chloé Rispal. Families of automata characterizing context-sensitive languages. Acta Informatica, Springer Verlag, 2005, 41, pp.293-314. ⟨10.1007/s00236-004-0160-0⟩. ⟨inria-00525422⟩

Share

Metrics

Record views

204

Files downloads

273