Visibly Pushdown Transducers with Look-Ahead - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Visibly Pushdown Transducers with Look-Ahead

Emmanuel Filiot
  • Fonction : Auteur
  • PersonId : 854583
Frédéric Servais
  • Fonction : Auteur
  • PersonId : 872096

Résumé

Visibly Pushdown Transducers (VPTs) form a subclass of pushdown transducers. In this paper, we investigate the extension of VPTs with look-ahead (VPTs+LA). Intuitively they are VPTs that can check that the well-nested subword starting at the current position belongs to a given visibly pushdown language. First, we show that VPTs+LA are not more expressive than VPTs, but they are exponentially more succinct. Second, we show that the class of deterministic VPTs+LA corresponds exactly to the class of functional VPTs. Finally, we show that, while VPTs+LA may be exponentially more succinct than VPTs, checking equivalence of functional VPTs+LA is, as for VPTs, Exptime-complete.
Fichier principal
Vignette du fichier
main.pdf (199.9 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

inria-00573965 , version 1 (06-03-2011)
inria-00573965 , version 2 (25-04-2011)

Identifiants

  • HAL Id : inria-00573965 , version 1

Citer

Emmanuel Filiot, Frédéric Servais. Visibly Pushdown Transducers with Look-Ahead. [Research Report] 2011. ⟨inria-00573965v1⟩
60 Consultations
224 Téléchargements

Partager

Gmail Facebook X LinkedIn More