Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete

DOI10.1016/0304-3975(84)90092-6zbMath0556.68040OpenAlexW2007431032MaRDI QIDQ761043

Dung T. Huynh

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(84)90092-6

zbMATH Keywords

equivalencecomputational complexitydecision problemscontext-free grammarsmembership

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

A note on the complexity of deciding bisimilarity of normed unary processes, Classifying the computational complexity of problems, Operational State Complexity and Decidability of Jumping Finite Automata, Graph Ramsey theory and the polynomial hierarchy, Unnamed Item, On deciding trace equivalences for processes

Cites Work

• Remarks on the complexity of an invariant of context-free grammars
• On the equivalence, containment, and covering problems for the regular and context-free languages
• Commutative grammars: The complexity of uniform word problems
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item