Regularity Problems for Visibly Pushdown Languages

Conference item

Visibly pushdown automata are special pushdown automata whose stack behavior is driven by the input symbols according to a partition of the alphabet. We show that it is decidable for a given visibly pushdown automaton whether it is equivalent to a visibly counter automaton, i.e. an automaton that uses its stack only as counter. In particular, 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...

Expand abstract

Authors: Barany, V; Loeding, C; Serre, O

• Publisher: Springer
• Host title: Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science‚ STACS 2006
• Volume: 3884
• Publication date: 2006-01-01