1 Introduction↩︎

In this paper we investigate the application of the SCAN algorithm [1] and resolution in solving second-order quantifier elimination and computing uniform interpolants for basic path logic [2], [3].

We say that a clause is prefix stable for variables if for any variable in the clause, its prefix in any argument sequence (in which it occurs) is the same [4]. For example, the first clause below is prefix stable for variables and the second is not (where \(y\) has two different prefixes): \[\begin{align} &P(x,y)\lor Q(x,y,a)\\ &P(x,y)\lor Q(a,y,z). \end{align}\] By basic path logic (\(BPL\)) we understand the clausal class in which: (i) all argument sequences contain only variables and constants, and (ii) all clauses have prefix stability for variables. This implies \(BPL\) is a subclass of the clausal class for the \(\exists^*\forall^*\)-fragment of first-order logic.

Basic path logic has been introduced as the clausal class associated with modal logic \(\mathit{KD}\) based on the world path semantics and the functional translation to first-order logic [2], [3]. Basic path logic is computationally well-behaved: it is decidable by resolution without special refinements (no ordering- or selection-based restriction of inferences is needed) [3], which implies that any sound and refutationally complete ordering- and/or selection-based refinement provides a decision procedure for this class.¹ Further, the performance of resolution theorem provers is superior for modal logic problems when they are mapped to basic path logic than when they are mapped to the guarded fragment using the standard relational translation [6], [7].

The ordered fragment of first-order logic consists of those formulas in which, roughly speaking: (i) the argument sequence of each predicate is of the form \((x_1,x_2,\dots,x_n)\); and (ii) if \(i<j\), no quantifier binding \(x_j\) out-scopes any quantifier binding \(x_i\). For example, the following sentence belongs to the fragment: \[\forall x_1\exists x_2(R(x_1,x_2)\land \forall x_3\neg S(x_1,x_2,x_3)).\] The ordered fragment first appeared in the “fluted schema” introduced by W. V. Quine [8], [9], but the formal definition we follow was given, independently of Quine’s work, by A. Herzig [10], where the term “ordered formula” was coined. Herzig proposed a linear-time reduction from satisfiability of ordered formulas to satisfiability in \(\mathit{KD}\), which implies that the former is decidable in PSPACE. Also, it is proved in [2] that the quantifier prefix in the prenex normal form of any ordered formula can be freely permuted without affecting satisfiability; thus, by this permutability, every ordered formula can be transformed into \(BPL\)[3], [11]. Moreover, the ordered fragment is shown in [12] to have the Craig Interpolation Property.

Second-order quantifier elimination (SOQE) is the problem of reducing a formula \(\exists \overline{X} \varphi\), where \(\overline{X}\) are predicate variables and \(\varphi\) is a first-order formula, to an equivalent first-order formula \(\psi\) (possibly with equality) that does not contain any of the predicate symbols \(\overline{X}\) [1], [13]. For example, \[\exists X (Xa\land\forall x(Xx\to Bx)) \equiv Ba \quad \text{and} \quad \exists X(Xa\land\neg Xb) \equiv a\not\approx b.\]

SOQE is an important topic of artificial intelligence that has real-world applications in diverse areas, from knowledge representation, knowledge sharing and communication of agents, to answer set programming and logic, including description logics and modal correspondence theory. SOQE has been studied in the guise of forgetting [14], strongest necessary and weakest sufficient conditions in knowledge representation [15]–[20], symbol elimination and projection [21]. SOQE has applications in knowledge representation for ontology extraction, ontology comparison, and abductive reasoning [16], [17], [22]–[26], and in artificial intelligence for common-sense reasoning and circumscription [1], databases [13] and answer set programming  [27], [28].

SOQE is tightly connected to the problem of computing uniform interpolants. Given a first-order formula \(\varphi\) and a subset \(\Sigma\) of \(\mathop{\mathrm{sig}}(\varphi)\), the signature of \(\varphi\), a uniform interpolant of \(\varphi\) with regard to \(\Sigma\) is a first-order formula \(\psi\) such that \(\mathop{\mathrm{sig}}(\psi)=\Sigma\) and \[\models\varphi\to\chi \quad \ \text{iff} \ \quad \models\psi\to\chi \;\text{for every \chi with \mathop{\mathrm{sig}}(\varphi)\cap \mathop{\mathrm{sig}}(\chi)\subseteq \Sigma}.\] Note that if \(\overline{X}=\mathop{\mathrm{sig}}(\varphi)\setminus\Sigma\) and \(\psi\) is the result of SOQE for \(\varphi\), i.e., \(\psi\equiv\exists\overline{X}\varphi\), then \(\psi\) is a uniform interpolant of \(\varphi\) with regard to \(\Sigma\). For example, \(Ba\) is a uniform interpolant of \(Xa \wedge \forall x (Xx \rightarrow Bx)\) with regard to the signature containing only \(B\) and \(a\), and \(a\not\approx b\) is a uniform interpolant of \(Xa \wedge \neg Xb\) with regard to the signature containing only \(a\) and \(b\). Also, when we are interested in uniform interpolation in a fragment of first-order logic, the aforementioned \(\varphi\), \(\psi\) and \(\chi\) are assumed to be formulas of the fragment. In other words, the construction of uniform interpolants is dependent on the target language. For example, a uniform interpolant of \(Xa \wedge \neg Xb\) is \(\top\) in first-order logic without equality (instead of \(a\not\approx b\)). However, the target language of SOQE is always assumed to be first-order logic with equality.

There are few settings in which SOQE and uniform interpolation are known to be decidable. For propositional logic SOQE and uniform interpolation are decidable, but in more general settings, e.g., for many modal logics, description logics and first-order logic, they are not even semi-decidable.

Efforts to automate modal correspondence theory led to the development of the SOQE algorithm SCAN for first-order clause logic [1], [29]. Given a clause set \(N\) and predicate variables \(\overline{X}\), the SCAN algorithm attempts to eliminate the symbols \(\overline{X}\) in an iterative process performing all necessary inferences upon \(X\)-literals and deleting clauses once they are no longer needed. On successful termination, the returned clause set \(M\) is equivalent to \(\exists \overline{X} N\). The soundness of SCAN for the SOQE problem has been proved in [1], but because of the inherent undecidability of SOQE it cannot generally be complete. It was however shown that SCAN is complete for solving the correspondence problem of the class of Sahlqvist axioms in modal logic [30]. It is also known to be sound and complete for propositional problems. Moreover, if SCAN does not terminate then the conjunction of the infinite set of persisting clauses (closed under first-order universal quantification and) free of predicate variables from \(\overline{X}\) is a solution to the problem [1].

Because of the mentioned nice properties of basic path logic in resolution, the question arises whether the SCAN algorithm can be applied to solve the SOQE problem and compute uniform interpolants in this case. The main research questions and contributions of this paper are the following:

1.0.0.1 1. Characterisation of the search space of SCAN on basic path logic with fixed constant positions.

The SCAN algorithm based on constraint resolution replaces unification in the resolution and factoring rules by adding inequalities (constraints) to conclusions. These constraints fall outside the scope of the language of basic path logic, which means the latter is insufficient to characterize the search space of SCAN. For that reason, and because \(BPL\) is slightly more general than it needs to be for deciding the ordered fragment and modal logic \(\mathit{KD}\), we introduce the class \(BPL_{fcp}^{\not\approx}\), in which inequalities are allowed and constants have fixed argument positions, and show that \(BPL_{fcp}^{\not\approx}\) is closed under the rules of SCAN.

1.0.0.2 2. Termination and completeness of SCAN on \(BPL_{fcp}^{\not\approx}\).

We further show that the set of \(BPL_{fcp}^{\not\approx}\)-clauses over a finite relational signature is finitely bounded modulo condensing (a form of subsumption deletion). This implies that SCAN is a decision procedure for SOQE and is SOQE-complete for \(BPL_{fcp}^{\not\approx}\). The result can be seen to follow from the characterisation and properties of \(BPL\) in [3], [11], noting that normalised conclusions of SCAN inferences are either standard resolvents or conditionals enumerating the coincidence of pairs of constants with the same indices.

1.0.0.3 3. Consequence-preserving clausification for the ordered fragment.

The previous transformation of the ordered fragment to clauses in \(BPL\) or \(BPL_{fcp}^{\not\approx}\) involves an unusual quantifier exchange operation [2]. Although it is sufficient for solving the satisfiability problem, for uniform interpolation we need a clausification that preserves logical consequences in the ordered fragment. To address this problem, we introduce constant Skolemisation (CSk) and show that: for any sentences \(\phi\) and \(\psi\) of the ordered fragment, \(\models \phi \mathrel{\rightarrow}\psi\) iff \(\models \mathop{\mathrm{CSk}(\phi )}\mathrel{\rightarrow}\psi\). Moreover, the clausification of ordered sentences using CSk also results in \(BPL\) and \(BPL_{fcp}^{\not\approx}\) clauses.

1.0.0.4 4.Uniform interpolants (for the ordered fragment) in basic path logic.

Unskolemisation of a clause set returned by SCAN is always possible since the clauses in question contain only variables and constants. Specifically, every such clause set can be expressed as a first-order formula in prenex normal form with a \(\exists^*\forall^*\) quantifier prefix. However, such a formula is in general not expressible in the ordered fragment. As a partial solution to the problem, we show that clauses with inequalities between constants can be deleted without any cost on logical consequences in equality-free first-order logic, and therefore we obtain a “uniform interpolant” expressed in basic path logic. It remains open whether an additional procedure can be devised to construct a uniform interpolant in the ordered fragment.

The rest of the paper is arranged as follows. In Section 2 we recap the definition of basic path logic and its nice properties when using resolution. These results allow us to conclude uniform interpolation completeness for \(BPL\). In Section 3, we recap the definition of the ordered fragment, introduce constant Skolemisation, and prove that it preserves logical consequences in the ordered fragment. We present the SCAN algorithm and some basic results in Section 4, and then formulate the clausal class \(BPL_{fcp}^{\not\approx}\) in Section 5, where we prove its closure under constraint resolution and the termination and SOQE-completeness of SCAN. Section 6 discusses the elimination of inequalities and the remaining problem in computing uniform interpolants for the ordered fragment.

2 Basic Path Logic, Resolution and Uniform Interpolation↩︎

Let \(u_i\) denote the \(i\)th element in the sequence \(\overline{u}\) of terms. The prefix of \(u_i\) in \(\overline{u}\) is \(\varepsilon\) (the empty sequence) if \(i = 1\), and \((u_1, \ldots, u_{i-1})\), otherwise.

Let \(T\) denote a set of sequences of terms. We say \(T\) is prefix stable, if for any term \(t\), all its occurrences in \(T\) have the same prefix. We say a clause is prefix stable if the set of argument sequences of the literals is prefix stable.

In basic path logic (\(BPL\)) only variables are required to be prefix stable. A set of sequences of terms is prefix stable for variables if every occurrence of a variable \(u\) in the set has the same prefix [3], [11]. Recall the example we saw above: \[\begin{align} &P(x,y)\lor Q(x,y,a)\\ &P(x,y)\lor Q(a,y,z). \end{align}\] The first clause is prefix stable for variables because every occurrence of \(x\) has the prefix \(\varepsilon\), and every occurrence of \(y\) has the prefix \((x)\); by contrast, the second is not prefix stable for variables because the first occurrence of \(y\) has the prefix \((x)\) while the second has the prefix \((a)\).

Let \(\Sigma\) be a signature of finitely many predicate symbols \(P, Q, \ldots\), constants \(a,b, \ldots\) and infinitely many first-order variables \(x, y, \ldots\) By definition, \(BPL\) is the class of \(\Sigma\)-clauses which are prefix stable for variables. Specifically, for any clause \(C\) in \(BPL\):

(i) \(C\) is a disjunction of literals of the form \((\neg)P(\overline{u})\), where each term \(u_i\) in \(\overline{u}\) is either a variable or a constant, and

(ii) for any two literals \((\neg)P(u_1, \ldots, u_m)\) and \((\neg)Q(v_1, \ldots, v_n)\) in \(C\) both the following conditions hold for variables:

 **T1**

 :   If $u_i$ and $v_j$ are the same variable then $i=j$.

 **T2**

 :   Each pair $u_k$ and $v_k$ preceding $u_i$ and $v_i$ are
     identical.

\(BPL\) has the property that prefix stability for variables is preserved by binary resolution and factoring defined in Table ¿tbl:table95resol95inference95rules? and also tautology deletion, subsumption deletion and condensation [3], [11]. This implies

Theorem 2([item95resol95decides95BPL]) also gives us a decision procedure for consequence finding in \(BPL\), because binary resolution and subsumption is in general consequence finding complete:

This means that binary resolution computes strongest consequences modulo subsumption, which in turn implies that \(BPL\) has the uniform interpolation property and the approach is uniform interpolation complete for \(BPL\):

3 The Ordered Fragment and Constant Skolemisation↩︎

Let \(X_m = \{ x_1, \ldots, x_m\}\) denote an ordered set of variables. A formula in the ordered fragment is an ordered formula over \(X_n\) for some \(n \geq 0\), defined inductively as follows:

(i) For any \(n\)-ary predicate symbol \(P\), \(P(x_1, \ldots, x_n)\) is an ordered formula over \(X_n\).

(ii) Any Boolean combination of ordered formulas over \(X_n\) is an ordered formula over \(X_n\).

(iii) If \(\phi\) is an ordered formula over \(X_{n+1}\), then \(\exists x_{n+1} \phi\) and \(\forall x_{n+1} \phi\) are ordered formulas over \(X_n\).

Recall the example we saw before: \[\forall x_1\exists x_2(R(x_1,x_2)\land \forall x_3\neg S(x_1,x_2,x_3)).\] We can easily check that it is an ordered formula over \(X_0\).

We observe that the free variables in ordered formulas over \(X_n\) are exactly \(x_1,\dots,x_n\), and, in particular, ordered formulas over \(X_0\) are closed. We thus refer to ordered formulas over \(X_0\) as ordered sentences.

Let \(\psi\) be a first-order formula in prenex normal form. We use \(\Upsilon \psi\) to denote the result of moving universal quantifiers to the front, i.e., the quantifier prefix in \(\Upsilon \psi\) is of the form \(\forall^*\exists^*\). The operator \(\Upsilon\) was called the quantifier exchange operator in [2]. Although, in general, \(\Upsilon \psi\) is not logically equivalent to \(\psi\), we have the following result.

Notice that by pushing the negation inwards in \(\neg \Upsilon \psi\) we get a \(\exists^*\forall^*\)-formula. Moreover, transforming \(\neg \Upsilon\psi\) into clausal form results in a clause set in \(BPL\) [3], [11]. Thus, satisfiability in the ordered fragment can also be decided by resolution without special refinements.

However, if we are to use SCAN or resolution to compute uniform interpolants for ordered sentences, the invariance of satisfiability in Theorem 5 is insufficient. We need to show that by transforming an ordered sentence into a set of clauses in \(BPL\), its logical consequences in the ordered fragment are not affected. For this purpose, we introduce constant Skolemisation (for ordered sentences) and prove that it preserves logical consequences in the ordered fragment.

In constant Skolemisation, we introduce new constants for all eliminated quantifiers (so no functional terms are added). The definition below is adapted from that of inner Skolemisation [32], [33] presented in [13]. Let \(\phi\) be a first-order formula in which no occurrence of subformulas of \(\phi\) is of zero polarity. The constant Skolemisation of \(\phi\), written \(\mathop{\mathrm{CSk}(\phi)}\), is the result of exhaustive application of the following operation.

1. If \(\delta\) is an occurrence of a subformula of the form \(\exists x\gamma\) and is of positive polarity, pick a fresh constant \(c\) and replace \(\delta\) by \(\gamma(x/c)\), the result of substituting \(c\) for \(x\) in \(\gamma\).

2. If \(\delta\) is an occurrence of a subformula of the form \(\forall x\gamma\) and is of negative polarity, pick a fresh constant \(c\) and replace \(\delta\) by \(\gamma(x/c)\), the result of substituting \(c\) for \(x\) in \(\gamma\).

For example, \[\begin{align} & \mathop{\mathrm{CSk}(\forall x\exists y\forall z P(x,y,z))} = \forall x\forall z P(x,c,z)\\ & \mathop{\mathrm{CSk}(\exists x\forall y (R(x,y)\lor \neg\forall z S(x,y,z)))} = \forall y (R(c_1,y)\lor \neg S(c_1,y,c_2)). \end{align}\] During the construction of \(\mathop{\mathrm{CSk}(\phi)}\), if the quantifier in a subformula occurrence \(\delta\) in \(\phi\) is eliminated by introducing a constant \(c\), we say that \(c\) is the Skolem constant associated with \(\delta\). Thus, in the second example, \(c_1\) is the Skolem constant associated with \(\exists x\forall y (R(x,y)\lor \neg\forall z S(x,y,z))\), and \(c_2\) is the one associated with \(\forall z S(x,y,z)\).

In the rest of this section we show that logical consequences in the ordered fragment is invariant under constant Skolemsation.

Therefore, for any ordered sentences \(\phi\) and \(\psi\), if \(\models\phi\to\psi\) then \(\models\mathop{\mathrm{CSk}(\phi)}\to\psi\). To show that logical consequences are also preserved in the other direction, i.e., if \(\models\mathop{\mathrm{CSk}(\phi)}\to\psi\) then \(\models\phi\to\psi\), we need a characterisation of the expressive power of the ordered fragment. The bisimulation for the ordered fragment, or ordered bisimulation, is developed in [12] in a more general setting. In the following we offer a definition adapted for the present work.

Given structures \(\mathfrak{A}\) and \(\mathfrak{B}\) interpreting the same signature, an ordered bisimulation between \(\mathfrak{A}\) and \(\mathfrak{B}\) is a binary relation \(Z\subseteq \bigcup_{n\geq 0}(A^n\times B^n)\) such that for any \(\bar{a}\in A^n\), \(\bar{b}\in B^n\) with \(\bar{a} Z \bar{b}\), the following conditions hold:

1. for any \(n\)-ary predicate \(P\) in the signature, \(\bar{a}\in P^\mathfrak{A}\) iff \(\bar{b}\in P^\mathfrak{B}\);

2. for any \(a\in A\) there is \(b\in B\) such that \(\bar{a}aZ\bar{b}b\);

3. for any \(b\in B\) there is \(a\in A\) such that \(\bar{a}aZ\bar{b}b\).

By a pointed structure we understand a pair \((\mathfrak{A},\bar{a})\), where \(\mathfrak{A}\) is a structure and \(\bar{a}\) is a tuple of elements of \(\mathfrak{A}\). We say that pointed structures \((\mathfrak{A},\bar{a})\) and \((\mathfrak{B},\bar{b})\) are ordered bisimilar, written \((\mathfrak{A},\bar{a})\sim(\mathfrak{B},\bar{b})\), if there is an ordered bisimulation between \(\mathfrak{A}\) and \(\mathfrak{B}\) and, in addition, \(\bar{a}Z\bar{b}\). We write \(\mathfrak{A}\sim\mathfrak{B}\) if \((\mathfrak{A},\varepsilon)\sim(\mathfrak{B},\varepsilon)\) holds, where \(\varepsilon\) is the empty tuple.

We use the following trick, taken from [35], to inflate models of equality-free first-order formulas. We assume that the signature in question is relational. Let \(\mathfrak{A}\) be a structure (with domain \(A\)) and \(n\) a positive integer. Then \(\mathfrak{A}'\) is defined to be the structure over the domain \(A\times \{1,\dots,n\}\) such that for any \(m\)-ary predicate \(R\), any \(a_1,\dots,a_m\in A\), and any \(i_1,\dots,i_m\in\{1,\dots,n\}\), \[(\langle a_1,i_1\rangle,\dots,\langle a_m,i_m\rangle)\in R^{\mathfrak{A}'} \text{ iff } (a_1,\dots,a_m)\in R^{\mathfrak{A}}.\] We call \(\mathfrak{A}'\) the \(n\)-fold Cartesian product of \(\mathfrak{A}\). Intuitively, \(\mathfrak{A}'\) is the result of duplicating each element of \(\mathfrak{A}\) for \(n-1\) times.

Now we are ready to prove the following lemma, which establishes the preservation of logical consequences in the other direction.

Finally, since the transformation to clausal form (after constant Skolemisation) involves only logical equivalences, we conclude that, for any ordered sentence \(\phi\), the clausal form of \(\mathop{\mathrm{CSk}(\phi)}\) has the same logical consequences in the ordered fragment as \(\phi\).

4 The SCAN Algorithm↩︎

The input to SCAN is a set \(N\) of first-order clauses and a list of predicate variables \(\overline{X}\). The aim is to eliminate these symbols from \(N\) producing a set \(M\) such that \[\models \exists X N \mathrel{\equiv}M.\]

When SCAN is applied to a first-order formula \(\varphi\), the formula is first transformed into clausal form as implemented in the Otter theorem prover. This involves four steps: (i) transforming the formula into prenex normal form \(\overline{Q x} \varphi'\), which moves the quantifiers to the outside of the formula so that \(\varphi'\) is free of quantifiers. (ii) Skolemisation: the replacement of existentially quantified variables by Skolem terms and dropping the existential quantifiers, which results in a formula \(\forall \overline{y} \varphi''\) where \(\varphi''\) is quantifier-free and \(\overline{y} \subseteq \overline{x}\), In the next step, (iii), \(\varphi''\) is transformed into conjunctive normal form. The clausal form \(N = \mathop{\mathrm{Cls}}(\varphi)\) is then obtained by (iv) writing \(\varphi''\) as a set of clauses.

By \(\overline{s}\) we denote a sequence of terms \((s_1, \ldots, s_n)\). \(L(\overline{s})\) denotes a literal with argument sequence \(\overline{s}\) where \(n\) is the arity of the predicate symbol of \(L\) and the length of \(\overline{s}\). Assuming the lengths of \(\overline{s}\) and \(\overline{t}\) are \(n\), \(\overline{s} \not\approx \overline{t}\) is shorthand notation for \(s_1 \not\approx t_1 \mathrel{\vee}\ldots \mathrel{\vee}s_n \not\approx t_n\).

The idea of the SCAN algorithm is to generate sufficiently many logical consequences of \(N\) and eventually only keeping those non-redundant clauses in which no symbols from \(\overline{X}\) occur. This is realised by a saturation process which interleaves (i) inference steps, (ii) normalisation and redundancy elimination steps, and (iii) purifying deletion steps. These are based by the inference system \(\mathit{\mathsf{C}}\) defined by the rules given Tables ¿tbl:table95scan95inference95rules? and ¿tbl:table95cresol95calculus?.

Table ¿tbl:table95scan95inference95rules? specifies the inference rules of SCAN performing all inferences upon \(\overline{X}\)-literals. The \(\mathit{\mathsf{C}}\)-resolution and \(\mathit{\mathsf{C}}\)-factoring rules are variations of the standard resolution and factoring rules in which constraints are used instead of unification. It is convenient to think of a \(\mathit{\mathsf{C}}\)-resolvent as a conditional formula saying, if each of the corresponding terms are equal (i.e., \(s_i \mathrel{\approx}t_i\)), then \(C\mathrel{\vee}D\) holds. Similarly, for \(\mathit{\mathsf{C}}\)-factoring.

We assume that clauses are eagerly normalised using:

Constraint elimination:

\(C\lor s\not\approx t\;\Rightarrow_{\mathrm{CEl}} \;C\sigma\)
if \(\sigma\) is a most general unifier of \(s\approx t\), i.e., \(s\sigma\approx t\sigma\) and \(\sigma\) is the most general substitution with this property.

The constraint elimination rule is useful for simplifying clauses, reducing their size and making them more digestable by removing as many constraints as possible, because otherwise clauses grow in width very rapidly. Eager constraint elimination improves the performance and success rate because other simplification possibilities such as those in Table ¿tbl:table95simplification95rules? can be recognised and applied more efficiently during the saturation process [1], [29]. Another purpose of constraint elimination is that it performs reflexivity resolution required for equational reasoning in the presence of inequality literals. Due to the absence of positive equational literals no further rules are needed for equality inference. In addition, the characterisation of the search space for the clausal form of the ordered fragment in the next section is easier if it is assumed that clauses contain only constraints between distinct constants.

The \(\mathit{\mathsf{C}}\)-resolution system can be freely enhanced by any equivalence preserving redundancy elimination rules to improve efficiency while preserving correctness. Without redundancy elimination the success rates are in general lower. Table ¿tbl:table95simplification95rules? lists some common redundancy elimination rules which are highly effective in saturation-based provers.

The purified clause deletion rule deletes a clause with a designated \(X\)-literal if no inference upon this literal produces clauses not already implied by other clauses in the current set.

There are two extended purity deletion rules: The positive version deletes all clauses containing \(X\), if these clauses all contain \(X\) positively (i.e., unnegated, with positive polarity). The intuition is that then instantiating \(X\) with \(\top\) makes these clauses true. Dually, if all clauses containing \(X\) contain \(X\) negatively, then these clauses can be made true by substituting \(\bot\) for \(X\). (Note that standard purity deletion is an instance of extended purity deletion.)

Let \(N\) be the input clause set and suppose the aim is to eliminate the variables \(\overline{X}\). The idea of the derivation process in SCAN is the following: First, processing of the input clauses is done, which may include \(\mathit{\mathsf{C}}\)-factoring with eager constraint elimination, subsumption deletion, tautology deletion and creation of appropriate data structures.

Then, the main derivation loop is performed until all symbols in \(\overline{X}\) have been eliminated. Each iteration consists of the following steps:

(a) A clause \(K\) and an \(X\)-literal \(L\) in the clause is picked for purification: All \(\mathit{\mathsf{C}}\)-inferences are performed with \(K\) upon \(L\) and the remaining clauses as well as all obtained clauses in this sub-loop. Each inferred clause is checked if it is subsumed by a present clause or subsumes some present clauses. If no more \(\mathit{\mathsf{C}}\)-inferences are possible with \(K\) upon \(L\) then \(K\) is purified and is deleted.

(b) Extended purity deletion (positive and negative) is applied.

(c) Other redundancy elimination steps may be performed at any time.

SCAN finally attempts to express the obtained clause set \(M\) as a first-order formula by reversing Skolemisation.

There are various choices that can be made in the algorithm and different derivations are obtained depending on the choices. SCAN may or may not terminate. If SCAN terminates normally then the remaining clauses do not contain any of the predicate variables in \(\overline{X}\).

The choices also influence if back-translation to a first-order formula is possible. The problem is that derived clauses can contain different complex Skolem terms requiring Henkin quantifiers which cannot be captured by a linear sequence of quantifiers [1].

As already said, the SCAN algorithm is not guaranteed to terminate; in fact, in general, there cannot be an algorithm that necessarily succeeds, even if a finite solution exists, since the SOQE problem is not even semi-decidable.

5 The Prefix Stable Clausal Class \(BPL_{fcp}^{\not\approx}\)↩︎

The search space of SCAN on the clausal form of ordered sentences can be characterized as an adaptation of the clausal class \(BPL\) in which constants occur in fixed argument positions in atoms and clauses possibly include negative constraints, i.e., the inequality literals. We name the class \(BPL_{fcp}^{\not\approx}\)(basic path clauses with inequality constraints and fixed constant positions).

Formally, the signature of \(BPL_{fcp}^{\not\approx}\) is any signature \(\Sigma\) defined in Section 2 also including equality \(\mathrel{\approx}\). We assume that each constant \(a\) is associated with an index \(i\) in \(\{1, \ldots, n \}\), where \(n\) is the maximal arity of any predicate symbol in the given ordered sentence.

\(BPL_{fcp}^{\not\approx}\) is the class of all \(\exists^*\forall^*\) clauses in which additionally the following conditions all hold. For any two non-constraint literals \((\neg)P(\underline u)\) and \((\neg)Q(\underline v)\) in \(C\), both the following hold:

L1

if \(u_i\) and \(v_j\) are the same variable then \(i=j\), and

L2

each pair \(u_k\) and \(v_k\) preceding \(u_i\) and \(v_i\) are identical, unless \(u_k\) and \(v_k\) are both (possibly distinct) constants.

L3

For any constant \(a\), if the index of \(a\) is \(i\) (\(1\leq i \leq n\)) then \(a\) occurs only at argument position \(i\) in non-constraint literals of any clause.

L4

In each constraint \(u \mathrel{\not\approx}v\) of clause \(C\), \(u\) and \(v\) are position compatible, i.e., if \(u\) is a variable occuring at argument position \(i\) in a non-constraint literal of \(C\) or \(u\) is a constant with index \(i\) then either \(v\) is a variable occurring at argument position \(i\) in a non-constraint literal of \(C\), \(v\) is singular (does not occur anywhere else in \(C\)) or \(v\) is a constant with index \(i\). We say that the position associated with \(u \mathrel{\not\approx}v\) is \(i\).

L1 and L2 say that clauses are prefix-stable for variables when constants are disregarded. L3* says that argument positions of constants are unique. L4 says that constraints are position compatible.* Observe that L3 holds for both sets of clauses in \(BPL_{fcp}^{\not\approx}\) and individual clauses, whereas L1, L2 and L4 are clause specific. When we say a set of sequences of variables and constants is prefix stable (for variables) modulo disregard for constants we mean that the set satisfies L1 and L2.

For example, the following clauses satisfy L1–L4 \[\begin{align} Q(a,y) \mathrel{\vee}P(a,y), \quad Q(a,y) \mathrel{\vee}P(b,y), \quad Q(a,y) \mathrel{\vee}P(b,y) \mathrel{\vee}a\mathrel{\not\approx}b \mathrel{\vee}c\mathrel{\not\approx}d \end{align}\] while \(Q(a,y) \mathrel{\vee}P(x,y)\) does not, since L2 does not hold.

Suppose \(\varphi\) is a sentence in the ordered fragment (without equality). Let \(N\) be a clausal form of the constant Skolemisation of \(\varphi\). It is not difficult to see that clauses in \(N\) contain only variables and constants, are prefix-stable as defined at the beginning of Section 2 and the uniqueness of argument position of constants (L3) is satisfied. Thus \(N\) satisfies both the more general property of prefix stability for variables (T1 and T2) and prefix stability for variables modulo disregard for constants (L1 and L2). Since \(N\) is free of equality and it is during the constraint resolution or constraint factoring steps that constraints (inequality literals) are introduced, condition L4 vacuously holds. Therefore:

One might have expected that the inference rules of the system \(\mathit{\mathsf{C}}\) preserve prefix-stability for variables, but the following example shows the constraint resolvent of two \(BPL\)-clauses after normalisation may not be prefix-stable for variables, where the aim is to eliminate \(X\). \[\begin{align} 1.\;& \hphantom{\neg} X(a,y) \mathrel{\vee}P(a,y) \\ 2.\;& \neg X(b,z) \mathrel{\vee}Q(b,z)\\ \text{\sout{3.}}\;& \hphantom{\neg} P(a,y) \mathrel{\vee}Q(b,z) \mathrel{\vee}a \not\approx b \mathrel{\vee}y \not\approx z && \text{(1,2)}\\ 3'.\;& \hphantom{\neg} P(a,y) \mathrel{\vee}Q(b,y) \mathrel{\vee}a \not\approx b && \text{(norm 3)} \end{align}\] Clause \(3'\). does not satisfy T2 and is therefore not prefix stable for variables. We note however all clauses satisfy L1–L4. The reason is that, in the inference rules of \(\mathit{\mathsf{C}}\), unification has been replaced by constraints and inferences are performed even when the literals resolved or factored upon are not unifiable. Unification is sufficient for refutation finding (and uniform interpolation where the target language does not include equality) but not for SOQE where we are interested in solutions expressed in first-order logic with equality. The SOQE solution of eliminating \(X\) from clauses 1. and 2.is clause \(3'\).which says that if \(a \approx b \mathrel{\rightarrow}(P(a,y) \mathrel{\vee}Q(b,y))\), whereas the uniform interpolant in first-order logic without equality is \(\top\).

To prove this theorem, we need to show that each inference step in SCAN preserves prefix-stability for variables when constants are disregarded (L1 and L2), constants do not change positions in non-constraint literals (L3) and are position compatible in constraints (L4). We consider the inference rules constraint resolution, constraint factoring and eager constraint elimination in turn.

5.0.0.0.1 Constraint resolution

Let \(C = X(\overline{u}) \mathrel{\vee}C' \mathrel{\vee}C'^{\not\approx}\) and \(D = \neg X(\overline{v}) \mathrel{\vee}D' \mathrel{\vee}D'^{\not\approx}\) be variable disjoint copies of clauses in \(BPL_{fcp}^{\not\approx}\) and assume they are both normalised, i.e., contraint elimination is not applicable. Suppose constraint resolution is applicable to \(C\) and \(D\). This means \(\overline{u}\) and \(\overline{v}\) have the same length. Assume \(C'^{\not\approx}\) and \(D'^{\not\approx}\) are the respective subclauses containing the constraints of \(C\) and \(D\).

A resolvent of \(C\) and \(D\) is \[C' \mathrel{\vee}C'^{\not\approx} \mathrel{\vee}D' \mathrel{\vee}D'^{\not\approx} \mathrel{\vee} \overline{u} \not\approx \overline{v}.\] The part \(C' \mathrel{\vee}C'^{\not\approx} \mathrel{\vee}D' \mathrel{\vee}D'^{\not\approx}\) is the disjoint union of subclauses of \(C\) and \(D\), which implies L1, L2, L3 and L4 are preserved. The positions of the terms in each of the new constraints \(u_i \not\approx v_i\) are their respective argument positions in the literals resolved upon, which are the same. We can conclude the resolvent satisfies L4 and belongs to \(BPL_{fcp}^{\not\approx}\).

5.0.0.0.2 Constraint factoring

Similarly, let \(C = (\neg)X(\overline{u}) \mathrel{\vee}(\neg)X(\overline{v}) \mathrel{\vee}C'\) be any normalised clause in \(BPL_{fcp}^{\not\approx}\). Suppose constraint factoring is applicable and produces factor \[(\neg)X(\overline{u}) \mathrel{\vee}C' \mathrel{\vee}\overline{u} \not\approx \overline{v}.\] The part \(X(\overline{u}) \mathrel{\vee}C'\) is unchanged and satisfies L1–L4. We note that \(u_i\) and \(v_i\) of each constraint \(u_i \mathrel{\not\approx}v_i\) occur in the same argument position in the literals \(X(\overline{u})\) and \(X(\overline{v})\). This implies L4 holds and the factor is a \(BPL_{fcp}^{\not\approx}\)-clause.

5.0.0.0.3 Constraint elimination

Constraint elimination applies to a clause \(C \mathrel{\vee}\overline{u} \mathrel{\not\approx}\overline{v}\), where \(C\) is normalised and therefore does not contain any constraints involving variables. Suppose \(\overline{u} \mathrel{\not\approx}\overline{v}\) is the disjunction \[\label{constraint95disjunction} u_1 \not\approx v_1 \mathrel{\vee}\ldots \mathrel{\vee}u_n \not\approx v_n.\tag{1}\] Because \(\overline{u}\) and \(\overline{v}\) are variable disjoint and linear (since they satisfy L1 and L2), the bindings \(\sigma\) produced for unifiable pairs \(u_k \not\approx v_k\), i.e., \(\sigma = \{ u_k \mapsto v_k \}\) or \(\sigma = \{ v_k \mapsto u_k \}\), are independent in the following sense: No variable changed in a binding occurs on the right of another binding of the bindings produced during \(\Rightarrow_{\mathrm{CEl}}^*\), i.e., exhaustive application of constraint elimination to the clause. This implies that the bindings and individual contraint elimination steps can be applied in any order to the subclause (1 ) leading to the same normalised clause. Without loss of generality we assume eager constraint elimination is performed in the order from left to right in (1 ).

Observe that constraints of the form \(a \mathrel{\not\approx}a\) or \(x \mathrel{\not\approx}x\) (the latter is a possibility in a factor) are simply dropped during constraint elimination (in this case the binding is \(\sigma=\emptyset\)). \(u_k \not\approx v_k\) is not unifiable when the terms are distinct constants and \(u_k\) and \(v_k\) are left untouched and the constraint remains in the result of applying \(\Rightarrow_{\mathrm{CEl}}^*\).

The following lemma shows that a binding \(\sigma\) during constraint elimination from left to right preserves L1 and L2. It also trivially preserves L3 and L4.

Let \(A\) be a set of argument sequences in the signature of \(BPL_{fcp}^{\not\approx}\). We say two argument sequences \(s\) and \(t\) (of equal length) are \(k\)-equal if \(s\) and \(t\) are equal except possibly at position \(k\), that is, for every position \(i \not= k\), \(s|_i = t|_i\).

Recall, the prefix of \(u_i\) in \(\overline{u}\) is the empty sequence \(\varepsilon\) if \(i = 1\), and \((u_1, \ldots, u_{i-1})\), otherwise. We define the variable prefix of \(u_i\) in \(\overline{u}\) as the sequence \((u_{j_1}, \ldots, u_{j_{k-1}})\) of all variables in \(\overline{u}\), where \(j_1 < \ldots < j_{k-1} < i\) and all the other terms in the prefix of \(u_i\) are constants. If none of the \(u_1, \ldots, u_{i-1}\) are variables the variable prefix is the empty sequence \(\varepsilon\).

To prove this lemma, we consider two arbitrary sequences in \(A\sigma\). They are of the form \(s \sigma\) and \(t \sigma\) with \(s\) and \(t\) some sequences in \(A\). For \(s\) and \(t\) conditions L1 and L2 hold, and we want to show they also hold for the sequences \(s \sigma\) and \(t \sigma\).

We continue the proof of Lemma 5. The lemma just proved is true for \(t \sigma\) and \(t\), as well. If neither \(s\) nor \(t\) contain the variable \(u_{j_k}\) then the substitution \(\sigma\) does not affect \(s\) and \(t\). Then \(s \sigma = s\) and \(t \sigma = t\). In this case \(s \sigma\) and \(t \sigma\) trivially satisfy L1 and L2 (since \(s\) and \(t\) do).

Without loss of generality let us assume that \(s|_{j_k} = u_{j_k}\). Then \(s|_{j_k} \sigma = v_{j_k}\). We distinguish two cases:

(i) \(t|_{j_k} \not= u_{j_k}\) and \(t|_{j_k} \not= v_{j_k}\). \(\sigma\) leaves \(t\) unchanged so that \(t \sigma = t\). Suppose \(s \sigma|_i = t \sigma|_j\) is a variable. Then \(s \sigma|_i = t \sigma|_j = t|_j\). Also, \(j \not= {j_k}\) and \(i \not= {j_k}\), since otherwise \(t|_j = v_{j_k}\) which contradicts our assumption. This implies \(s|_i = s \sigma|_i = t \sigma|_j = t|_j\). By L1 which holds for \(s\) and \(t\) we get that \(i = j\). By L2 for any \(l < i=j\) we have \(s|_l = t|_l\) unless both \(s|_l\) and \(t|_l\) are (possibly distinct) constants. Suppose \(s|_l\) and \(t|_l\) are not both constants. Then, \(i = j < {j_k}\) since otherwise, if \(i = j = {j_k}\) then \(s|_i = u_{j_k} \not= t|_i\) which is a contradiction, or if \(i = j > {j_k}\) then since \(s|_{j_k} \not= t|_{j_k}\) by assumption, \(s\) and \(t\) contradict L1 and L2. Consequently by the Lemma \(s \sigma|_l = s|_l = t|_l = t \sigma|_l\). Therefore, conditions L1 and L2 are true for case (i).

(ii) \(t|_{j_k} = u_{j_k}\) or \(t|_{j_k} = v_{j_k}\). Then \(t \sigma|_{j_k} = v_{j_k} = s \sigma|_{j_k}\). Suppose \(s \sigma|_i = t \sigma|_j\) is a variable.

 a.  If $i = {j_k}$ then $s \sigma|_i = v_{j_k} = t \sigma|_j$.
     Then, either $t|_j = u_{j_k}$ or $t|_j = v_{j_k}$. In either
     case, it follows that $j = {j_k}$ and hence $i=j$.

 b.  If $j = {j_k}$ then by a similar argument $i= j$.

 c.  If $i \not= {j_k}$ and $j \not= {j_k}$ then the Lemma implies
     $s \sigma|_i =
     s|_i$ and $t \sigma|_j = t|_j$. Since
     $s \sigma|_i = t \sigma|_j$ we have $s|_i = t|_j$ and it
     follows by *L1* that $i = j$.

 Therefore, $s \sigma$ and $t \sigma$ satisfy *L1*.

 Let $l < i=j$ be arbitrary and suppose $s|_l$ and $t|_l$ are
 variables (by *L2* it cannot be that one is a variable and the
 other is a constant). By *L2* we have that $s|_l = t|_l$.

 a.  Consider the case that $l \not= {j_k}$. By the Lemma
     $s \sigma|_l = s|_l$ and $t \sigma|_l = t|_l$. Since $s|_l$ and
     $t|_l$ coincide, we conclude $s \sigma|_l =
     t \sigma|_l$. (Note that if $t|_{j_k} = v_{j_k}$ then
     $s|_{j_k} = u_{j_k} \not= t|_{j_k}$ and consequently
     $i=j < {j_k}$.)

 b.  For $l = {j_k}$: $s \sigma|_l = v_{j_k} = t \sigma|_l$ by
     assumption.

This completes the proof of Lemma 5.

We can conclude that the normalisation obtained by eager constraint elimination of any resolvent or factor in \(\mathit{\mathsf{C}}\) preserves L1–L4 and belongs to \(BPL_{fcp}^{\not\approx}\).

Trivially, the class \(BPL_{fcp}^{\not\approx}\) is closed under clause deletion rules, including purified clause deletion, extended purity deletion, tautology deletion and subsumption deletion. To see that the condensation of a \(BPL_{fcp}^{\not\approx}\)-clause is a \(BPL_{fcp}^{\not\approx}\)-clause notice that the condensation of a clause is a factor that subsumes it, and use Lemma 5 to show the following:

Let \(A\) be a set of argument sequences in the language of \(BPL_{fcp}^{\not\approx}\)-clause and assume \(\sigma\) be an idempotent unifier of two sequences \(\overline{u}\) and \(\overline{v}\) in \(A\). Then, \(A\sigma\) satisfies properties L1 and L2 if \(A\) does.

This allows us to show standard factoring preserves properties L1 and L2. Preservation of L3 and L4 is not difficult to see.

This completes the proof of Theorem 10.

We now argue that SCAN is a decision procedure for eliminating predicate variables \(\overline{X}\) from any finite set \(N\) of \(BPL_{fcp}^{\not\approx}\) clauses. This requires us to show that any \(\mathit{\mathsf{C}}\)-saturated set \(N^\infty\) of \(N\) is finite, which follows if the depth and width of any derived clauses are finitely bounded.

Trivially, the clause (term) depth is bounded as \(BPL_{fcp}^{\not\approx}\) clauses do not contain complex terms, only variables and constants.

The existence of a finite bound of the size of derived clauses, i.e., the number of literals in derived clauses does not grow indefinitely, is tied with the maximum number of variables which can occur in any variable indecomposable (sub)clause.

Let \(A\) be a set of sequences (or a clause) in \(BPL_{fcp}^{\not\approx}\). The variable partition of \(A\) is the finest partition of \(A\) into disjoint subsets of sequences (subclauses) which do not share common variables. The blocks in the variable partition are said to be variable indecomposable or split. It suffices to show there is a bound on the number of variables occurring in any variable indecomposable and condensed \(A\). Because if there is, then there can only be a limited number of non-variant variable indecomposable subsets in \(BPL_{fcp}^{\not\approx}\). In particular, there can only be a limited number of non-variant variable indecomposable subsets of any condensed \(A\). This implies that any condensed \(A\) in \(BPL_{fcp}^{\not\approx}\) is bounded in size. Consequently, \(BPL_{fcp}^{\not\approx}\) is bounded in size.

Now, w.l.o.g.we can assume that all clauses are normalised and all constraints are between constants. We can further limit our attention to the non-constraint literals in clauses. It is not difficult to see that the maximum number of variables occurring in any variable indecomposable \(BPL_{fcp}^{\not\approx}\)-clause is the same as the variable bound in any \(BPL\)-clause (or any \(BPL\)-clause satisfying the fixed constant position condition). Variable indecomposable normalised \(BPL_{fcp}^{\not\approx}\)-clauses have in general more literals than \(BPL\)-clauses satisfying the fixed constant position condition, because of the presence of the constraints but also because of condition L2 which allows combinatorially many more literals in a clause involving the constants in the input set. Since there are only finitely many constants and because of the finite bound on variables the size of \(BPL_{fcp}^{\not\approx}\)-clauses is finitely bounded.

This implies that SCAN is SOQE-complete for \(BPL_{fcp}^{\not\approx}\)(and the clausal form of the ordered fragment resulting from constant Skolemisation).

6 Extracting Uniform Interpolants in Basic Path Logic↩︎

In this section we offer a construction of uniform interpolants (in equality-free first-order logic) using \(BPL_{fcp}^{\not\approx}\) clauses computed by SCAN. We have shown that, for any finite set of \(BPL_{fcp}^{\not\approx}\) clauses (and any finite list of predicate variables), SCAN always terminates with a finite set of \(BPL_{fcp}^{\not\approx}\) clauses, and thus we have a solution to SOQE in this case. However, since \(BPL_{fcp}^{\not\approx}\) clauses in general are not expressible in \(BPL\) and the ordered fragment, both of which are equality-free, some extra work is needed in order to extract uniform interpolants from \(BPL_{fcp}^{\not\approx}\) clauses.

As constraint elimination is applied eagerly, all inequalities occurring in the output set of clauses are between (distinct) constants, e.g. \(a\mathrel{\not\approx}b\). Fortunately, replacing these inequalities with \(\top\), or equivalently, deleting all clauses containing such inequalities does not cause a loss of logical consequences in equality-free first-order logic. The correctness of this deletion is discussed below. Again, we make use of the fact that models of equality-free formulas can be inflated.

In particular, this allows us to replace inequalities between (distinct) constants by \(\top\) in the \(BPL_{fcp}^{\not\approx}\) clauses returned by SCAN without any change to the logical consequences in \(BPL\) and the ordered fragment. Notice that replacing a disjunct in a clause by \(\top\) amounts to deleting the clause altogether. Moreover,

Therefore, at this stage, we have already shown that uniform interpolants in \(BPL\) can be extracted from the result of SCAN. Note that this result is a little finer than Theorem 4 because it establishes the uniform interpolation property within \(BPL\) clauses where constants have fixed positions.

The remaining problem is to extract uniform interpolants in the ordered fragment in this framework. We have seen in Section 3 that each ordered sentence can be transformed into a set of \(BPL\) clauses (with fixed constant positions) and such a transformation preserves logical consequences in the ordered fragment in both directions. Since \(BPL\) clauses contain no functional terms, it is always possible to unskolemise the output of SCAN (after deleting clauses with inequalities) and get an (equality-free) first-order sentence in the \(\exists^*\forall^*\)-fragment. The challenge we are facing here is that these sentences are in general not expressible in the ordered fragment. For example, let us start from the following ordered sentence as an input: \[\begin{gather} \forall x_1\forall x_2 \exists x_3((\neg X(x_1,x_2) \mathrel{\vee}P(x_1,x_2,x_3))\mathrel{\wedge}(\neg Y(x_1,x_2) \mathrel{\vee}Q(x_1,x_2,x_3))) \\ \mathrel{\wedge}\;\forall x_1 \exists x_2 X(x_1,x_2)\mathrel{\wedge}\;\forall x_1\exists x_2 Y(x_1,x_2). \end{gather}\] By constant Skolemisation and clausification, we have clauses 1–4 as below. \[\begin{align} 1.\;& \neg X(x,y) \mathrel{\vee}P(x,y,a)\\ 2.\;& \hphantom{\neg} X(x,b)\\ 3.\;& \neg Y(x,y) \mathrel{\vee}Q(x,y,a)\\ 4.\;& \hphantom{\neg} Y(x,c)\\ \text{\sout{5.}}\;& P(x,y,a) \mathrel{\vee}x \mathrel{\not\approx}x' \mathrel{\vee}y \mathrel{\not\approx}b && \text{(C-res, 1, 2)}\\ 5'.\;& P(x,b,a) && \text{(2 \times CEl)}\\ \text{\sout{6.}}\;& Q(x,y,a) \mathrel{\vee}x \mathrel{\not\approx}x' \mathrel{\vee}y \mathrel{\not\approx}c && \text{(C-res, 3, 4)}\\ 6'.\;& \hphantom{\neg} Q(x,c,a) && \text{(2 \times CEl)} \end{align}\] Applying rules as above, Clauses \(5'\) and \(6'\) remain, and we get the following first-order formula via the usual unskolemisation (i.e., each Skolem constant is eliminated by introducing an existential quantifier): \[\exists u \exists v \exists w \forall x (P(x,u,w) \mathrel{\wedge}Q(x,v,w)).\] However, it is not an ordered sentence, and we show below that it is not equivalent to any ordered sentence.

We say that a first-order sentence \(\phi\) is invariant under ordered bisimulations if, for any structures \(\mathfrak{A}\) and \(\mathfrak{B}\), the following implication holds: \[\mathfrak{A}\sim\mathfrak{B}\;\Longrightarrow\;\mathfrak{A}\models\phi\ \text{iff} \ \mathfrak{B}\models\phi.\] The following result is included in [12].

Let \(\phi :=\exists u \exists v \exists w \forall x (P(x,u,w) \mathrel{\wedge}Q(x,v,w))\). To show that this sentence is not equivalent to any sentence of the ordered fragment, we only need to show that it is not invariant under ordered bisimulations. Let \(P\) and \(Q\) be ternary and \(\mathfrak{A}\) the \(\{P,Q\}\)-structure (with domain \(A\)) such that: \[\begin{align} A&=\{a_1,a_2\}\\ P^{\mathfrak{A}}&=\{(a_1,a_1,a_1),(a_2,a_1,a_1)\}\\ Q^{\mathfrak{A}}&=\{(a_1,a_2,a_1),(a_2,a_2,a_1)\}. \end{align}\] We can easily verify that \(\mathfrak{A}\models\phi\). Now consider the structure \(\mathfrak{A}'\) over the same domain \(A\) such that: \[\begin{align} P^{\mathfrak{A}'}&=\{(a_1,a_1,a_1),(a_2,a_1,a_1)\}\\ Q^{\mathfrak{A}'}&=\{(a_1,a_2,a_2),(a_2,a_2,a_2)\}. \end{align}\] We observe that \(\mathfrak{A}'\nvDash\phi\). Let \(Z\subseteq \bigcup_{n\geq 0}(A^n\times A^n)\) be the relation that agrees with the identity relation on \(\bigcup_{n\geq 0}A^n\) except that, for any \(\bar{a}\in \bigcup_{n\geq 0}A^n\): \[\begin{align} &a_1a_2a_1\bar{a}Za_1a_2a_2\bar{a}\\ &a_2a_2a_1\bar{a}Za_2a_2a_2\bar{a}. \end{align}\] A routine check shows that \(Z\) is an ordered bisimulation between \(\mathfrak{A}\) and \(\mathfrak{A'}\) and, in addition, \(\varepsilon Z\varepsilon\). Thus, \(\mathfrak{A}\sim\mathfrak{A}'\), and \(\phi\) is not invariant under ordered bisimulations. By Theorem 14, \(\phi\) is not equivalent to any ordered sentence.

As SCAN tries to exhaust all consequences in first-order logic, it is not a surprise that it also produces formulas which fall beyond the expressivity of the ordered fragment. In order to compute uniform interpolants in the ordered fragment, we need to weaken the output set of clauses (so that it can be translated back to the ordered fragment) and meanwhile retain all of its consequences in the ordered fragment. At the time of writing, we do not know how this can be achieved.

7 Conclusion↩︎

In this paper, we have used the decidability result of unrefined resolution to show the uniform interpolation property of basic path logic. Also, we characterised the search space of the SCAN algorithm on \(BPL\) clauses with fixed constant positions, proving that SCAN is terminating and therefore SOQE is solvable in this case. For computing uniform interpolants of ordered sentences, we proposed constant Skolemisation, with which the clausification of ordered sentences is proved to be consequence-preserving in the fragment (not just satisfiability-preserving). However, although constraints in the output of SCAN can always be eliminated and the resulting (equality-free) set of clauses can be expressed by an (equality-free) \(\exists^*\forall^*\)-formula, we note that it is not generally expressible in the ordered fragment. For future research we would like to find a method for extracting uniform interpolants in the ordered fragment from \(BPL\) clauses.

We would like to thank the reviewers and audience of the CADE-30 Workshop in Honor of Christoph Weidenbach’s 60th Birthday hed in August 2025, and participants of Dagstuhl Seminar 26091 on “Revisiting the Foundations of Deduction in a New World” held in February 2026, where earlier versions of this work were presented.

Declarations↩︎

The research was not supported by grant funding.

The authors have no conflicts of interest to declare that are relevant to the content of this article.

References↩︎

---

1. On the side we remark, these observations do not extend to the \(\exists^*\forall^*\) clausal class which is NEXPTIME-complete, but with a range-restriction transformation hyper-resolution decides the \(\exists^*\forall^*\) clausal class [5].↩︎