Skip to Main content Skip to Navigation
Journal articles

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 : Wednesday, February 26, 2020 - 7:06:06 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

273

Files downloads

464