D<: subtyping and typing are undecidable, but removing the bad-bounds rule and restricting comparison of function types yields decidable fragments with complete algorithms.
Verification of PCP-Related Computational Reductions in Coq
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
We formally verify several computational reductions concerning the Post correspondence problem (PCP) using the proof assistant Coq. Our verifications include a reduction of a string rewriting problem generalising the halting problem for Turing machines to PCP, and reductions of PCP to the intersection problem and the palindrome problem for context-free grammars. Interestingly, rigorous correctness proofs for some of the reductions are missing in the literature.
fields
cs.PL 1years
2019 1verdicts
CONDITIONAL 1representative citing papers
citing papers explorer
-
Undecidability of $D_{<:}$ and Its Decidable Fragments
D<: subtyping and typing are undecidable, but removing the bad-bounds rule and restricting comparison of function types yields decidable fragments with complete algorithms.