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 (6)

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

This page was built for publication: Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete