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.
Type de document :
Article dans une revue
Acta Informatica, Springer Verlag, 2005, 41, pp.293-314. 〈10.1007/s00236-004-0160-0〉
Liste complète des métadonnées

Littérature citée [17 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00525422
Contributeur : Christophe Morvan <>
Soumis le : lundi 11 octobre 2010 - 17:31:08
Dernière modification le : mercredi 11 avril 2018 - 12:12:02
Document(s) archivé(s) le : mercredi 12 janvier 2011 - 03:02:52

Fichier

morvan-rispal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

176

Téléchargements de fichiers

156