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 (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.
Fichier principal
Vignette du fichier
main.pdf (172.73 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

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

Identifiants

  • HAL Id : inria-00573965 , version 2

Citer

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

Collections

LARA
60 Consultations
224 Téléchargements

Partager

Gmail Facebook X LinkedIn More