2. Preliminaries

It is assumed that the reader has some familiarity with equational theorem proving (Bachmair and Ganzinger, Reference Bachmair and Ganzinger1994; Nieuwenhuis and Rubio, Reference Nieuwenhuis and Rubio2001) and string rewriting systems (Book and Otto, Reference Book and Otto1993; Holt et al., Reference Holt, Eick and O’Brien2005; Kapur and Narendran, Reference Kapur and Narendran1985). The notion of conditional

equations and Horn clauses are discussed in Dershowitz (Reference Dershowitz, Albert, Monien and Artalejo1991).

An alphabet $\Sigma$ is a finite set of symbols (or letters). The set of all strings of symbols over $\Sigma$ is denoted $\Sigma^*$ with the empty string $\lambda$ .

If $s\in \Sigma^*$ , then the length of s, denoted $|s|$ , is defined as follows: $|\lambda|:=0$ , $|a|:=1$ for each $a\in \Sigma$ , and $|sa|:=|s|+1$ for $s\in \Sigma^*$ and $a\in\Sigma$ .

A multiset is an unordered collection with possible duplicate elements. We denote by M(x) the number of occurrences of an object x in a multiset M.

An equation is an expression $s\approx t$ , where s and t are strings, that is, $s,t \in \Sigma^*$ . A literal is either a positive equation L, called a positive literal, or a negative equation $\neg L$ , called a negative literal. We also write a negative literal $\neg (s\approx t)$ as $s\not\approx t$ . We identify a positive literal $s\approx t$ with the multiset $\{\{s\},\{t\}\}$ and a negative literal $s\not\approx t$ with the multiset $\{\{s,t\}\}$ . A clause (over $\Sigma^*$ ) is a finite multiset of literals, written as a disjunction of literals $\neg A_1\vee \cdots \vee \neg A_m \vee B_1\vee \cdots \vee B_n$ or as an implication $\Gamma \rightarrow \Delta$ , where $\Gamma=A_1 \wedge \cdots \wedge A_m$ and $\Delta=B_1\vee \cdots \vee B_n$ . We say that $\Gamma$ is the antecedent and $\Delta$ is the succedent of clause $\Gamma \rightarrow \Delta$ . A Horn clause is a clause with at most one positive literal. The empty clause, denoted $\square$ , is the clause containing no literals.

A conditional equation is a clause of the form $(s_1 \approx t_1 \wedge \cdots \wedge s_n \approx t_n) \rightarrow l \approx r$ . If $n=0$ , a conditional equation is simply an equation. A conditional equation is naturally represented by a Horn clause. A conditional equational theory is a set of conditional equations.

Any ordering $\succ_S$ on a set S can be extended to an ordering $\succ_S^{mul}$ on finite multisets over S as follows: $M\succ_S^{mul} N$ if (i) $M\neq N$ and (ii) whenever $N(x) > M(x)$ then $M(y) > N(y)$ , for some y such that $y\succ_S x$ .

Given a multiset M and an ordering $\succ$ on M, we say that x is maximal (resp. strictly maximal) in M if there is no $y\in M$ (resp. $y \in M\setminus\{x\})$ with $y\succ x$ (resp. $y \succ x$ or $x=y$ ).

An ordering $>$ on $\Sigma^*$ is terminating if there is no infinite chain of strings $s > s_1 > s_2 > \cdots$ for any $s \in \Sigma^*$ . An ordering $>$ on $\Sigma^*$ is admissible if $u > v$ implies $xuy > xvy$ for all $u,v,x,y \in \Sigma^*$ . An ordering $>$ on $\Sigma^*$ is a reduction ordering if it is terminating and admissible.

The lexicographic ordering $\succ_{lex}$ induced by a total precedence ordering $\succ_{prec}$ on $\Sigma$ ranks strings of the same length in $\Sigma^*$ by comparing the letters in the first index position where two strings differ using $\succ_{prec}$ . For example, if $a=a_1a_2\cdots a_k$ and $b=b_1b_2\cdots b_k$ , and the first index position where a and b are differ is i, then $a \succ_{lex} b$ if and only if $a_i \succ_{prec} b_i$ .

The length-lexicographic ordering $\succ$ on $\Sigma^*$ is defined as follows: $s \succ t$ if and only if $|s|>|t|$ , or they have the same length and $s\succ_{lex} t$ for $s,t\in \Sigma^*$ . If $\Sigma$ and $\succ_{prec}$ are fixed, then it is easy to see that we can determine whether $s\succ t$ for two (finite) input strings $s\in \Sigma^*$ and $t\in \Sigma^*$ in O(n) time, where $n=|s|+|t|$ . The length-lexicographic ordering $\succ$ on $\Sigma^*$ is a reduction ordering. We also write $\succ$ for a multiset extension of $\succ$ if it is clear from context. In this paper, we assume that a total precedence $\succ_{prec}$ (simply written $\succ$ ) on $\Sigma$ is always given, unless otherwise stated.

A string rewriting system R (over $\Sigma^*$ ) is a subset of $\Sigma^* \times \Sigma^*$ . Let R be a string rewriting system over $\Sigma^*$ . Then, $u\rightarrow_R v$ if there exist $x, y \in \Sigma^*$ such that $u = xly$ and $v = xry$ and $l \rightarrow r \in R$ . By $\rightarrow_R^*$ (resp. $\overset{*}{\leftrightarrow_R}$ ), we denote the reflexive and transitive closure of R (resp. the reflexive, symmetric, and transitive closure of R). Note that the relation $\overset{*}{\leftrightarrow_R}$ is a congruence relation w.r.t. the concatenation of strings over $\Sigma^*$ , which is called the Thue congruence associated with R. $\rightarrow_R$ is confluent if for all $s,t,u\in \Sigma^*$ with $s\rightarrow_R^* t$ and $s\rightarrow_R^* u$ there exists some $w\in \Sigma^*$ such that $t \rightarrow_R^* w$ and $u \rightarrow_R^* w$ .

$\rightarrow_R$ is terminating if there is no infinite sequence of strings $s_i \in \Sigma^*$ with $s_0 \rightarrow_R s_1 \rightarrow_R \cdots$ .

A string rewriting system R (over $\Sigma^*$ ) is convergent if $\rightarrow_R$ is both confluent and terminating.

We say that $\approx$ has the monotonicity property over $\Sigma^*$ if $s\approx t$ implies $usv \approx utv$ for all $s,t,u,v\in\Sigma^*$ . Throughout this paper, it is assumed that $\approx$ has the monotonicity property over $\Sigma^*$ .

3. Superposition with Strings

3.1. Inference rules

The following inference rules for clauses over strings are parameterized by a selection function $\mathcal{S}$ and the length-lexicographic ordering $\succ$ , where $\mathcal{S}$ arbitrarily selects exactly one negative literal for each clause containing at least one negative literal (see Section 3.6 in Nieuwenhuis and Rubio (Reference Nieuwenhuis and Rubio2001) or Section 6 in Bachmair and Ganzinger (Reference Bachmair, Ganzinger, Bibel and Schmitt1998)). In this strategy, an inference involving a clause with a selected literal is performed before an inference from clauses without a selected literal for a theorem proving process. The intuition behind the (eager) selection of negative literals is that, roughly speaking, one may first prove the whole antecedent of each clause from other clauses. Then clauses with no selected literals are involved in the main deduction process. This strategy is particularly useful when we consider Horn completion in Section 6 and a decision procedure for the word problems associated with it. In the following, the symbol $\bowtie$ is used to denote either $\approx$ or $\not\approx$ .

\begin{align*}\textbf{Superposition: } \frac{C\vee u_1u_2 \approx s \qquad D\vee u_2u_3\approx t}{C\vee D\vee u_1t\approx su_3}\end{align*}

if (i) $u_2$ is not $\lambda$ , (ii) C contains no selected literal, (iii) D contains no selected literal, (iv) $u_1u_2 \succ s$ , and (v) $u_2u_3 \succ t$ .Footnote ²

\begin{align*}\textbf{Rewrite: }\frac{C\vee u_1u_2u_3 \bowtie s \qquad D\vee u_2\approx t}{C\vee D\vee u_1tu_3\bowtie s}\end{align*}

if (i) $u_1u_2u_3\bowtie s$ is selected for the left premise whenever $\bowtie$ is $\not\approx$ , (ii) C contains no selected literal whenever $\bowtie$ is $\approx$ , (iii) D contains no selected literal, and (iv) $u_2 \succ t$ .Footnote ³

\begin{align*}\textbf{Equality Resolution: }\frac{C\vee s\not\approx s}{C}\end{align*}

if $s\not\approx s$ is selected for the premise.

The following Paramodulation and Factoring inference rules are used for non-Horn clauses containing positive literals only (cf. Equality Factoring (Bachmair and Ganzinger, Reference Bachmair and Ganzinger1994; Nieuwenhuis and Rubio, Reference Nieuwenhuis and Rubio2001) and Merging Paramodulation rule (Bachmair and Ganzinger,

1994)).

\begin{align*}\textbf{Paramodulation: }\frac{C\vee s\approx u_1u_2 \qquad D\vee u_2u_3\approx t}{C\vee D \vee su_3\approx u_1t}\end{align*}

if (i) $u_2$ is not $\lambda$ , (ii) C contains no selected literal, (iii) C contains a positive literal, (iv) D contains no selected literal, (v) $s\succ u_1u_2$ , and (vi) $u_2u_3\succ t$ .

\begin{align*}\textbf{Factoring: }\frac{C\vee s\approx t \vee su\approx tu}{C\vee su\approx tu}\end{align*}

if C contains no selected literal.

In the proposed inference system, finding whether a string s occurs within a string t can be done in linear time in the size of s and t by using the existing string matching algorithms such as the Knuth–Morris–Pratt (KMP) algorithm (Cormen et al., Reference Cormen, Leiserson, Rivest and Stein2001). For example, the KMP algorithm can be used for finding $u_2$ in $u_1u_2u_3$ in the Rewrite rule and finding $u_2$ in $u_1u_2$ in the Superposition and Paramodulation rule.

In the remainder of this paper, we denote by $\mathfrak{S}$ the inference system consisting of the Superposition, Rewrite, Equality Resolution, Paramodulation, and the Factoring rule and denote by S a set of clauses over strings. Also, by the contraction rules we mean the following inference rules–Simplification, Subsumption, and Tautology.

\begin{align*}\textbf{Simplification: }\frac{S\cup\{C\vee l_1ll_2\bowtie v,\; l\approx r\}}{S\cup\{C\vee l_1rl_2\bowtie v,\; l\approx r\}}\end{align*}

if (i) $l_1ll_2\bowtie v$ is selected for $C\vee l_1ll_2\bowtie v$ whenever $\bowtie$ is $\not\approx$ , (ii) $l_1$ is not $\lambda$ , and (iii) $l \succ r$ .

In the following inference rule, we say that a clause C subsumes a clause $C^\prime$ if C is contained in C’, where C and C’ are viewed as the finite multisets.

\begin{align*}\textbf{Subsumption: }\frac{S\cup\{C, C^\prime\}}{S\cup\{C\}}\end{align*}

if $C\subseteq C'$ .

\begin{align*}\textbf{Tautology: }\frac{S\cup\{C \vee s\approx s\}}{S}\end{align*}

Example 1. Let $a \succ b \succ c\succ d \succ e$ and consider the following inconsistent set of clauses 1: $ad\approx b\vee ad\approx c$ , 2: $b \approx c$ , 3: $ad\approx e$ , and 4: $c\not\approx e$ . Now, we show how the empty clause is derived:

1. 5: $ad \approx c \vee ad \approx c$ (Paramodulation of 1 with 2)

2. 6: $ad \approx c$ (Factoring of 5)

3. 7: $c \approx e$ (Rewrite of 6 with 3)

4. 8: $e \not\approx e$ ( $c\not\approx e$ is selected for 4. Rewrite of 4 with 7)

5. 9: $\square$ ( $e \not\approx e$ is selected for 8. Equality Resolution on 8)

Note that there is no inference with the selected literal in 4 from the initial set of clauses 1, 2, 3, and 4. We produced clauses 5, 6, and 7 without using a selected literal. Once we have clause 7, there is an inference with the selected literal in 4.

Example 2. Let $a \succ b \succ c \succ d$ and consider the following inconsistent set of clauses 1: $aa \approx a \vee bd\not\approx a$ , 2: $cd \approx b$ , 3: $ad \approx c$ , 4: $bd\approx a$ , and 5: $dab\not\approx db$ . Now, we show how the empty clause is derived:

1. 6: $aa \approx a \vee a\not\approx a$ ( $bd\not\approx a$ is selected for 1. Rewrite of 1 with 4)

2. 7: $aa \approx a$ ( $a\not\approx a$ is selected for 6. Equality resolution on 6)

3. 8: $ac\approx ad$ (Superposition of 7 with 3)

4. 9: $add \approx ab$ (Superposition of 8 with 2)

5. 10: $ab \approx cd$ (Rewrite of 9 with 3)

6. 11: $dcd\not\approx db$ ( $dab\not\approx db$ is selected for 5. Rewrite of 5 with 10)

7. 12: $db \not\approx db$ ( $dcd\not\approx db$ is selected for 11. Rewrite of 11 with 2)

8. 13: $\square$ ( $db \not\approx db$ is selected for 12. Equality Resolution on 12)

3.2. Lifting properties

Recall that $\Sigma^*$ is the set of all strings over $\Sigma$ with the empty string $\lambda$ . We let $T(\Sigma\cup \{\bot\})$ be the set of all first-order ground terms over $\Sigma\cup \{\bot\}$ , where each letter from $\Sigma$ is interpreted as a unary function symbol and $\bot$ is the only constant symbol. (The constant symbol $\bot$ does not have a special meaning (e.g., “false”) in this paper.) We remove parentheses for notational convenience for each term in $T(\Sigma\cup \{\bot\})$ . Since $\bot$ is the only constant symbol, we see that $\bot$ occurs only once at the end of each term in $T(\Sigma\cup \{\bot\})$ . We may view each term in $T(\Sigma\cup \{\bot\})$ as a string ending with $\bot$ . Now, the definitions used in Section 2 can be carried over to the case when $\Sigma^*$ is replaced by $T(\Sigma\cup \{\bot\})$ . In the remainder of this paper, we use the string notation for terms in $T(\Sigma\cup \{\bot\})$ unless otherwise stated.

Let $s\approx t$ be an equation over $\Sigma^*$ . Then, we can associate $s\approx t$ with the equation $s(x)\approx t(x)$ , where $s(x)\approx t(x)$ represents the set of all its ground instances over $T(\Sigma\cup \{\bot\})$ . (Here, $\lambda(x)$ and $\lambda\bot$ correspond to x and $\bot$ , respectively.) First, $s\approx t$ over $\Sigma^*$ corresponds to $s\bot \approx t\bot$ over $T(\Sigma\cup \{\bot\})$ . Now, using the monotonicity property, if we concatenate string u to both sides of $s\approx t$ over $\Sigma^*$ , then we have $su \approx tu$ , which corresponds to $su\bot\approx tu\bot$ .

There is a similar approach in string rewriting systems. If S is a string rewriting system over $\Sigma^*$ , then it is known that we can associate term rewriting system $R_S$ with S in such a way that $R_S:=\{l(x)\rightarrow r(x)\,|\,l\rightarrow r \in S\}$ (Book and Otto, Reference Book and Otto1993), where x is a variable and each letter from $\Sigma$ is interpreted as a unary function symbol. We may rename variables (by standardizing variables apart) whenever necessary. This approach is particularly useful when we consider critical pairs between the rules in a string rewriting system. For example, if there are two rules $aa\rightarrow c$ and $ab\rightarrow d$ in S, then we have $cb \leftarrow aab\rightarrow ad$ , where ${<}cb, ad{>}$ (or ${<}ad, cb{>}$ ) is a critical pair formed from these two rules. This critical pair can also be found if we associate $aa\rightarrow c\in S$ with $a(a(x))\rightarrow c(x) \in R_S$ and $ab\rightarrow d\in S$ with $a(b(x))\rightarrow d(x) \in R_S$ . First, we rename the rule $a(b(x))\rightarrow d(x) \in R_S$ into $a(b(y))\rightarrow d(y)$ . Then by mapping x to b(z) and y to z, we have $c(b(z))\leftarrow a(a(b(z)))\rightarrow a(d(z))$ , where ${<}c(b(z)), a(d(z)){>}$ is a critical pair formed from these two rules. This critical pair can be associated with the critical pair ${<}cb, ad{>}$ formed from $aa\rightarrow c$ in S and $ab\rightarrow d$ in S.

However, if $s\not\approx t$ is a negative literal over strings, then we cannot simply associate $s\not\approx t$ with the negative literal $s(x)\not\approx t(x)$ over first-order terms. Suppose to the contrary that we associate $s\not\approx t$ with $s(x)\not\approx t(x)$ . Then $s\not\approx t$ implies $su\not\approx tu$ for a nonempty string u because we can substitute u(y) for x in $s(x)\not\approx t(x)$ , and $su\not\approx tu$ can also be associated with $s(u(y))\not\approx t(u(y))$ . Using the contrapositive argument, this means that $su\approx tu$ implies $s\approx t$ for the nonempty string u. Recall that we do not assume the cancelation property of equations over strings in this paper.Footnote ⁴ Instead, we simply associate $s\not\approx t$ with $s\bot\not\approx t\bot$ . The following lemma is based on the above observations. We denote by $T(\Sigma\cup \{\bot\}, X)$ the set of first-order terms built on $\Sigma\cup\{\bot\}$ and a denumerable set of variables X, where each symbol from $\Sigma$ is interpreted as a unary function symbol and $\bot$ is the only constant symbol.

Lemma 3. Let $C:=s_1\approx t_1\vee\cdots\vee s_m \approx t_m \vee u_1\not\approx v_1 \vee\cdots \vee u_n \not\approx v_n$ be a clause over $\Sigma^*$ and P be the set of all clauses that follow from C using the monotonicity property. Let Q be the set of all ground instances of the clause $s_1(x_1)\approx t_1(x_1) \vee \cdots \vee s_m(x_m)\approx t_m(x_m) \vee u_1\bot\not\approx v_1\bot \vee \cdots \vee u_n\bot\not\approx v_n\bot$ over $T(\Sigma\cup \{\bot\}, X)$ , where $x_1,\ldots, x_m$ are distinct variables in X and each letter from $\Sigma$ is interpreted as a unary function symbol. Then there is a one-to-one correspondence between P and Q.

Proof. For each element D of P, D has the form $D:=s_1w_1\approx t_1w_1\vee\cdots\vee s_mw_m \approx t_mw_m \vee u_1\not\approx v_1 \vee\cdots \vee u_n \not\approx v_n$ for some $w_1,\ldots, w_m \in \Sigma^*$ . (If $w_i=\lambda$ for all $1\leq i \leq m$ , then D is simply C.) Now, we map each element D of P to D’ in Q, where $D':=s_1w_1\bot\approx t_1w_1\bot \vee\cdots\vee s_mw_m\bot\approx t_mw_m\bot \vee u_1\bot\not\approx v_1\bot \vee\cdots \vee u_n\bot \not\approx v_n\bot$ . Since $\bot$ is the only constant symbol in $\Sigma\cup \{\bot\}$ , it is easy to see that this mapping is well defined and bijective.

Definition 4.

1. (i) We say that every term in $T(\Sigma\cup \{\bot\})$ is a g-term. (Recall that we remove parentheses for notational convenience.)

2. (ii) Let $s\approx t$ (resp. $s\rightarrow t$ ) be an equation (resp. a rule) over $\Sigma^*$ . We say that $su\bot\approx tu\bot$ (resp. $su\bot\rightarrow tu\bot$ ) for some string u is a g-equation (resp. a g-rule) of $s\approx t$ (resp. $s\rightarrow t$ ).

3. (iii) Let $s\not\approx t$ be a negative literal over $\Sigma^*$ . We say that $s\bot\not\approx t\bot$ is a (negative) g-literal of $s\not\approx t$ .

4. (iv) Let $C:=s_1\approx t_1\vee\cdots\vee s_m\approx t_m \vee u_1\not\approx v_1 \vee \cdots\vee u_n\not\approx v_n$ be a clause over $\Sigma^*$ . We say that $s_1w_1\bot\approx t_1w_1\bot\vee\cdots\vee s_mw_m\bot\approx t_mw_m\bot \vee u_1\bot\not\approx v_1\bot \vee \cdots\vee u_n\bot\not\approx v_n\bot$ for some strings $w_1,\ldots,w_m$ is a g-clause of clause C. Here, each $w_k\bot \in T(\Sigma\cup \{\bot\})$ for nonempty string $w_k$ in the g-clause is said to be a substitution part of C.

5. (v) Let $\pi$ be an inference (w.r.t. $\mathfrak{S}$ ) with premises $C_1,\ldots, C_k$ and conclusion D. Then a g-instance of $\pi$ is an inference (w.r.t. $\mathfrak{S}$ ) with premises $C_1',\ldots, C_k'$ and conclusion D’, where $C_1',\ldots, C_k'$ and D’ are g-clauses of $C_1,\ldots, C_k$ and D, respectively.

Since each term in $T(\Sigma\cup \{\bot\})$ is viewed as a string, we may consider inferences between g-clauses using $\mathfrak{S}$ . Note that concatenating a (nonempty) string at the end of a g-term is not allowed for any g-term over $T(\Sigma\cup \{\bot\})$ . For example, $abc\bot d$ is not a g-term, and $a\bot \not\approx b\bot \vee abc\bot d \approx def\bot d$ is not a g-clause. We emphasize that we are only concerned with inferences between (legitimate) g-clauses here.

We may also use the length-lexicographic ordering $\succ_g$ on g-terms. Given a total precedence ordering on $\Sigma\cup \{\bot\}$ for which $\bot$ is minimal, it can be easily verified that $\succ_g$ is a total reduction ordering on $T(\Sigma\cup \{\bot\})$ . We simply denote the multiset extension $\succ_g^{mul}$ of $\succ_g$ as $\succ_g$ for notational convenience.Footnote ⁵ We denote ambiguously all orderings on g-terms, g-equations, and g-clauses over $T(\Sigma\cup \{\bot\})$ by $\succ_g$ . Now, we consider the lifting of inferences of $\mathfrak{S}$ between g-clauses over $T(\Sigma\cup \{\bot\})$ to inferences of $\mathfrak{S}$ between clauses over $\Sigma^*$ . Let $C_1,\ldots, C_n$ be clauses over $\Sigma^*$ and let

\begin{align*}\frac{C_1'\ldots C_n'}{C'}\end{align*}

be an inference between their g-clauses, where $C_i'$ is a g-clause of $C_i$ for all $1\leq i \leq n$ . We say that this inference between g-clauses can be lifted if there is an inference

\begin{align*}\frac{C_1\ldots C_n}{C}\end{align*}

such that C’ is a g-clause of C. In what follows, we assume that a g-literal $L'_i$ in $C'_i$ is selected in the same way as $L_i$ in $C_i$ , where $L_i$ is a negative literal in $C_i$ and $L'_i$ is a g-literal of $L_i$ .

Lifting of an inference between g-clauses is possible if it does not correspond to a g-instance of an inference (w.r.t. $\mathfrak{S}$ ) into a substitution part of a clause, which is not necessary (see, e.g., Bachmair and Ganzinger (Reference Bachmair, Ganzinger, Dershowitz and Lindenstrauss1995); Nieuwenhuis and Rubio (Reference Nieuwenhuis and Rubio2001)). Suppose that there is an inference between g-clauses $C_1'\ldots C_n'$ with conclusion C’ and there is also an inference between clauses $C_1\ldots C_n$ over $\Sigma^*$ with conclusion C, where $C_i'$ is a g-clause of $C_i$ for all $1\leq i \leq n$ . Then, the inference between g-clauses $C_1'\ldots C_n'$ over $T(\Sigma\cup \{\bot\})$ can be lifted to the inference between clauses $C_1\ldots C_n$ over $\Sigma^*$ in such a way that C’ is a g-clause of C. This can be easily verified for each inference rule in $\mathfrak{S}$ .

Example 5. Consider the following Superposition inference with g-clauses:

\begin{align*}\frac{ad\bot \approx cd\bot \vee aabb\bot\approx cbb\bot \qquad abb\bot \approx db\bot}{ad\bot \approx cd\bot \vee adb\bot \approx cbb\bot}\end{align*}

where $ad\bot \approx cd\bot \vee aabb\bot\approx cbb\bot$ (resp. $abb\bot \approx db\bot$ ) is a g-clause of $a\approx c \vee aa\approx c$ (resp. $ab \approx d$ ) and $aabb\bot \succ_g cbb\bot$ (resp. $abb\bot \succ_g db\bot$ ). This Superposition inference between g-clauses can be lifted to the following Superposition inference between clauses over $\Sigma^*$ :

\begin{align*}\frac{a\approx c \vee aa\approx c \qquad ab \approx d}{a\approx c \vee ad \approx cb}\end{align*}

where $aa\succ c$ and $ab \succ d$ . We see that conclusion $ad\bot \approx cd\bot \vee adb\bot \approx cbb\bot$ of the Superposition inference between the above g-clauses is a g-clause of conclusion $a\approx c \vee ad \approx cb$ of this inference.

Example 6. Consider the following Rewrite inference with g-clauses:

\begin{align*}\frac{a\bot \not\approx d\bot \vee aabb\bot\not\approx cd\bot \qquad abb\bot \approx cb\bot}{a\bot \not\approx d\bot \vee acb\bot \not\approx cd\bot}\end{align*}

where $aabb\bot\not\approx cd\bot$ is selected and $a\bot \not\approx d\bot \vee aabb\bot\not\approx cd\bot$ (resp. $abb\bot \approx cb\bot$ ) is a g-clause of $a\not\approx d \vee aabb\not\approx cd$ (resp. $ab \approx c$ ) with $abb\bot \succ_g cb\bot$ . This Rewrite inference between g-clauses can be lifted to the following Rewrite inference between clauses over $\Sigma^*$ :

\begin{align*}\frac{a \not\approx d \vee aabb\not\approx cd \qquad ab \approx c}{a \not\approx d \vee acb \not\approx cd}\end{align*}

where $aabb\not\approx cd$ is selected and $ab\succ c$ . We see that conclusion $a\bot \not\approx d\bot \vee acb\bot \not\approx cd\bot$ of the Rewrite inference between the above g-clauses is a g-clause of conclusion $a \not\approx d \vee acb \not\approx cd$ of this inference.

4. Redundancy and Contraction Techniques

By Lemma 3 and Definition 4, we may translate a clause $C:=s_1\approx t_1\vee\cdots\vee s_m \approx t_m \vee u_1\not\approx v_1 \vee\cdots \vee u_n \not\approx v_n$ over $\Sigma^*$ with all its implied clauses using the monotonicity property into the clause $s_1(x_1)\approx t_1(x_1) \vee \cdots \vee s_m(x_m)\approx t_m(x_m) \vee u_1\bot\not\approx v_1\bot \vee \cdots \vee u_n\bot\not\approx v_n\bot$ over $T(\Sigma\cup \{\bot\}, X)$ with all its ground instances, where $x_1,\ldots, x_m$ are distinct variables in X, each symbol from $\Sigma$ is interpreted as a unary function symbol, and $\bot$ is the only constant symbol. This allows us to adapt the existing notion of redundancy found in the literature (Bachmair and Ganzinger, Reference Bachmair and Ganzinger1994; Nieuwenhuis and Rubio, Reference Nieuwenhuis and Rubio2001).

(ii) A g-clause C follows from a set of g-clauses $\{C_1,\ldots,C_n\}$ , denoted by $\{C_1,\ldots,C_n\}\models C$ , if C is true in every model of $\{C_1, \ldots, C_k\}$ .

Otherwise, suppose that $l\approx r$ simplifies $D:=C\vee l_1ll_2\approx v$ into $C\vee l_1rl_2\approx v$ . Then every g-clause D’ of D has the form $D':=C'\vee l_1ll_2w\bot \approx vw\bot$ for some $w\in \Sigma^*$ , where C’ is a g-clause of C. Now, we have $\{D'', ll_2w\bot \approx rl_2w\bot\}\models D'$ , where $D'':=C'\vee l_1rl_2w\bot \approx vw\bot$ is a g-clause of $C\vee l_1rl_2\approx v$ for some $w\in\Sigma^*$ and $ll_2w\bot \approx rl_2w\bot$ is a g-equation of $l\approx r$ . We also have $D' \succ_g D''$ and $D' \succ_g ll_2w\bot \approx rl_2w\bot$ because $l_1$ is not $\lambda$ in the condition of the rule (i.e., $l_1ll_2w\bot \succ_g ll_2w\bot$ ), and thus the conclusion follows.

We see that if C subsumes $C^\prime$ with C and $C^\prime$ containing the same number of literals, then they are the same when viewed as the finite multisets, so we can remove $C^\prime$ . Therefore, we exclude this case in the following lemma.

5. Refutational Completeness

In this section, we adapt the model construction and equational theorem proving techniques used in Bachmair and Ganzinger (Reference Bachmair and Ganzinger1994), Nieuwenhuis and Rubio (Reference Nieuwenhuis and Rubio2001), and Kim and Lynch (Reference Kim and Lynch2021) and show that S with the contraction rules is refutationally complete.

Now, let $C:=D \vee s\bot \approx t\bot$ such that C is not a g-clause of a clause with a selected literal in S. Then C produces $E_C=\{s\bot\rightarrow t\bot\}$ if the following conditions are met: (1) $I_C\not\models C$ , (2) $I_C\not\models t\bot\approx t'\bot$ for every $s\bot\approx t'\bot$ in D, (3) $s\bot\approx t\bot$ is reductive for C, and (4) $s\bot$ is irreducible by $R_C$ . We say that C is productive and produces $E_C$ if it satisfies all of the above conditions. Otherwise, $E_C=\emptyset$ . Finally, we define $I_S$ as the equality interpretation $R_S^*$ , where $R_S=\bigcup_C E_C$ is the set of all g-rules produced by g-clauses of clauses in S.

Lemma 15(iv) says that the monotonicity assumption used in this paper holds w.r.t. a model constructed by Definition 14.

In the proof of the following lemma, we write $s[t]_{suf}$ to indicate that t occurs in s as a suffix and (ambiguously) denote by $s[u]_{suf}$ the result of replacing the occurrence of t (as a suffix of s) by u.

In the remainder of the proof of this lemma, we assume that C is neither redundant w.r.t. S nor is it a reducible g-clause w.r.t. $R_S$ of some clause in S. (Otherwise, we are done by (i) or (ii).)

1. (iii) Suppose that $C:=C' \vee s\bot \approx t\bot$ produces the rule $s\bot \rightarrow t\bot$ . Since $s\bot \rightarrow t\bot \in E_C \subset R_S$ , we see that C is true in $I_S$ . We show that $C^\prime$ is false in $I_S$ . Let $C':=\Gamma \rightarrow \Delta$ . Then $I_C\not\models C'$ by Definition 14, which implies that $I_C\cap \Delta = \emptyset, I_C\supseteq \Gamma$ , and thus $I_S \supseteq \Gamma$ . It remains to show that $I_S\cap \Delta = \emptyset$ . Suppose to the contrary that $\Delta$ contains an equation $s'\bot \approx t'\bot$ which is true in $I_S$ . Since $I_C\cap\Delta =\emptyset$ , we must have $s'\bot\approx t'\bot \in I\setminus I_C$ , which is only possible if $s\bot=s'\bot$ and $I_C\models t\bot\approx t'\bot$ , contradicting condition (2) in Definition 14.

2. (iv) Suppose that C is of the form $C:=B' \vee s\bot \not\approx t\bot$ , where $s\bot \not\approx t\bot$ is a g-literal of a selected literal in a clause in S and B’ is a g-clause of B.

3. (iv.1) If $s\bot=t\bot$ , then B’ is an equality resolvent of C and the Equality Resolution inferences can be lifted. By saturation of S under $\mathfrak{S}$ and the induction hypothesis, B’ is true in $I_S$ . Thus, C is true in $I_S$ .

4. (iv.2) If $s\bot\neq t\bot$ , then suppose to the contrary that C is false in $I_S$ . Then we have $I_S \models s\bot \approx t\bot$ , which implies that $s\bot$ or $t\bot$ is reducible by $R_S$ by Lemma 15(iii). Without loss of generality, we assume that $s\bot$ is reducible by $R_S$ with some rule $lu\bot \rightarrow ru\bot$ for some $u\in\Sigma^*$ produced by a productive g-clause $D' \vee lu\bot \approx ru\bot$ of a clause $D \vee l \approx r \in S$ . This means that $s\bot$ has a suffix $lu\bot$ . Now, consider the following inference by Rewriting:

   \begin{align*}\frac{B\vee s[lu]_{suf}\not\approx t\qquad D\vee l\approx r}{B \vee D\vee s[ru]_{suf}\not\approx t}\end{align*}

   where $s[lu]_{suf}\not\approx t$ is selected for the left premise. The conclusion of the above inference has a g-clause $C':=B' \vee D' \vee s\bot[ru\bot]_{suf} \not\approx t\bot$ . By saturation of S under $\mathfrak{S}$ and the induction hypothesis, C’ must be true in $I_S$ . Moreover, we see that $s\bot[ru\bot]_{suf} \not\approx t\bot$ is false in $I_S$ by Lemma 15(iii), and D’ are false in $I_S$ by (iii). This means that B’ is true in $I_S$ , and thus C (i.e., $C=B' \vee s\bot \not\approx t\bot$ ) is true in $I_S$ , which is the required contradiction.

   1. (v) If C is nonproductive, then we assume that C is not a g-clause of a clause with a selected literal. Otherwise, the proof is done by (iv). This means that C is of the form $C:=B' \vee su\bot \approx tu\bot$ , where $su\bot \approx tu\bot$ is maximal in C and B’ contains no selected literal. If $su\bot = tu\bot$ , then we are done. Therefore, without loss of generality, we assume that $su\bot \succ_g tu\bot$ . As C is nonproductive, it means that (at least) one of the conditions in Definition 14 does not hold.

If condition (1) does not hold, then $I_C \models C$ , so we have $I_S \models C$ , that is, C is true in $I_S$ . If condition (1) holds but condition (2) does not hold, then C is of the form $C:=B_1' \vee su\bot\approx tu\bot \vee svw\bot\approx t'vw\bot$ , where $su=svw$ (i.e., $u=vw$ ) and $I_C \models tu\bot\approx t'vw\bot$ .

Suppose first that $tu\bot = t'vw\bot$ . Then we have $t=t'$ since $u=vw$ . Now, consider the following inference by Factoring:

\begin{align*}\frac{B_1\vee s\approx t \vee sv\approx tv}{B_1\vee sv\approx tv}\end{align*}

The conclusion of the above inference has a g-clause $C':=B_1' \vee svw\bot\approx tvw\bot$ , that is, $C':=B_1' \vee su\bot\approx tu\bot$ since $u=vw$ . By saturation of S under $\mathfrak{S}$ and the induction hypothesis, C’ is true in $I_S$ , and thus C is true in $I_S$ .

Otherwise, suppose that $tu\bot \neq t'vw\bot$ . Then we have $tu\bot \downarrow_{R_C} t'vw\bot$ by Lemma 15(iii) and $tu\bot \succ_g t'vw\bot$ because $su\bot \approx tu\bot$ is maximal in C. This means that $tu\bot$ is reducible by $R_C$ by some rule $l\tau\bot \rightarrow r\tau\bot$ produced by a productive g-clause $D' \vee l\tau\bot \approx r\tau\bot$ of a clause $D \vee l \approx r \in S$ . Now, we need to consider two cases:

1. (v.1) If t has the form $t:=u_1u_2$ and l has the form $l:=u_2u_3$ , then consider the following inference by Paramodulation:

\begin{align*}\frac{B\vee s\approx u_1u_2 \qquad D\vee u_2u_3\approx r}{B\vee D \vee su_3\approx u_1r}\end{align*}

The conclusion of the above inference has a g-clause $C':=B' \vee D' \vee su_3\tau\bot \approx u_1r\tau\bot$ with $u=u_3\tau$ . By saturation of S under $\mathfrak{S}$ and the induction hypothesis, C’ is true in $I_S$ . Since D’ is false in $I_S$ by (iii), either B’ or $su_3\tau\bot \approx u_1r\tau\bot$ is true in $I_S$ . If B’ is true in $I_S$ , so is C. If $su_3\tau\bot \approx u_1r\tau\bot$ is true in $I_S$ , then $su\bot \approx tu\bot$ is also true in $I_S$ by Lemma 15(iii), where $t=u_1u_2$ and $u=u_3\tau$ . Thus, C is true in $I_S$ .

1. (v.2) If t has the form $t:=u_1u_2u_3$ and l has the form $l:=u_2$ , then consider the following inference by Rewrite:

\begin{align*}\frac{B\vee s\approx u_1u_2u_3 \qquad D\vee u_2\approx r}{B\vee D\vee s\approx u_1ru_3}\end{align*}

The conclusion of the above inference has a g-clause $C'':=B' \vee D' \vee su\bot \approx u_1ru_3u\bot$ with $\tau = u_3u$ . By saturation of S under $\mathfrak{S}$ and the induction hypothesis, C” is true in $I_S$ . Since D’ is false in $I_S$ by (iii), either B’ or $su\bot \approx u_1ru_3u\bot$ is true in $I_S$ . Similarly to case (v.1), if B’ is true in $I_S$ , so is C. If $su\bot \approx u_1ru_3u\bot$ is true in $I_S$ , then $su\bot \approx tu\bot$ is also true in $I_S$ by Lemma 15(iii), where $t=u_1u_2u_3$ . Thus, C is true in $I_S$ .

If conditions (1) and (2) hold but condition (3) does not hold, then $su\bot \approx tu\bot$ is only maximal but is not strictly maximal, so we are in the previous case. (Since $\succ_g$ is total on g-clauses, condition (2) does not hold.) If conditions (1)–(3) hold but condition (4) does not hold, then $su\bot$ is reducible by $R_C$ by some rule $l\tau\bot \rightarrow r\tau\bot$ produced by a productive g clause $D' \vee l\tau\bot \approx r\tau\bot$ of a clause $D \vee l \approx r \in S$ . Again, we need to consider two cases:

1. (v.1’) If s has the form $s:=u_1u_2$ and l has the form $l:=u_2u_3$ , then consider the following inference by Superposition:

\begin{align*}\frac{B\vee u_1u_2 \approx t \qquad D\vee u_2u_3\approx r}{B\vee D \vee u_1r \approx tu_3}\end{align*}

The conclusion of the above inference has a g-clause $C':=B' \vee D' \vee u_1r\tau\bot \approx tu_3\tau\bot$ with $u=u_3\tau$ . By saturation of S under $\mathfrak{S}$ and the induction hypothesis, C’ is true in $I_S$ . Since D’ is false in $I_S$ by (iii), either B’ or $u_1r\tau\bot \approx tu_3\tau\bot$ is true in $I_S$ . If B’ is true in $I_S$ , so is C. If $u_1r\tau\bot \approx tu_3\tau\bot$ is true in $I_S$ , then $su\bot \approx tu\bot$ is also true in $I_S$ by Lemma 15(iii), where $s=u_1u_2$ and $u=u_3\tau$ . Thus, C is true in $I_S$ .

1. (v.2’) If s has the form $s:=u_1u_2u_3$ and l has the form $l:=u_2$ , then consider the following inference by Rewrite:

\begin{align*}\frac{B\vee u_1u_2u_3 \approx t \qquad D\vee u_2\approx r}{B\vee D\vee u_1ru_3\approx t}\end{align*}

The conclusion of the above inference has a g-clause $C'':=B' \vee D' \vee u_1ru_3u\bot \approx tu\bot$ with $\tau = u_3u$ . By saturation of S under $\mathfrak{S}$ and the induction hypothesis, C” is true in $I_S$ . Since D’ is false in $I_S$ by (iii), either B’ or $u_1ru_3u\bot \approx tu\bot$ is true in $I_S$ . Similarly to case (v.1’), If B’ is true in $I_S$ , so is C. If $u_1ru_3u\bot \approx tu\bot$ is true in $I_S$ , then $su\bot \approx tu\bot$ is also true in $I_S$ by Lemma 15(iii), where $s=u_1u_2u_3$ . Thus, C is true in $I_S$ .

Definition 19. (i) A theorem proving derivation is a sequence of sets of clauses $S_0=S,S_1,\ldots$ over $\Sigma^*$ such that:

1. (i.1) Deduction: $S_i=S_{i-1} \cup \{C\}$ if C can be deduced from premises in $S_{i-1}$ by applying an inference rule in $\mathfrak{S}$ .

2. (i.2) Deletion: $S_i = S_{i-1} \setminus \{D\}$ if D is redundant w.r.t. $S_{i-1}$ .Footnote ⁶

3. (ii) The set $S_\infty:=\bigcup_i(\bigcap_{j\geq i}S_j)$ is the limit of the theorem proving derivation:

\begin{align*}\frac{S\cup\{C\vee l_1ll_2\bowtie v,\; l\approx r\}}{S\cup\{C\vee l_1rl_2\bowtie v,\; l\approx r\}}\end{align*}

We see that the soundness of a theorem proving derivation w.r.t. the proposed inference system is straightforward, that is, $S_i\models S_{i+1}$ for all $i\geq 0$ .

Next, suppose an inference $\pi$ with conclusion D is redundant w.r.t. S’ and let $\pi'$ be a g-instance of it such that B is the maximal premise and D’ is the conclusion of $\pi'$ (i.e., a g-clause of D). Then there exists a minimal set $P:=\{D_1', \ldots, D_n'\}$ (w.r.t. $\succ_g$ ) of g-clauses of clauses in S’ such that $P\models D'$ and $B\succ_g D_i'$ for all $1\leq i \leq n$ . As above, we may infer that all $D_i'$ in P are not redundant w.r.t. S’, and thus $\pi'$ is redundant w.r.t. S.

If a clause C is deleted in a theorem proving derivation, then C is redundant w.r.t. some $S_j$ . By Lemma 21(i), it is also redundant w.r.t. $\bigcup_jS_j$ . Similarly, every clause in $\bigcup_jS_j\setminus S_\infty$ is redundant w.r.t. $\bigcup_jS_j$ .

By fairness, every inference $\pi$ by $\mathfrak{S}$ with premises in $S_\infty$ is redundant w.r.t. $\bigcup_j S_j$ . Using Lemma 21(ii) and the above, $\pi$ is also redundant w.r.t. $S_\infty$ , which means that $S_\infty$ is saturated under $\mathfrak{S}$ .

The following theorem states that $\mathfrak{S}$ with the contraction rules is refutationally complete for clauses over $\Sigma^*$ .

6. Conditional Completion

In this section, we present a saturation procedure under $\mathfrak{S}$ for a set of conditional equations over $\Sigma^*$ , where a conditional equation is naturally written as an equational Horn clause. A saturation procedure under $\mathfrak{S}$ (with contraction rules) can be viewed as conditional completion (Dershowitz, Reference Dershowitz, Albert, Monien and Artalejo1991) for a set of conditional equations over $\Sigma^*$ . If a set of conditional equations over $\Sigma^*$ is simply a set of equations over $\Sigma^*$ , then the proposed saturation procedure under $\mathfrak{S}$ (with contraction rules) corresponds to a completion procedure for a string rewriting system. Conditional string rewriting systems were considered in Deiß (Reference Deiß1992) in the context of embedding a finitely generated monoid with decidable word problem into a monoid presented by a finite convergent conditional presentation. It neither discusses a conditional completion (or a saturation) procedure nor considers the word problems for conditional equations over $\Sigma^*$ in general.

First, it is easy to see that a set of equations over $\Sigma^*$ is consistent. Similarly, a set of conditional equations R over $\Sigma^*$ is consistent because each conditional equation has always a positive literal and we cannot derive the empty clause from R using a saturation procedure under $\mathfrak{S}$ that is refutationally complete (cf. Section 9 in Dershowitz and Plaisted (Reference Dershowitz and Plaisted2001)).

Figure 1 shows the inference rules of $\mathfrak{S}$ (with selection) for equational Horn clauses. Since we only consider equational Horn clauses in this section, we neither need to consider the Factoring rule nor the Paramodulation rule in $\mathfrak{S}$ . In the remainder of this section, by a conditional equational theory R, we mean a set of conditional equations R over $\Sigma^*$ .

Figure 1. The inference system $\mathfrak{S}$ for conditional equations over $\Sigma^*$ .

Given a conditional equational theory R, let $G:=s\not\approx t$ be the goal of a word problem $s\approx^? t$ w.r.t. R. (Note that G does not have any positive literal.) Then we see that $R \cup \{s\approx t\}$ is consistent if and only if $R\cup \{G\}$ is inconsistent. This allows one to decide a word problem w.r.t. R using the equational theorem proving procedure discussed in Section 5.

Finally, since $\mathfrak{S}$ is refutationally complete by Thereom 24, Rewrite together with Equality Resolution is also refutationally complete for $R\cup\{G\}$ .

Given a finitely saturated conditional equational theory R under $\mathfrak{S}$ , we provide a decision procedure for the word problems w.r.t. R in the following theorem.

Otherwise, if $R_n$ does not contain the empty clause, then $R_n$ is consistent, and thus $R_0$ is consistent by Theorem 24, that is, $\{s\not\approx t\} \cup R$ is consistent. Since R is consistent and $\{s\not\approx t\} \cup R$ is saturated under $\mathfrak{S}$ , we may infer that $R\not\models s\approx t$ .

The following corollary is a consequence of Theorem 27 and the following observation. Let $R=R_0, R_1, \ldots, R_n$ be a finite fair theorem proving derivation w.r.t. $\mathfrak{S}$ for an initial conditional equational theory R with the limit $\bar{R}:=R_n$ . Then $R\cup \{G\}$ is inconsistent if and only if $\bar{R}\cup \{G\}$ is inconsistent by the soundness of the derivation and Theorem 24.

1. 6: $\lambda \not\approx ba \vee ac\approx ca$ ( $ab\not\approx ba$ is selected for 4. Rewrite of 4 with 3)

2. 7: $\lambda\not\approx ba \vee ac \not\approx ca \vee bc \approx cb$ ( $ab\not\approx ba$ is selected for 5. Rewrite of 5 with 3)

3. 8: $a\approx b$ (Superposition of 1 with 3)

4. 9: $\lambda \not\approx bb \vee ac\approx ca$ ( $\lambda \not\approx ba$ is selected for 6. Rewrite of 6 with 8)

5. 10: $\lambda \not\approx \lambda \vee ac\approx ca$ ( $\lambda \not\approx bb$ is selected for 9. Rewrite of 9 with 2)

6. 11: $ac\approx ca$ ( $\lambda \not\approx \lambda$ is selected for 10. Equality Resolution on 10)

7. 12: $\lambda\not\approx bb \vee ac \not\approx ca \vee bc \approx cb$ ( $\lambda\not\approx ba$ is selected for 7. Rewrite of 7 with 8)

8. 13: $\lambda\not\approx \lambda \vee ac \not\approx ca \vee bc \approx cb$ ( $\lambda\not\approx bb$ is selected for 12. Rewrite of 12 with 2)

9. 14: $ac \not\approx ca \vee bc \approx cb$ ( $\lambda\not\approx \lambda$ is selected for 13. Equality Resolution on 13)

10. 15: $ca \not\approx ca \vee bc \approx cb$ ( $ac \not\approx ca$ is selected for 14. Rewrite of 14 with 11)

11. 16: $bc \approx cb$ ( $ca \not\approx ca$ is selected for 15. Equality Resolution on 15)

$\cdots$

After some simplification steps, we have a saturated set $\bar{R}$ for R under $\mathfrak{S}$ using our selection strategy (i.e., the selection of negative literals). We may infer that the positive literals in $\bar{R}$ are as follows. $1^\prime:bb \approx \lambda$ , $2^\prime:a\approx b$ , and $3^\prime: bc \approx cb$ . Note that only the positive literals in $\bar{R}$ are now needed to solve a word problem w.r.t. R because of our selection strategy.

Now, consider the word problem $\phi:= acbcba\approx^?bccaba$ w.r.t. R, where the goal of $\phi$ is $G:=acbcba\not\approx bccaba$ . We only need the Rewrite and Equality Resolution steps on G and its derived literals from G using $1^\prime$ , $2^\prime$ , and $3^\prime$ . Note that all the following literals are selected except the empty clause.

$4^\prime$ : $bcbcbb\not\approx bccbbb$ (Rewrite steps of G and its derived literals from G using $2^\prime$ ).

$5^\prime$ : $bcbc\not\approx bccb$ (Rewrite steps of $4^\prime$ and its derived literals from $4^\prime$ using $1^\prime$ ).

$6^\prime$ : $ccbb\not\approx ccbb$ (Rewrite steps of $5^\prime$ and its derived literals from $5^\prime$ using $3^\prime$ ).

$7^\prime$ : $\square$ (Equality Resolution on $6^\prime$ )

Since $\bar{R}\cup G$ is inconsistent, we see that $R\cup G$ is inconsistent by the soundness of the derivation, where R and $\bar{R}$ are consistent. Therefore, we may infer that $R \models acbcba\approx bccaba$ .

7. Unification in Conditional Equational Theories

This section is concerned with unification in conditional equational theories over strings. It presents a complete method of solving unification problems over strings w.r.t. a conditional equational theory over strings if it is finitely saturated under $\mathfrak{S}$ with contraction rules.

In what follows, by the contraction rules, we mean the contraction rules in Section 3 for Horn clauses. We assume that the contraction rules are applied eagerly during a theorem proving derivation w.r.t. $\mathfrak{S}$ with the contraction rules, that is, the contraction rules are applied to a Horn clause set as soon as they become applicable. In this case, we see that the application of the Rewrite rule in $\mathfrak{S}$ can be replaced by the application of the Simplification rule for Horn clauses.

Next, we show that $\approx_{S_n}$ and $\approx_{R(S_n)}$ coincide. Since $S_n$ is saturated under $\mathfrak{S}$ with the contraction rules, each clause in $S_n$ with the nonempty conditional part is now redundant in $S_n$ . By Lemma 34, $R(S_n)$ is convergent, and thus $\approx_{R(S_n)}$ and $\downarrow_{R(S_n)}$ coincide. Now, we see that the unconditional part of each clause in $S_n$ having the nonempty conditional part does not modify/expand $\approx_{R(S_n)}$ by Definition 30(iii). Since $\approx_{S_n}$ and $\approx_{R(S_n)}$ also coincide, the conclusion follows.

The above lemma provides a method of deriving an equivalent convergent (unconditional) rewrite system over $\Sigma^*$ from a conditional equational theory over $\Sigma^*$ if it can be finitely saturated under $\mathfrak{S}$ with the contraction rules. In what follows, a rewrite system R over $\Sigma^*$ oriented by $\succ$ can also be viewed as a set of equations over $\Sigma^*$ (i.e., an equational theory over $\Sigma^*$ ).

If a conditional equational theory $S = S_0$ over $\Sigma^*$ can be finitely saturated by a fair theorem proving derivation w.r.t. $\mathfrak{S}$ with the contraction rules in some $S_n$ , then solving unification problems over strings w.r.t. S can be reduced to solving unification problems over strings w.r.t. $\approx_{R(S_n)}$ by Lemma 35. In this case, a unification problem $ux\approx_S^?vy$ is reduced to the unification problem $ux\approx_{R(S_n)}^?vy$ for two finite words $u,v \in \Sigma^*$ and $x,y \in X$ .

Figure 2 shows the proposed inference system for solving unification problems over strings w.r.t. $\approx_{R(S_n)}$ over strings, which is adapted from the rule-based E-unification algorithm for an unconditional equational theory E in Baader and Snyder (Reference Baader and Snyder2001). The computation of solving a unification problem can now be proceeded by applying the inference rules in Figure 2 with the initial system of the form $\{ux \approx^? vy\};\emptyset$ in an attempt to reach some terminal system of form $\emptyset;Q$ representing an $R(S_n)$ -unifier $\sigma_Q$ of u and v, which will be discussed in more detail.

Figure 2. The rules of deduction for rule-based $R(S_n)$ -unification.

We denote by $\mathfrak{I}$ the inference system consisting of Trivial, Decomposition, Orientation, Variable Elimination, and Lazy Paramodulation (see Figure 2). We denote by $\Longrightarrow$ a transformation on the systems $P;Q$ , where a multiset P consists of $R(S_n)$ -unification problems and a multiset Q consists of the equations in solved form. A set of equations $\{x_1\approx t_1, \ldots, x_n \approx t_n\}$ is in solved form (Baader and Snyder, Reference Baader and Snyder2001) if each variable $x_i$ has a single occurrence in the set. A substitution $\{x_1\mapsto t_1, \ldots, x_n\mapsto t_n\}$ may be represented by a set of equations in solved form, so for any set of equations Q in solved form, we denote by the corresponding substitution $\sigma_Q$ . By $\overset{*}{\Longrightarrow}$ we denote a sequence of transformations on the systems $P;Q$ including the empty sequence.

Recall that we write $s[t]_{suf}$ to indicate that t occurs in s as a suffix and (ambiguously) denote by $s[u]_{suf}$ the result of replacing the occurrence of t (as a suffix of s) by u. The following definition is adapted from Baader and Snyder (Reference Baader and Snyder2001).

It remains to show that such a rewrite proof can be a constrained rewrite proof for $sx\theta$ and $ty\theta$ w.r.t. R. Since R is convergent on $\Sigma^*$ , we choose the rightmost reduction strategy for R, where the rightmost reduction strategy always contracts a rightmost redex (i.e., a redex occurring as a suffix) in a reducible string over $\Sigma^*$ using instances of rules from R. At each step of a rewrite proof, among all the possible instances of rules from R that could be used for rightmost reduction, we choose one that is minimal w.r.t. $\succ^{lex}$ (i.e., the lexicographic extension of $\succ$ to pairs of strings over $\Sigma^*$ ). This means that for any instance $lz\rho \rightarrow rz\rho$ of $l \rightarrow r \in R$ with a fresh variable $z\in X$ used in a rewrite proof for $sx\theta$ and $ty\theta$ , $lz\rho \rightarrow rz\rho$ must be a reduced instance of $l\rightarrow r$ w.r.t. R. Also, $sx\theta$ and $ty\theta$ are reduced instances of sx and ty w.r.t. R, respectively, so we may infer that there exists a constrained rewrite proof for $sx\theta$ and $ty\theta$ w.r.t. R.

The following theorem shows the completeness of $\mathfrak{I}$ for solving an S-unification problem over $\Sigma^*$ if a conditional equational theory S over $\Sigma^*$ can be finitely saturated under $\mathfrak{S}$ with the contraction rules.Footnote ⁹ Note that unification in conditional equational theories over strings is undecidable in general because unification in (unconditional) equational theories over strings is undecidable (Otto et al., Reference Otto, Narendran and Dougherty1998). In what follows, given a set of S-unification problems P and a set of equations in solved form Q, by Vars(P) and Vars(Q), we denote the set of variables occurring in P and Q, respectively. Also, Vars(P,Q) denotes the set of all variables occurring in P or Q. By $P\theta$ , we denote a substitution $\theta$ applied to P in such a way that $\theta$ is applied to each of the equations in P. By $Dom\;\tau$ for a substitution $\tau$ , we denote $Dom\;\tau:=\{x \in X\,|\,x\tau \neq x\}$ . We say that a substitution $\theta$ is an S-solution of $P;Q$ if $\theta$ is an S-unifier of each of the equations in P and Q. It is a reduced S-solution of $P;Q$ over $\Sigma^*$ if $x\theta$ is in R(S)-normal form for all $x \in Vars(P,Q)$ .

We now define a measure of $P;Q$ and its solution $\tau$ using a quadruple $<m, n_1, n_2, n_3>$ (cf. Baader and Snyder (Reference Baader and Snyder2001)), ordered by the well-founded lexicographic ordering on quadruples of natural numbers. Here,

$m =$ The total number of rewrite steps by $R(S_n)$ in all the minimal-length constrained rewrite proofs for equations in $P\tau$ w.r.t. $R(S_n)$ ;