Visibly pushdown automata are a restricted model of pushdown automata which enjoy good properties similar to finite automata. While the language defined by a visibly pushdown automaton can hardly be regular, we can study the decision problem whether it is the restriction of a regular language to the set of well-matched words. This is known to be decidable in elementary time (Bárány, Löding, Serre 2006) but only P-hard, leaving a big gap in complexity. The problem is closely related to the weak validation problem (Segoufin, Vianu 2002), whose decidability status is still unknown.

I will present ongoing work towards proving that the problem can be solved in polynomial-time. In particular, we show how to efficiently test if a visibly pushdown automaton defines a visibly counter language, and if a visibly counter automaton defines a regular language restricted to well-matched words.

(joint work with Annika Delb and Moses Ganardi)