Visibly Pushdown Transducers with Look-Ahead

Abstract : Visibly Pushdown Transducers (VPT) form a subclass of pushdown transducers. In this paper, we investigate the extension of VPT with visibly pushdown look-ahead (VPT+LA). Their transitions are guarded by visibly pushdown automata that can check whether the well-nested subword starting at the current position belongs to the language they define. First, we show that VPT+LA are not more expressive than VPT, but are exponentially more succinct. Second, we show that the class of deterministic VPT+LA corresponds exactly to the class of functional VPT, yielding a simple characterization of functional VPT. Finally, we show that while VPT+LA are exponentially more succinct than VPT, checking equivalence of functional VPT+LA is, as for VPT, Exptime-complete. As a consequence of these results, we show that for any functional VPT there is an equivalent unambiguous one.
Type de document :
Rapport
[Research Report] 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00573965
Contributeur : Emmanuel Filiot <>
Soumis le : lundi 25 avril 2011 - 15:57:06
Dernière modification le : vendredi 16 septembre 2016 - 15:14:53
Document(s) archivé(s) le : jeudi 8 novembre 2012 - 17:15:56

Fichier

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

Identifiants

  • HAL Id : inria-00573965, version 2

Collections

Citation

Emmanuel Filiot, Frédéric Servais. Visibly Pushdown Transducers with Look-Ahead. [Research Report] 2011. 〈inria-00573965v2〉

Partager

Métriques

Consultations de la notice

90

Téléchargements de fichiers

75