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 (VPTla). 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 VPTla are not more expressive than VPT, but are exponentially more succinct. Second, we show that the class of deterministic VPTla corresponds exactly to the class of functional VPT, yielding a simple characterization of functional VPT. Finally, we show that while VPTla are exponentially more succinct than VPT, checking equivalence of functional VPTla is, as for VPT, EXPT-C. As a consequence, we show that any functional VPT is equivalent to an unambiguous one.