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 | Source: | 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. | Keywords: | formal language theory; automata | Document URI: | http://hdl.handle.net/1942/13178 | ISBN: | 978-3-642-27659-0 | DOI: | 10.1007/978-3-642-27660-6_21 | ISI #: | 000307258500021 | Rights: | Copyright © 2012, Springer Berlin / Heidelberg | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2014 |
Appears in Collections: | Research publications |
Show full item record
SCOPUSTM
Citations
8
checked on Sep 4, 2020
WEB OF SCIENCETM
Citations
7
checked on Sep 28, 2024
Page view(s)
88
checked on Aug 25, 2023
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.