English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We first show that infinite satisfiability can be reduced to finitesatisfiability for all prenex formulas of Separation Logic with $k\geq1$selector fields ($\seplogk{k}$). Second, we show that this entails thedecidability of the finite and infinite satisfiability problem for the class ofprenex formulas of $\seplogk{1}$, by reduction to the first-order theory of oneunary function symbol and unary predicate symbols. We also prove that thecomplexity is not elementary, by reduction from the first-order theory of oneunary function symbol. Finally, we prove that the Bernays-Sch\"onfinkel-Ramseyfragment of prenex $\seplogk{1}$ formulae with quantifier prefix in thelanguage $\exists^*\forall^*$ is \pspace-complete. The definition of a complete(hierarchical) classification of the complexity of prenex $\seplogk{1}$,according to the quantifier alternation depth is left as an open problem.

The Complexity of Prenex Separation Logic with One Selector