Visibly Pushdown Transducers with Look-Ahead
| Autor: | Emmanuel Filiot, Frédéric Servais |
|---|---|
| Přispěvatelé: | Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Mária Bieliková and Gerhard Friedrich and Georg Gottlob and Stefan Katzenbeisser and György Turán |
| Jazyk: | angličtina |
| Rok vydání: | 2011 |
| Předmět: |
Discrete mathematics
Computer science Pushdown automaton 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] 010201 computation theory & mathematics Computer Science::Logic in Computer Science 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] 020201 artificial intelligence & image processing Tree automaton Equivalence (formal languages) Look-ahead ComputingMilieux_MISCELLANEOUS Computer Science::Formal Languages and Automata Theory |
| Zdroj: | [Research Report] 2011 SOFSEM 2012: Theory and Practice of Computer Science ISBN: 9783642276590 SOFSEM Current Trends in Theory and Practice of Computer Science (SOFSEM) Current Trends in Theory and Practice of Computer Science (SOFSEM), 2012, Unknown, Unknown Region. pp.251-263, ⟨10.1007/978-3-642-27660-6_21⟩ |
| DOI: | 10.1007/978-3-642-27660-6_21⟩ |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|