Two-Way Parikh Automata with a Visibly Pushdown Stack
| Autor: | Emmanuel Filiot, Jean-Marc Talbot, Luc Dartois |
|---|---|
| Přispěvatelé: | Laboratoire d'Algorithmique Complexité et Logique (LACL), Université Paris-Est Créteil Val-de-Marne - Paris 12 (UPEC UP12), Université libre de Bruxelles (ULB), Modélisation et Vérification (MOVE), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Bojańczyk M., Simpson A., ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016), Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
Discrete mathematics
050101 languages & linguistics Nested word TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Computer science 05 social sciences Pushdown automaton 02 engineering and technology Decision problem 16. Peace & justice Decidability Undecidable problem Automaton TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Bounded function Computer Science::Logic in Computer Science 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Equivalence (formal languages) Computer Science::Formal Languages and Automata Theory |
| Zdroj: | Foundations of Software Science and Computation Structures. FoSSaCS 2019 FOSSACS 2019 FOSSACS 2019, Apr 2019, Pragues, Czech Republic. pp.189-206, ⟨10.1007/978-3-030-17127-8_11⟩ Bojańczyk M., Simpson A. Foundations of Software Science and Computation Structures. FoSSaCS 2019, Springer, pp.189-206, 2019, 978-3-030-17126-1. ⟨10.1007/978-3-030-17127-8_11⟩ Lecture Notes in Computer Science ISBN: 9783030171261 FoSSaCS |
| Popis: | International audience; In this paper, we investigate the complexity of the emptiness problem for Parikh automata equipped with a pushdown stack. Push-down Parikh automata extend pushdown automata with counters which can only be incremented and an acceptance condition given as a semi-linear set, which we represent as an existential Presburger formula over the final values of the counters. We show that the non-emptiness problem both in the deterministic and non-deterministic cases is NP-c. If the input head can move in a two-way fashion, emptiness gets undecidable, even if the pushdown stack is visibly and the automaton deterministic. We define a restriction, called the single-use restriction, to recover decid-ability in the presence of two-wayness, when the stack is visibly. This syntactic restriction enforces that any transition which increments at least one dimension is triggered only a bounded number of times per input position. Our main contribution is to show that non-emptiness of two-way visibly Parikh automata which are single-use is NExpTime-c. We finally give applications to decision problems for expressive transducer models from nested words to words, including the equivalence problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|