Visibly Pushdown Automata with Multiplicities: Finiteness and K-Boundedness
Mathieu Caralp, Pierre-Alain Reynier, Jean-marc Talbot · 2012
Abstract. We propose an extension of visibly pushdown automata by means of weights (represented as positive integers) associated with transitions, called visibly 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 computations. Finally, the multiplicity of such an automaton is the supremum of multiplicities 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 theK-boundedness problem, i.e. deciding whether the multiplicity is bounded byK: we prove this problem to be EXPTIMEcomplete whenK 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. 1