×

Dyc\(k_ 1\)-reductions of context-free languages. (English) Zbl 0642.68134

Fundamentals of computation theory, Proc. Int. Conf., Kazan/USSR 1987, Lect. Notes Comput. Sci. 278, 218-227 (1987).
Summary: [For the entire collection see Zbl 0633.00025.]
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, the Petri net languages, and NP-complete sets.

MSC:

68Q45 Formal languages and automata

Citations:

Zbl 0633.00025