On the Decidability of Grammar Problems

DOI10.1145/322307.322317zbMATH Open0497.68049OpenAlexW1984570925MaRDI QIDQ3962487FDOQ3962487

Authors: H. 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

separabilitycontext-free grammarsdecidabilityundecidabilitysimilarity 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

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

Cited In (6)

• A complete refinement procedure for regular separability of context-free languages
• A Note on Decidable Separability by Piecewise Testable Languages
• The language intersection problem for non-recursive context-free grammars
• Regular separability of well-structured transition systems
• Regular separability of one counter automata
• Separability by piecewise testable languages is \textsc{PTime}-complete

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

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