<p>I believe that a type of automata that your are looking for could be &quot;visibly counter automata&quot;. 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).</p>
<p>You might want to check the paper &quot;Regularity Problems for Visibly Pushdown Languages&quot; by Barany et al.: <a href="https://www.logic.rwth-aachen.de/%7Evbarany/BLS_stacs06_withAppendix.pdf" rel="noreferrer">https://www.logic.rwth-aachen.de/~vbarany/BLS_stacs06_withAppendix.pdf</a></p>

CC BY-SA 4.0
2020-10-31T14:29:09.890Z
2020-10-31T14:29:09.890Z
Bartosz Bednarczyk
<p>The &quot;narrowest&quot; 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?</p>
<p>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 &quot;call symbols&quot; and &quot;return symbols&quot; are matched one-to-one.</p>
<p>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.</p>

<reference-request><fl.formal-languages><context-free>
Generalizations of Dyck languages?
Antimony
# Generalizations of Dyck languages?

(Asked by: username_0 on 2020-10-30)

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.

**Tags:** reference-request, fl.formal-languages, context-free


---

## 1 answers

### Answer by username_1 on 2020-10-31. Score: 5 | Accepted answer

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](https://www.logic.rwth-aachen.de/%7Evbarany/BLS_stacs06_withAppendix.pdf)


---

