www.uhasselt.be
DSpace

Document Server@UHasselt >
Research >
All items >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/13178

Title: Visibly Pushdown Transducers with Look-ahead
Authors: Servais, Frederic
Filiot, Emmanuel
Issue Date: 2012
Publisher: Springer
Citation: Bieliková, Mária; Friedrich, Gerhard; Gottlob, Georg; Katzenbeisser, Stefan; Turán, György (Ed.). SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, Springer,p. 251-263
Series/Report: Lecture Notes in Computer Science
Series/Report no.: 7147
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.
URI: http://hdl.handle.net/1942/13178
DOI: 10.1007/978-3-642-27660-6_21
ISI #: 000307258500021
ISBN: 978-3-642-27659-0
ISSN: 0302-9743
Category: C1
Type: Proceedings Paper
Appears in Collections: Databases and Theoretical Computer Science

Files in This Item:

There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.