Congruences for Visibly Pushdown Languages

We study congruences on words in order to characterize the class of visibly pushdown languages (VPL), a subclass of context-free languages. For any language L, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if, L is a VPL. We then study the problem of finding canonical minimal deterministic automata for VPLs. Though VPLs in general do not have a unique minimal automata, we show that the class of well-matched VPLs does have unique minimal k-module automata. We then present a minimization algorithm, which takes a k-module visibly pushdown automaton and constructs the minimal k-module machine for it in polynomial time