Equivalence of Deterministic Nested Word to Word Transducers

Abstract : We study the equivalence problem of deterministic nested word to word transducers and show it to be surprisingly robust. Modulo polynomial time reductions, it can be identified with 4 equivalence problems for diverse classes of deterministic non-copying order-preserving transducers. In particular, we present polynomial time back and fourth reductions to the morphism equivalence problem on context free languages, which is known to be solvable in polynomial time.
Type de document :
Communication dans un congrès
Maciej Gebala and Malgorzata Korzeniowska and Witold Charatonik. Fundamentals of Computation Theory, Sep 2009, Wroclaw, Poland. Springer, 5699, pp.310-322, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-03409-1_28〉
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-00423961
Contributeur : Grégoire Laurence <>
Soumis le : mardi 13 octobre 2009 - 14:53:24
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : mardi 16 octobre 2012 - 12:10:59

Fichier

0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Slawomir Staworko, Grégoire Laurence, Aurélien Lemay, Joachim Niehren. Equivalence of Deterministic Nested Word to Word Transducers. Maciej Gebala and Malgorzata Korzeniowska and Witold Charatonik. Fundamentals of Computation Theory, Sep 2009, Wroclaw, Poland. Springer, 5699, pp.310-322, 2009, Lecture Notes in Computer Science. 〈10.1007/978-3-642-03409-1_28〉. 〈inria-00423961〉

Partager

Métriques

Consultations de la notice

534

Téléchargements de fichiers

174