Regularity Problems for Visibly Pushdown Languages
Vince Barany‚ Christof Loeding and Olivier Serre
Abstract
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 be accepted by a finite automaton if only well-matched words are considered as input.
Details
| Book Title |
Proceedings of the 23rd Annual Symposioum on Theoretical Aspects of Computer Science‚ STACS 2006 |
| Editor |
B. Durand and W. Thomas |
| Pages |
420−431 |
| Publisher |
Springer |
| Series |
LNCS |
| Volume |
3884 |
| Year |
2006 |
Links
Related pages
|
People |