inria-00573965, version 2
Visibly Pushdown Transducers with Look-Ahead
Emmanuel Filiot
1Frédéric Servais
a, 1
(2011)
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.
- a – Université Libre de Bruxelles
- 1 : Computer Science Department, Université Libre de Bruxelles, Belgium
- Université Libre de Bruxelles
- Domaine : Informatique/Théorie et langage formel
- Versions disponibles : v1 (06-03-2011) v2 (25-04-2011)
- inria-00573965, version 2
- http://hal.inria.fr/inria-00573965
- oai:hal.inria.fr:inria-00573965
- Contributeur : Emmanuel Filiot
- Soumis le : Lundi 25 Avril 2011, 15:57:06
- Dernière modification le : Lundi 25 Avril 2011, 17:07:41






Documents associés
Exporter