Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness
| Autor: | Mathieu Caralp, Pierre-Alain Reynier, Jean-Marc Talbot |
|---|---|
| Přispěvatelé: | 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), Reynier, Pierre-Alain |
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Weighted tree automata Boundedness TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Nested word Pushdown automaton Nonlinear Sciences::Cellular Automata and Lattice Gases Embedded pushdown automaton Infimum and supremum Automaton Deterministic pushdown automaton Combinatorics TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Multiplicity [INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Bounded function Visibly Pushdown Automata Computer Science::Formal Languages and Automata Theory [INFO.INFO-FL] Computer Science [cs]/Formal Languages and Automata Theory [cs.FL] Mathematics |
| Zdroj: | Developments in Language Theory ISBN: 9783642316524 Developments in Language Theory |
| DOI: | 10.1007/978-3-642-31653-1_21 |
| Popis: | We propose an extension of visibly pushdown automata by means of weights (represented as positive integers) associated with transitions, called visi- bly pushdown automata with multiplicities. The multiplicity of a computation is the product of the multiplicities of the transitions used along this computation. The multiplicity of an input is the sum of the ones of all its successful compu- tations. Finally, the multiplicity of such an automaton is the supremum of multi- plicities over all possible inputs. We prove the problem of deciding whether the multiplicity of an automaton is finite to be in PTIME. We also consider the K-boundedness problem, i.e. deciding whether the multiplicity is bounded by K: we prove this problem to be EXPTIME- complete when K is part of the input and in PTIME when K is fixed. As visibly pushdown automata are closely related to tree automata, we discuss deeply the relationship of our extension with weighted tree automata. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|