The synchronized graphs trace the context-sensitive languages

Abstract : Morvan and Stirling have proved that the context-sensitive languages are exactly the traces of graphs de ned by transducers with labelled nal states. We prove that this result is still true if we restrict to the traces of graphs de ned by synchronized transducers with labelled nal states. From their construction, we deduce that the context-sensitive languages are the languages of path labels leading from and to rational vertex sets of letter-to-letter rational graphs.
Document type :
Conference papers
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00620118
Contributor : Chloé Rispal <>
Submitted on : Monday, October 3, 2011 - 3:27:04 PM
Last modification on : Friday, February 8, 2019 - 3:38:03 PM
Long-term archiving on : Wednesday, January 4, 2012 - 2:26:18 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00620118, version 1

Collections

Citation

Chloé Rispal. The synchronized graphs trace the context-sensitive languages. INFINITY 2002, 4th International Workshop on Verification of Infinite-State Systems, Aug 2003, Brno, Czech Republic. 10pp. ⟨hal-00620118⟩

Share

Metrics

Record views

172

Files downloads

139