Regularity Problems for Visibly Pushdown Languages

Abstract. Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a par-tition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter au-tomaton, i.e. an automaton that uses its stack only as counter. In par-ticular, this allows to decide whether a given visibly pushdown language is a regular restriction of the set of well-matched words, meaning that the language can be accepted by a finite automaton if only well-matched words are considered as input.