Document Server@UHasselt >
All items >
Please use this identifier to cite or link to this item:
|Title: ||Visibly Pushdown Transducers with Look-ahead|
|Authors: ||Servais, Frederic|
|Issue Date: ||2012|
|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 deﬁne. 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.|
|ISI #: ||000307258500021|
|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.