On the Decidability of Grammar Problems

DOI10.1145/322307.322317MaRDI QIDQ3962487zbMATH OpenOpenAlexFDO

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

complexity of s- grammars and s-languagescontext-free grammarsdecidabilityefficient reductions of membership problems for always-halting Turing machinesemptiness-of-intersection problem for pairs of s-grammarsgrammatical coveringseparabilitysimilarity relationundecidability

Mathematics Subject Classification ID

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

Cited in

(10)

• Separability by piecewise testable languages is \textsc{PTime}-complete
• A complete refinement procedure for regular separability of context-free languages
• A Note on Decidable Separability by Piecewise Testable Languages
• Regular separability of one counter automata
• Regular separability of well-structured transition systems
• The language intersection problem for non-recursive context-free grammars
• Timed games and deterministic separability
• Containment of regular path queries under path constraints
• Regular separators for VASS coverability languages
• The complexity of separability for semilinear sets and Parikh automata

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)