Jantzen, Matthias; Kudlek, Manfred; Lange, Klaus-Jörn; Petersen, Holger 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. Cited in 3 Documents MSC: 68Q45 Formal languages and automata Keywords:context-free languages; Dyck language; Petri net languages; NP-complete sets Citations:Zbl 0633.00025 PDFBibTeX XML