s'authentifier
version française rss feed

inria-00573965, version 2

Visibly Pushdown Transducers with Look-Ahead

Emmanuel Filiot () 1, Frédéric Servais () a1

(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.

 
  • inria-00573965, version 2
  • oai:hal.inria.fr:inria-00573965
  • Contributeur : 
  • Soumis le : Lundi 25 Avril 2011, 15:57:06
  • Dernière modification le : Lundi 25 Avril 2011, 17:07:41
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...