On the Decidability of Grammar Problems

DOI10.1145/322307.322317zbMath0497.68049OpenAlexW1984570925MaRDI QIDQ3962487

Harry B. III Hunt

Publication date: 1982

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/322307.322317

zbMATH Keywords

undecidabilityseparabilitydecidabilitycontext-free grammarssimilarity relationgrammatical coveringcomplexity of s- grammars and s-languagesefficient reductions of membership problems for always-halting Turing machinesemptiness-of-intersection problem for pairs of s-grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (6)

A complete refinement procedure for regular separability of context-free languages ⋮ Unnamed Item ⋮ The language intersection problem for non-recursive context-free grammars ⋮ A Note on Decidable Separability by Piecewise Testable Languages ⋮ Separability by piecewise testable languages is \textsc{PTime}-complete ⋮ Unnamed Item

This page was built for publication: On the Decidability of Grammar Problems