Two-Way Visibly Pushdown Automata and Transducers
| Autor: | Pierre-Alain Reynier, Jean-Marc Talbot, Luc Dartois, Emmanuel Filiot |
|---|---|
| Přispěvatelé: | Département d'Informatique [Bruxelles] (ULB), Faculté des Sciences [Bruxelles] (ULB), Université libre de Bruxelles (ULB)-Université libre de Bruxelles (ULB), Modélisation et Vérification (MOVE), Laboratoire d'informatique Fondamentale de Marseille (LIF), Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-École Centrale de Marseille (ECM)-Centre National de la Recherche Scientifique (CNRS), Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU)-Centre National de la Recherche Scientifique (CNRS)-École Centrale de Marseille (ECM)-Aix Marseille Université (AMU) |
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
FOS: Computer and information sciences
TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Nested word Formal Languages and Automata Theory (cs.FL) Computer science Computer Science - Formal Languages and Automata Theory 0102 computer and information sciences 02 engineering and technology 01 natural sciences Regular language 0202 electrical engineering electronic engineering information engineering [INFO]Computer Science [cs] Equivalence (formal languages) Finite set ComputingMilieux_MISCELLANEOUS Discrete mathematics Pushdown automaton Computer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing) Automaton Decidability TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Transducer 010201 computation theory & mathematics F.4.3 020201 artificial intelligence & image processing Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16) Proc. 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), 2016, Unknown, Unknown Region. pp.217--226, ⟨10.1145/2933575.2935315⟩ |
| Popis: | Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models are equivalent: deterministic two-way transducers, monadic second-order (MSO) transducers, and deterministic one-way automata equipped with a finite number of registers. Nested words are words with a nesting structure, allowing to model unranked trees as their depth-first-search linearisations. In this paper, we consider transformations from nested words to words, allowing in particular to produce unranked trees if output words have a nesting structure. The model of visibly pushdown transducers allows to describe such transformations, and we propose a simple deterministic extension of this model with two-way moves that has the following properties: i) it is a simple computational model, that naturally has a good evaluation complexity; ii) it is expressive: it subsumes nested word-to-word MSO transducers, and the exact expressiveness of MSO transducers is recovered using a simple syntactic restriction; iii) it has good algorithmic/closure properties: the model is closed under composition with a unambiguous one-way letter-to-letter transducer which gives closure under regular look-around, and has a decidable equivalence problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|