  We define a class of Separation Logic formulae, whose entailment problem:
given formulae $\phi, \psi_1, \ldots, \psi_n$, is every model of $\phi$ a model
of some $\psi_i$? is 2EXPTIME-complete. The formulae in this class are
existentially quantified separating conjunctions involving predicate atoms,
interpreted by the least sets of store-heap structures that satisfy a set of
inductive rules, which is also part of the input to the entailment problem.
Previous work consider established sets of rules, meaning that every
existentially quantified variable in a rule must eventually be bound to an
allocated location, i.e. from the domain of the heap. In particular, this
guarantees that each structure has treewidth bounded by the size of the largest
rule in the set. In contrast, here we show that establishment, although
sufficient for decidability (alongside two other natural conditions), is not
necessary, by providing a condition, called equational restrictedness, which
applies syntactically to (dis-)equalities. The entailment problem is more
general in this case, because equationally restricted rules define richer
classes of structures, of unbounded treewidth. In this paper we show that (1)
every established set of rules can be converted into an equationally restricted
one and (2) the entailment problem is 2EXPTIME-complete in the latter case,
thus matching the complexity of entailments for established sets of rules.
