The "narrowest" generalization of Dyck languages that I am aware of is Visibly Pushdown languages. Are there any useful classes of languages that are intermediate between Dyck languages and Visibly Pushdown Automata?

For example, Dyck languages require parenthesis to be paired, but visibly pushdown languages merely require that stack movement is controlled by the input tape, without any requirement that "call symbols" and "return symbols" are matched one-to-one.

It is easy to imagine an intermediate class, e.g. the class of visibly push down languages where the removal of all level symbols from each word results in a Dyck language, but I'm not sure if any such classes have useful properties or have been the subject of previous study.


I believe that a type of automata that your are looking for could be "visibly counter automata". It is easy to imagine what they should be - they are just standard automata but equipped with a set of non-negative unbounded counters that can be incremented/decremented after you read a specific letter (like in the case of VPA).

You might want to check the paper "Regularity Problems for Visibly Pushdown Languages" by Barany et al.: https://www.logic.rwth-aachen.de/~vbarany/BLS_stacs06_withAppendix.pdf


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.