zbMATH — the first resource for mathematics

Dyck\(_ 1\)-reductions of context-free languages. (English) Zbl 0695.68054
Summary: We consider language families obtained from context-free languages by complete cancellation of substrings from the Dyck language with one pair of parentheses. The class of such languages contains languages with arbitrary exponential growth of word lengths, the EOL languages, the Petri net languages, and NP-complete sets. We show that the emptiness problem for this class is undecidable, and that the word problem for the subclass based on context-free languages of finite index is decidable.

68Q45 Formal languages and automata
03D40 Word problems, etc. in computability and recursion theory
03B25 Decidability of theories and sets of sentences