scientific article; zbMATH DE number 4139308

MaRDI QIDQ3471701zbMATH OpenFDO

Authors Manfred Kudlek, Holger Petersen, Matthias Jantzen

Publication date 1990

zbMATH Keywords

context-free languagesdecision problemsDyck languageemptiness problemword problem

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4047162
• Publication:4725774
• scientific article; zbMATH DE number 1534571
• scientific article; zbMATH DE number 3854428
• Epsilon-reducible context-free languages and characterizations of indexed languages
• scientific article; zbMATH DE number 2050940
• scientific article; zbMATH DE number 994049
• scientific article; zbMATH DE number 4024816
• -reducible languages
• Reduced Languages as ω-Generators

Cited in

(13)

• The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index
• Simple reductions between D0L language and sequence equivalence problems
• Cancellation in context-free languages: enrichment by reduction
• On the computing powers of \(\mathcal{L}\)-reductions of insertion languages
• \(\mathcal{L}\)-reduction computation revisited
• The inclusion problem of context-free languages: some tractable cases
• scientific article; zbMATH DE number 994049 (Why is no real title available?)
• The Inclusion Problem of Context-Free Languages: Some Tractable Cases
• Coordinated pair systems ; part II : sparse structure of Dyck words and Ogden's lemma
• scientific article; zbMATH DE number 4047162 (Why is no real title available?)
• Normal forms for phrase-structure grammars
• scientific article; zbMATH DE number 512829 (Why is no real title available?)
• scientific article; zbMATH DE number 3999319 (Why is no real title available?)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3471701)