Entailment is Undecidable for Symbolic Heap Separation Logic Formulae with Non-Established Inductive Rules
Mnacho Echenim, Radu Iosif, Nicolas Peltier · 2020
Entailment is undecidable in general for Separation (SL) Logic formulæ with inductive definitions, but it has been shown to be decidable [1] if the inductive rules satisfy three conditions, namely progress, connectivity and establishment.We show that entailment is undecidable if the latter condition is dropped, thus drawing a much clearer frontier for (un)decidability.