@TechReport{      filiot:inria-00573965,
  Author        = "Filiot, Emmanuel and Servais, Fr{\'e}d{\'e}ric",
  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.}",
  affiliation   = "Computer Science Department, Universit{\'e} Libre de Bruxelles, Belgium",
  date-added    = "2013-11-13 11:42:41 +0000",
  date-modified = "2013-11-13 11:43:04 +0000",
  hal_id        = "inria-00573965",
  Keywords      = "visibly pushdown transducers",
  Language      = "Anglais",
  Month         = "March",
  PDF           = "http://hal.inria.fr/inria-00573965/PDF/main.pdf",
  Title         = "{Visibly Pushdown Transducers with Look-Ahead}",
  Type          = "Rapport de recherche",
  URL           = "http://hal.inria.fr/inria-00573965",
  Year          = "2011",
  bdsk-url-1    = "http://hal.inria.fr/inria-00573965",
  File          = "Visibly Pushdown Transducers with Look-Ahead - Filiot, Servais (1) (0) - a - a - x.pdf",
  file-2        = "Visibly Pushdown Transducers with Look-Ahead - Filiot, Servais (0) (0) - a - a - x.pdf"
}

@TechReport{ filiot:inria-00573965, Author = "Filiot, Emmanuel and Servais, Fr{\'e}d{\'e}ric", 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.}", affiliation = "Computer Science Department, Universit{\'e} Libre de Bruxelles, Belgium", date-added = "2013-11-13 11:42:41 +0000", date-modified = "2013-11-13 11:43:04 +0000", hal_id = "inria-00573965", Keywords = "visibly pushdown transducers", Language = "Anglais", Month = "March", PDF = "http://hal.inria.fr/inria-00573965/PDF/main.pdf", Title = "{Visibly Pushdown Transducers with Look-Ahead}", Type = "Rapport de recherche", URL = "http://hal.inria.fr/inria-00573965", Year = "2011", bdsk-url-1 = "http://hal.inria.fr/inria-00573965", File = "Visibly Pushdown Transducers with Look-Ahead - Filiot, Servais (1) (0) - a - a - x.pdf", file-2 = "Visibly Pushdown Transducers with Look-Ahead - Filiot, Servais (0) (0) - a - a - x.pdf" }