Properties of Visibly Pushdown Transducers
| Autor: | Emmanuel Filiot, Jean-Marc Talbot, Jean-François Raskin, Frédéric Servais, Pierre-Alain Reynier |
|---|---|
| Přispěvatelé: | Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Laboratoire d'informatique Fondamentale de Marseille - UMR 6166 (LIF), Université de la Méditerranée - Aix-Marseille 2-Université de Provence - Aix-Marseille 1-Centre National de la Recherche Scientifique (CNRS), Filiot, Emmanuel |
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
Discrete mathematics
Nested word Computer science Existential quantification Pushdown automaton Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Decidability [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 Nesting (computing) 020201 artificial intelligence & image processing Equivalence (formal languages) Word (computer architecture) Computer Science::Formal Languages and Automata Theory [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] PSPACE |
| Zdroj: | 35th International Symposium on Mathematical Foundations of Computer Science 35th International Symposium on Mathematical Foundations of Computer Science, Aug 2010, Brno, Czech Republic Mathematical Foundations of Computer Science 2010 ISBN: 9783642151545 |
| Popis: | International audience; Visibly pushdown transducers (VPTs) form a strict subclass of pushdown transducers (PTs) that extends finite state transducers with a stack. Like visibly pushdown automata, the input symbols determine the stack operations. It has been shown that visibly pushdown languages form a robust subclass of context-free languages. Along the same line, we show that word transductions defined by VPTs enjoy strong properties, in contrast to PTs. In particular, functionality is decidable in PTime, k-valuedness is in NPTime and equivalence of (non-deterministic) functional VPTs is ExpTime-C. Those problems are undecidable for PTs. Output words of VPTs are not necessarily well-nested. We identify a general subclass of VPTs that produce well-nested words, which is closed by composition, and for which the type checking problem is decidable. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|