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.
