On the Decidability of Grammar Problems
From MaRDI portal
Publication:3962487
DOI10.1145/322307.322317zbMath0497.68049MaRDI QIDQ3962487
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
undecidability; separability; decidability; context-free grammars; similarity relation; grammatical covering; complexity of s- grammars and s-languages; efficient reductions of membership problems for always-halting Turing machines; emptiness-of-intersection problem for pairs of s-grammars
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68N20: Theory of compilers and interpreters
03D60: Computability and recursion theory on ordinals, admissible sets, etc.
Related Items
Unnamed Item, Unnamed Item, A complete refinement procedure for regular separability of context-free languages, The language intersection problem for non-recursive context-free grammars, Separability by piecewise testable languages is \textsc{PTime}-complete, A Note on Decidable Separability by Piecewise Testable Languages