Skip to Main content Skip to Navigation
Reports

Visibly Pushdown Transducers with Look-Ahead

Abstract : Visibly Pushdown Transducers (VPTs) form a subclass of pushdown transducers. In this paper, we investigate the extension of VPTs with look-ahead (VPTs+LA). Intuitively they are VPTs that can check that the well-nested subword starting at the current position belongs to a given visibly pushdown language. First, we show that VPTs+LA are not more expressive than VPTs, but they are exponentially more succinct. Second, we show that the class of deterministic VPTs+LA corresponds exactly to the class of functional VPTs. Finally, we show that, while VPTs+LA may be exponentially more succinct than VPTs, checking equivalence of functional VPTs+LA is, as for VPTs, Exptime-complete.
Complete list of metadata

https://hal.inria.fr/inria-00573965
Contributor : Emmanuel Filiot Connect in order to contact the contributor
Submitted on : Sunday, March 6, 2011 - 1:07:37 PM
Last modification on : Tuesday, October 19, 2021 - 12:55:35 PM
Long-term archiving on: : Tuesday, June 7, 2011 - 2:25:39 AM

File

main.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00573965, version 1

Citation

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

Share

Metrics

Record views

59

Files downloads

200