The Complexity of Prenex Separation Logic with One Selector
share
We first show that infinite satisfiability can be reduced to finite satisfiability for all prenex formulas of Separation Logic with k≥1 selector fields (k). Second, we show that this entails the decidability of the finite and infinite satisfiability problem for the class of prenex formulas of 1, by reduction to the first-order theory of one unary function symbol and unary predicate symbols. We also prove that the complexity is not elementary, by reduction from the first-order theory of one unary function symbol. Finally, we prove that the Bernays-Schönfinkel-Ramsey fragment of prenex 1 formulae with quantifier prefix in the language ∃^*∀^* is -complete. The definition of a complete (hierarchical) classification of the complexity of prenex 1, according to the quantifier alternation depth is left as an open problem.
READ FULL TEXT