Mnacho Echenim, Radu Iosif, Nicolas Peltier
On the Expressive Completeness of Bernays-Schonfinkel-Ramsey Separation Logic (2018)
On the Expressive Completeness of Bernays-Schonfinkel-Ramsey Separation Logic (2018)
TR-2018-1.pdf
Keywords:
Abstract: This paper investigates the satisfiability problem for Separation Logic, with unrestricted nesting of separating conjunctions and implications, for prenex formulae with quantifier prefix in the language $exists^*forall^*$, in the cases where the universe of possible locations is either countably infinite or finite. In analogy with first-order logic with uninterpreted predicates and equality, we call this fragment Bernays-Schonfinkel-Ramsey Separation Logic [$sr(seplogk{k})$]. We %found show that, unlike in first-order logic, the (in)finite satisfiability problem is undecidable for $sr(seplogk{k})$ and we define two non-trivial subsets thereof, that are decidable for finite and infinite satisfiability, respectively, by controlling the occurrences of universally quantified variables within the scope of separating implications, as well as the polarity of the occurrences of the latter. The decidability results are obtained by a controlled elimination of separating connectives, described as egin{inparaenum}[(i)] item an effective translation of a prenex form Separation Logic formula into a combination of a small number of emph{test formulae}, using only first-order connectives, followed by % item a translation of the latter into an equisatisfiable first-order formula. end{inparaenum}
