On the multiplicity equivalence problem for context-free grammars

DOI10.1007/3-540-58131-6_50MaRDI QIDQ6183608zbMATH OpenFDO

Authors W. Kuich

Publication date 29 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Recommendations

• On the commutative equivalence of context-free languages
• Complexity of problems of commutative grammars
• The complexity of equivalence problems for commutative grammars
• Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
• On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages

Cites work

• scientific article; zbMATH DE number 3932372 (Why is no real title available?)
• scientific article; zbMATH DE number 58306 (Why is no real title available?)
• scientific article; zbMATH DE number 3293666 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Closure properties of slender languages
• Language-theoretic problems arising from Richelieu cryptosystems
• The equivalence problem of multitape finite automata
• Thin and slender languages

Cited in

(2)

• Tree generating context-free grammars and regular tree grammars are equivalent
• scientific article; zbMATH DE number 7453188 (Why is no real title available?)

This page was built for publication: On the multiplicity equivalence problem for context-free grammars

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