On the multiplicity equivalence problem for context-free grammars

DOI10.1007/3-540-58131-6_50zbMATH Open1529.68135MaRDI QIDQ6183608FDOQ6183608

Authors: W. Kuich 

Publication date: 29 January 2024

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

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

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The equivalence problem of multitape finite automata
• Closure properties of slender languages
• Thin and slender languages
• Title not available (Why is that?)
• Language-theoretic problems arising from Richelieu cryptosystems

Cited In (2)

• Title not available (Why is that?)
• Tree generating context-free grammars and regular tree grammars are equivalent

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)