Skip to Main content Skip to Navigation

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Emmanuel Filiot Connect in order to contact the contributor
Submitted on : Monday, April 25, 2011 - 3:57:06 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:35 PM
Long-term archiving on: : Thursday, November 8, 2012 - 5:15:56 PM


Files produced by the author(s)


  • HAL Id : inria-00573965, version 2



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



Record views


Files downloads