Checking Overlaps of Nominal Rewriting Rules
Abstract
Nominal rewriting generalises first-order rewriting by providing support for the specification of binding operators. In this paper, we give sufficient conditions for (local) confluence of closed nominal rewriting theories, based on the analysis of rule overlaps. More precisely, we show that closed nominal rewriting rules where all proper critical pairs are joinable are locally confluent. We also show how to refine the notion of rule overlap to derive confluence of the closed rewriting relation. The conditions that we define are easy to check using a nominal unification algorithm.
Keywords: nominal syntax, rewriting, confluence, binding
1 Introduction
Two key properties of rewrite theories are termination (‘the computation is finite’) and confluence (‘it is deterministic’). Termination and confluence are undecidable in general, but decidable criteria do exist that are sufficient, and so can be used to check that a rewrite theory satisfies these properties.
Criteria for guaranteeing confluence of rewriting theories were first investigated in the context of the -calculus and abstract rewrite theories in works such as [15], in which the famous Newman’s Lemma was stated: confluence and local confluence coincide for terminating rewrite theories. Nowadays this is seen as a combinatorial property of abstract rewrite theories that strictly depends on Noetherianity, that is, well-foundedness of the rewrite relation [11].
Without termination, the Critical Pair Lemma, which is the kernel of the famous Knuth-Bendix completion procedure, guarantees local confluence of term rewriting theories [13]. The most famous sufficient condition for confluence without termination, giving also rise to a programming discipline, is orthogonality. Orthogonality essentially avoids ambiguity through two easily verifiable syntactic constraints on the rewriting rules: left-linearity, that constrains each variable occurring in the left-hand side of each rule to appear only once, and non-ambiguity, that constrains left-hand sides of rules to have no overlaps (except for trivial ones, at variable positions or between a rule and its copy at the root position). With these syntactic restrictions confluence of orthogonal rewriting theories is guaranteed [17].
Nominal rewriting generalises first-order rewriting by providing support for the specification of languages with binding operators. In nominal syntax, there are two kinds of variables: atoms, which are used to represent object-level variables and can be abstracted but not be substituted, and meta-variables, called simply variables or unknowns, which can be substituted but cannot be abstracted. Substitution of a variable by a term can capture atoms (unlike higher-order theories, where substitution is non-capturing). The nominal rewriting relation is defined using equivariant nominal matching, that is, matching modulo -equivalence and atom permutations. If rules are closed, then nominal matching is sufficient to generate the rewrite relation. Nominal matching is matching modulo -equivalence only, and it is efficient (it can be solved in linear time [3]).
For nominal rewriting theories, the Critical Pair Lemma and confluence of orthogonal theories were first investigated in [7], where it was shown that the above-mentioned results extend to the class of uniform nominal rewriting theories, that is, theories where rules do not generate new atoms. More precisely, in [7] it is shown that for the class of uniform theories, if all the non-trivial critical pairs are joinable then the theory is locally confluent, and therefore confluent if it is also terminating (by Newman’s Lemma). Another sufficient condition for confluence of uniform theories is orthogonality: if the rules are left-linear and have no non-trivial critical pairs then the theory is confluent [7]. Trivial critical pairs are defined by overlaps at variable positions, or overlaps at the root between a rule and its copy (as for first-order rewrite theories). However, overlaps at the root between a rule and a permuted variant are not trivial. Both of these criteria rely on checking all non-trivial critical pairs. It is important to check also the overlaps at the root between a rule and its permuted variants, because if we miss those overlaps the theory might not be confluent (see Example 4.3).
In [19], the orthogonality condition given in [7] was relaxed, to permit overlaps at the root between a rule and its permuted copies, but only for uniform rules that satisfy an additional condition, called -stability.
In this paper we give new criteria for (local) confluence of nominal rewriting. We show that also the conditions in the Critical Pair Lemma can be relaxed if rules are uniform and -stable: if all the non-trivial critical pairs, except possibly those caused by overlaps at the root between a rule and its permuted variants, are joinable, then the theory is locally confluent. Moreover, we give a new sufficient condition for -stability, which is easy to check as it relies simply on nominal matching.
In addition, we give new improved criteria for closed nominal rewriting: it is sufficient to check the overlaps generated using just one variant of each rule.
Summarising, the main contributions of this paper are:
(i) We relax the conditions in the Critical Pair Lemma for uniform rules that are -stable: it is not necessary to consider critical pairs generated by overlaps at the root between a rule and a permuted variant. See Subsection 4.1. 5
(ii) We show that closedness is a sufficient condition for -stability. Since closedness is easy to check (by simply solving a nominal matching problem), we get an easy to check condition for -stability. See Subsection 4.2.
(iii) We show that for closed rewriting, the criteria can be relaxed even more: it is sufficient to check overlaps by using one freshened version of each rule; overlaps between permuted variants of rules (at the root or otherwise) do not need to be considered at all. See Section 5.
1.1 Related work
First-order rewriting systems and the -calculus provide two useful notions of terms and reduction. However, both have limitations, which motivated extensions such as higher-order rewriting systems (see, e.g., [12,14]). Nominal rewriting systems are at an intermediate level between higher-order rewriting systems and their explicit substitution versions, which implement in a first-order setting the capture-avoiding substitution operation together with -conversion. For the latter, indices and rewrite rules are used to deal with the management of bound variables (see, e.g., [18]). Using nominal rewriting, we can specify capture-avoiding substitutions without the need to manage indices, since names and -equivalence are primitive notions.
Two notions of ‘orthogonality’ exist in previous work for nominal rewriting: In [7], orthogonality was left-linearity plus no non-trivial critical pairs. This was proved a sufficient condition for confluence of uniform rewrite rules. The notion of orthogonality was relaxed in [19] to allow overlaps at the root between permuted variants of rules. This weaker notion does not ensure confluence of uniform rules. If we also have -stability then confluence is guaranteed [19].
A sufficient condition for -stability was given in [19], called “abstract skeleton preserving” (ASP). This is a strong restriction: it only allows identity permutations to be suspended on variables, and it requires the use of different atoms in nested abstractions. Here we show that closedness, which does not impose such restrictions and can be checked simply by solving a nominal matching problem, is a sufficient condition for -stability. In addition, for closed rewriting the criteria for confluence can be simplified, by checking only overlaps of freshened rules. Closedness and the ASP criterion are complementary in the sense that none of them implies the other.
2 Syntax
We fix disjoint countably infinite collections of atoms, unknowns (or variables), and term-formers (or function symbols). We write for the set of atoms; will range over distinct atoms. will range over distinct unknowns. f g will range over distinct term-formers. We assume that to each f is associated an arity 0. A signature Σ is a set of term-formers with their arities.
A permutation is a bijection on atoms such that nontriv( () is finite. We write () for the swapping permutation that maps to , to and all other to themselves, and id for the identity permutation, so id(. The notation is used for functional composition of permutations, so ()((()), and for inverse, so ( if and only if ().
Permutations are represented by lists of swappings; thus, composition is list concatenation, and the inverse is obtained simply by reversing the list.
Define (nominal) terms inductively by:
Call a (suspended) variable and [] an (atom-)abstraction; it represents ‘’ or ‘’ in expressions like ‘’ or ‘’. We write for syntactic identity.
Define a permutation action by:
A substitution (on unknowns), ranged over by , is a partial function from unknowns to terms with finite domain. We write id for the substitution with dom(id (it will always be clear whether we mean ‘id the identity substitution’ or ‘id the identity permutation’). If dom() then () denotes id .
Define a(n unknowns) substitution action by:
If and are substitutions, maps each to ().
The set Pos() of positions of a term is defined below. Note that is the only position in atoms and variables.
Call a subterm of at position when
If Pos(), then [] denotes the replacement of by in .
A freshness (constraint) is a pair # of an atom and a term . We call a freshness of the form # primitive, and a finite set of primitive freshnesses a freshness context. Δ, Γ and will range over freshness contexts.
We denote by the set #()# of freshness constraints.
A freshness judgement is a tuple Δ # of a freshness context and a freshness constraint. An -equivalence judgement is a tuple Δ of a freshness context and two terms. The derivable freshness and -equivalence judgements are defined by the rules in Figure 1, where (() (). We call () the difference set of permutations and .
The functions atms() and unkn() will be used to compute the set of atoms and unknowns in a term, respectively. They are defined by:
3 Nominal Rewriting
This section introduces the main concepts related with nominal rewriting, including the nominal rewriting relation itself, confluence, closedness of terms in context and rules and the closed rewriting relation.
A rewrite judgement is a tuple of a freshness context and two terms. We may write ‘’ as ‘’.
A rewrite theory R Rw) is a pair of a signature Σ and a possibly infinite set of rewrite judgements Rw in that signature; we call these rewrite rules.
A rewrite rule is left-linear if each unknown occurs at most once in .
Define the meta-action of on by:
() () ([]) ] f() f()
where id id and (() ) () ()) .
Extend the meta-action to contexts by ()##
The meta-action of permutations affects only atoms in terms (it does not suspend on variables, in contrast with the permutation action of Definition 2.3). We use it to define the equivariant closure of a set of rules, needed to generate the rewrite relation (Definition 3.4; see [7,8] for more details).
The equivariant closure of a set of rewrite rules is the closure of by the meta-action of permutations, that is, it is the set of all the permutative variants of rules in . We write eq-closure(Rw) for the equivariant closure of Rw.
Below we write Δ () for the judgements Δ .
Nominal rewriting: Let R Rw) be a rewrite theory. The one-step rewrite relation is the least relation such that for every () Rw, position , permutation , and substitution ,
The notation Δ highlights the fact that the rewrite step from to occurs with some specific rule , position , permutation and substitution , under the freshness context Δ.
The rewrite relation is the reflexive transitive closure of the one-step rewrite relation, that is, the least relation that includes the one-step rewrite relation and such that:
for all Δ and implies Δ ; and
for all Δ, , , and Δ implies Δ .
holds, we say that rewrites to in the context Δ.
The rewrite relation is defined in a freshness context since it takes into account -equivalence, which depends on freshness information for the term unknowns.
The following rewrite theory, using a signature containing term-formers of arity 1, and and of arity 2, defines -reduction for the -calculus. Below, application is denoted by juxtaposition and ([] ) is written [ ] as usual (syntactic sugar). In this theory, we can derive ([]) and also # ([]).
A rewrite theory R is terminating if there are no infinite rewriting sequences, .e., there is no term in context from which infinite rewriting steps can be performed. It is locally confluent and Δ implies that there exists such that Δ and Δ . It is confluent when, if and Δ , then exists such that Δ and Δ .
We call the situation Δ and Δ a peak.
Since the definition of the rewriting relation generated by a rewrite theory R Rw) takes into account permuted variants of rules (via the use of the permutation in the one-step rewrite relation, see Definition 3.4), it is not necessary to include permuted variants of rules in Rw. For convenience, in the rest of the paper we assume that for any Rw, if and are both in Rw then id; in other words, Rw does not contain permuted variants of the same rule.
According to Definition 3.4, to generate a rewrite step we need to solve an equivariant matching problem, that is, we need to find a permutation and a substitution such that Δ . This problem is decidable, but exponential over the number of different atoms of the terms in context [4]. However, for closed rules [7], a simpler matching problem of the form Δ , called nominal matching [20], suffices to generate the rewrite relation. Nominal matching is decidable and unitary [20] and efficient (it can be solved in linear time [3,2]).
Closed rules roughly correspond to rules without free atoms, where rewriting cannot change the binding status of an atom. They are the counterpart of rules in standard higher-order rewriting formats (see [6]). Below we first recall the definition of nominal matching and then give a structural definition and an operational characterisation of closed terms.
A term-in-context is a pair Δ of a freshness context and a term. A nominal matching problem is a pair of terms-in-context
A solution to this problem is a substitution such that Δ , and dom() unkn()
The following structural definition of closedness follows [6,5].
Call a term-in-context Δ closed when
(i) every occurrence of an atom subterm in is under an abstraction of ;
(ii) if occurs under an abstraction of then any occurrence of occurs under an abstraction of or #
(iii) for any pair occurring in , and (), if neither nor occurs in the scope of an abstraction of or , respectively, then #
Call ) closed when () is closed. 6
It is easy to check whether a term is closed, using nominal matching and a freshened variant of the term [7] (see Proposition 3.11 below).
A freshened variant of a nominal term is a term with the same structure as , except that the atoms and unknowns are replaced by ‘fresh’ atoms and unknowns (so they are not in atms() and unkn(), and perhaps are also fresh with respect to some atoms and unknowns from other syntax, which we will always specify). We omit an inductive definition.
Similarly, if is a freshness context then denotes a freshened variant of (so if # then #, where and are chosen fresh for the atoms and unknowns appearing in ).
We may extend this to other syntax, like equality and rewrite judgements. Note that if is a freshened variant of then unkn( ) unkn(.
A term-in-context is closed if and only if there exists a solution for the matching problem
Due to the link between closedness of terms-in-context and solvability of a nominal matching problem, made explicit by the proposition above, the definition of closed rewriting (Definition 3.12) is based on nominal matching instead of using equivariant matching as in Definition 3.4.
Given a rewrite rule ) and a term-in-context , write Δ when there is some a freshened variant of (so, fresh for , and ), position and substitution such that
atms() # unkn) ([]) (2)
We call this (one-step) closed rewriting.
The closed rewrite relation is the reflexive transitive closure of the one-step closed rewrite relation (as in Definition 3.4, but notice the extended freshness context).
Any rule with free atoms, such as f() , is not closed (it is impossible to match it with a freshened variant). The rule []f() 0 is closed, since taking a freshened version []f( ) 0, it is possible to solve the matching problem ( ([]f( ) 0)) (# ([]f() 0)) with the substitution () ]. Notice that # []f( () ) []f().
We refer to [7,8] for more examples and properties of closed rewriting. To compute overlaps of rules, we use a nominal unification algorithm [20].
A nominal unification problem is a set of freshness constraints and pairs of terms, written ## It is unifiable if there exists a solution Γ (freshness context and substitution) such that Γ (##). In this case, Γ is said to be a unifier for the problem.
Nominal unification is decidable and unitary, that is, if there is a solution for a nominal unification problem there exists a most general one.
4 Confluence of Nominal Rewriting
In this section we consider two well-known criteria for confluence of first-order rewriting based on the notion of overlapping rewrite steps [1]. They can be extended to nominal rewrite theories, but it is necessary to add some conditions.
4.1 Critical Pair Criterion and Orthogonality
The notion of overlap has been extended from the first-order setting to the nominal rewriting setting [7]. In the first-order case, overlaps are computed by unification of a left-hand side of a rule with a non-variable subterm of the left-hand side of a rule (which could be a copy of with renamed variables, in which case the subterm must be strict, that is, overlaps at the root between a left-hand side and its copy are not considered). With nominal rules the nominal rewrite relation is generated by the equivariant closure of a set of rules (see Definitions 3.3 and 3.4) so we must consider permuted variants of rules, and use nominal unification instead of first-order unification. This is Definition 4.1, which follows [7]:
(Overlaps and CPs) Let ( 2) be copies of rewrite rules in eq-closure(Rw) (so and could be copies of the same rule), where () (, as usual. If the nominal unification problem has a most general solution Γ for some position , then we say that overlaps with , and we call the pair of terms-in-context Γ ([]) a critical pair. If is a variable position, or if and are identical modulo renaming of variables and , then we call the overlap and critical pair trivial, otherwise we call it non-trivial.
The critical pair Γ ([]) is joinable if there is a term such that Γ and Γ ([]) .
We distinguish between different kinds of overlaps and critical pairs:
(Permutative Overlaps and CPs) Let ( 1 2) be copies of rewrite rules in eq-closure(Rw), such that there is an overlap. If is a copy of , we say that the overlap is permutative. We call a permutative overlap at the root position root-permutative. We call an overlap that is not trivial and not root-permutative proper. We use the same terminology to classify critical pairs; e.g. we call a critical pair generated by a permutative overlap permutative.
A permutative overlap indicates that there is a critical pair generated by a rule and one of its permuted variants.
Note that only the root-permutative overlaps where is id are trivial. While overlaps at the root between variable-renamed versions of first-order rules can be discarded (they generate equal terms), in nominal rewriting we must also consider overlaps at the root between permuted variants of rules. Indeed, they do not necessarily produce the same result, as the following example shows (see also [19]).
Definition 4.4 introduces uniformity. In [7] a Critical Pair Lemma was proved for uniform nominal rewrite theories, that joinability of non-trivial critical pairs implies local confluence; confluence follows by Newman’s Lemma if the theory is terminating. Uniformity features in this paper in Theorem 4.6. Intuitively, uniformity means that if is not free in and rewrites to then is not free in .
(Uniformity) We call a nominal rewrite theory R Rw) uniform [7] when if Δ and Δ# for some , then Δ#.
Note that in the Critical Pair Lemma of [7], joinability is assumed for all non-trivial critical pairs. Joinability of proper critical pairs is insufficient for local confluence, even for a uniform theory: the rule in Example 4.3 is uniform. However, an additional condition allows us to prove that uniform rewrite theories with joinable proper critical pairs are locally confluent. Recall the notion of -stability from [19]:
(-stability) Call a rewrite rule -stable when, for all Δ implies Δ
A rewrite theory R Rw) is -stable if every rule in Rw is -stable.
-stability is hard to check in general because of the quantification over all and . -stability is related to closedness (Definition 3.9): we show in Section 4.2
that closed rules are -stable. The reverse implication does not hold: for example () is -stable but not closed.
(Critical Pair Lemma for uniform -stable theories) Let R Rw) be a uniform rewrite theory where all the rewrite rules in Rw are -stable. If every proper critical pair is joinable, then R is locally confluent.
We consider cases. There are four kinds of peaks:
If the rewrite steps occur at disjoint positions, then the peak is trivially joinable by applying the same rules, permutations and substitutions.
If the peak is an instance of a proper critical pair (joinable by assumption) then it is joinable since rewriting is compatible with instantiation [7, Theorem 49].
If the peak is generated by an overlap at a variable position, without loss of generality assume and occurs inside under an instance of an unknown () (see Figure 2). Then we can change the action of over , replacing by , such that , as it is done in the first-order case. Here we rely on uniformity to ensure that no free atoms are introduced by the rewrite step, so freshness constraints are preserved when replacing by .
If there is a root-permutative overlap then joinability follows by -stability.2
Call a rewrite theory R Rw) orthogonal when all the rules in Rw are left-linear and there are no non-trivial critical pairs.
Call R Rw) quasi-orthogonal when all rules are left-linear and there are no proper overlaps.
So orthogonal theories are left-linear and can have trivial overlaps only, whereas quasi-orthogonal theories are left-linear and can have trivial overlaps and root-permutative overlaps (Definition 4.2).
Orthogonal theories were defined in [7]. Quasi-orthogonal theories were defined in [19] and called orthogonal (we changed the name here to avoid confusion).
For uniform nominal rewrite theories, orthogonality implies confluence [7].
Quasi-orthogonality is insufficient for confluence of uniform theories; see Example 4.3. If a theory is uniform, quasi-orthogonal, and -stable, then it is confluent [19].
4.2 Criterion for -stability
This section presents closedness as a sufficient condition for -stability. Closedness is easy to check using a nominal matching algorithm (see Proposition 3.11).
An easy technical lemma will be useful, that substitutions that coincide modulo on the unknowns in a term yield -equivalent instances, and vice-versa (i.e., if the instances are -equivalent, the substitutions must coincide modulo on the unknowns of the term):
().
If is a closed rule, then is -stable.
It is sufficient to prove the following property: closed and and Δ implies Δ .
The matching problems ( ()) (()#() ()) and ( ()) (()#() ()) are solvable with solutions and , respectively, insofar as is closed. Hence, we can infer:
()#() () ()
()#() () ()
From Lemma 4.8 (), it follows that (()#()
Since () (), Lemma 4.8 () can be used to demonstrate the equivalences
and, finally, Δ()#() is obtained by transitivity. Notice that atoms in () do not appear in , so that the previous judgement can be strengthened taking only Δ as context. 2
5 Better Criteria for Confluence of Closed Rewriting
In this section we study confluence of closed rewriting (Definition 3.12). Closed rewriting uses freshened versions of rules and nominal matching, instead of the computationally more expensive equivariant matching used in Definition 3.4. Closed rewriting is complete for equational reasoning if the axioms are closed [8].
The following three lemmas state properties of closed rules and closed rewriting, and will be useful for Theorems 5.6 and 5.8. The first two state that if a rule has no free atoms then its freshness context can be extended to obtain a closed rule, and closed rewriting with either rule is equivalent. The third lemma states that a rule with free atoms generates an empty closed rewriting relation.
Let be a rule such that every occurrence of an atom subterm in or is under the scope of an abstraction of (i.e., no atom occurs free as a subterm in ). Then there exists a minimal context ()#() such that is closed.
By definition of closed term (see Definition 3.9), we must check:
(i) Every occurrence of an atom subterm is under an abstraction of .
(ii) If occurs under an abstraction of , then any occurrence of is in the scope of an abstraction of or #
(iii) For any pair occurring in and (), if and are not abstracted over the respective occurrences of , then #
The first point holds by assumption. For the second and third points, if # it is sufficient to include # 2
Suppose and are rules such that has no free atom-subterms and ()#() is the minimal set of freshness constraints that makes closed. Then, Γ Γ
Proof The left-to-right direction. If Γ , then Γ()#(Γ) , i.e., there is such that
Since ((), it suffices to show that Γ()#(Γ) to obtain Γ()#(Γ) as required.
To prove Γ()#(Γ) , observe that # if and occur in () and at least one of the following holds:
is abstracted over and is not abstracted over . We know
Then, since is not abstracted over , the same freshness context allows us to derive # and, consequently, #.
is in () and neither nor are abstracted over the respective occurrences of . The same argument is valid in this case.
The right-to-left direction. If Γ , then Γ()#(Γ) , i.e., there is such that
So ((). It follows that Γ()#(Γ) . 2
Suppose is a nominal rule and there exist and a closed-rewriting step . Then every occurrence of an atom subterm in or is under an abstraction of (i.e., no atom occurs free as a subterm in ).
By contradiction. Assume has a free atom subterm ; without loss of generality, we assume (if it occurs in we reason in the same way). By definition of closed-rewriting, there exists , a fresh variant of , such that ()#) []. But is free, and does not occur in , contradicting Δ()#) .2
The following definitions of fresh overlap and fresh critical pair will be used to derive sufficient conditions for confluence of closed rewriting.
(Fresh Overlaps and CPs) Let ( 2) be freshened versions of rewrite rules in Rw ( and could be two freshened versions of the same rule), where ()(, as usual. If the nominal unification problem has a most general solution Γ for some position , then we say that fresh overlaps with , and we call the pair of terms-in-context Γ ([]) a fresh critical pair.
If is a variable position, or if and are equal modulo renaming of variables and , then we call the overlap and critical pair trivial.
If and are freshened versions of the same rule and , then we call the overlap and critical pair fresh root-permutative.
A fresh overlap (resp. fresh critical pair) that is not trivial and not root-permutative is proper.
The fresh critical pair Γ ([]) is joinable if there is a term such that Γ and Γ ([]) .
Call a rewrite theory R Rw) fresh quasi-orthogonal when all rules are left-linear and there are no proper fresh critical pairs.
(Critical Pair Lemma for Closed Rewriting) Let R ) be a rewrite theory where every proper fresh critical pair is joinable. Then the closed rewriting relation generated by R is locally confluent.
Since rules with free atom-subterms do not generate closed rewriting steps (Lemma 5.3), without loss of generality we can assume that the rules in do not have free atom-subterms. Consider ) the closed rewrite theory obtained by extending the freshness contexts of rules in , as described in Lemma 5.1. Then, by Lemma 5.2, the closed rewriting relation generated by R is equivalent to the one generated by . Thus, joinability of proper fresh critical pairs in R implies joinability of proper fresh critical pairs in and it suffices to prove local confluence for the closed rewriting relation generated by . Also note that since all rules in are closed, they are uniform and -stable (Lemma 4.9).
We consider the kinds of peaks that may arise:
If the rewrite steps defining the peak occur at disjoint positions then the peak is trivially joinable by applying the same rules and substitutions.
If the peak is generated by an overlap at a variable position then consider and freshened versions of two rules (see Figure 2, but here we do not need permuted versions for the rules are already freshened). Let Δ be the context used to rewrite with and . Without loss of generality, we assume Δ()#) and occurs inside under an instance of an unknown (). Then we can change the action of over , replacing by , such that , as it is done in the first-order case. Here we rely on the assumption of uniformity, which ensures that no free atoms are introduced by the rewrite step, therefore no freshness constraint will be violated when replacing by .
If there are freshened rules and and a term-in-context , such that there is a rewrite step at position in using and at position using then Δ and Δ . Without loss of generality we assume that . Since the sets of variables in the freshened rules are disjoint, without loss of generality we can assume () (, and define the substitution such that (() (). Then, Δ . Therefore the unification problem has a solution. Hence, by Definition 5.4, there is a fresh critical pair between and . Observe that, if and is a permuted copy of (equal or not), then the terms of divergence and are -equivalent by triviality or -stability. If the critical pair is proper it is joinable by assumption. Therefore the peak is joinable since the rewriting relation is compatible with instantiation [7, Theorem 49].2
Since it is sufficient to consider just one freshened version of each rule when computing overlaps of closed rules, the number of fresh critical pairs for a rewrite theory with a finite number of rules is finite. Thus, Theorem 5.6 provides an effective criterion for local confluence, similar to the criterion for first-order systems.
We can deduce from Theorem 5.6 that the closed rewriting relation for the closed theory defining explicit substitution in Example 3.5 (i.e., all the rules except Beta) is locally confluent: every proper fresh critical pair is joinable. If we consider also the rule (Beta) then the system is not locally confluent. This does not contradict the previous theorem, because there is a proper fresh critical pair between (Beta) and (), obtained from (([]) )[], which is not joinable:
Next we consider criteria for confluence based on (quasi-) orthogonality. The following lemma is used in the proof of confluence.
Let R Rw) be a closed rewrite theory. if, and only if, there exist such that a()#u) .
In both directions, the proof is by induction on the number of steps in and Δ a()#u) , respectively. From left to right, the result follows by definition of closed rewriting. In the other direction, it is necessary to consider closedness of rules. Any version of can be used in one step Δ a()#u) . So, the version freshened with respect to Δ a() and all the terms in the rewrite sequence could be taken in this step. Weakening the freshness context, a()#u) is obtained. Since the atoms of do not occur in Δ and in the terms of the rewrite sequence, the freshness context can be strengthened into Δ a()#u) . Thus, is reached. 2
If R is a fresh-quasi-orthogonal rewrite theory, then the closed rewriting relation generated by R is confluent.
As in the previous theorem, we prove confluence for the closed rewriting relation generated by ), where is obtained by extending the freshness contexts to close the rules of which do not have free atom-subterms (see Lemmas 5.3, 5.1 and 5.2). Since all rules in are closed, they are also uniform and -stable.
Now we can proceed in the usual way (see, e.g., [1,16,7]), by proving the diamond property for a parallel closed-rewriting relation (simultaneous closed rewriting steps at disjoint positions). The proof proceeds by analysis of peaks: When overlaps occur under instances of variables, we use uniformity to ensure that when we change the substitution, the rewrite step is still possible. Joinability of root-permutative overlaps is a consequence of -stability for the rules are closed.
Alternatively, we can prove confluence by reducing to a previous result for standard nominal rewriting, using the previous lemma: Consider a peak and Δ . By Lemma 5.7 (), there exist such that Δ a()#u) and a()#u) . Theorem 28 of [19] guarantees confluence with the context Δ a()#u), since for closed theories our notion of fresh-quasi-orthogonality coincides with the notion of orthogonality defined in [19] (in this case, it does not matter which permuted version is used to obtain a proper critical pair). Using Lemma 5.7(), we obtain confluence of 2
Consider a signature for first-order logic, with term-formers , and of arity 1, and of arity 2 (as usual we write them infix). The following closed rules can be used to simplify formulas:
Why write [](()) on the right-hand side above, instead of the -equivalent []()? We could: these are equivalent—in a nominal context. The version above directly translates the corresponding CRS rule (see [6]) which, following Barendregt’s convention, must use different names for bound variables in a rule. Theorem 5.8 tells us that the closed rewriting relation generated by the theory in Example 5.9 is confluent. This theory is closed, but forbidden by ASP restrictions because of the permutation () on the right-hand side.
The criteria for local confluence given in Theorem 5.6 and for confluence given in Theorem 5.8 for closed rewriting are easy to check using a nominal unification algorithm: just compute overlaps for the set of rules obtained by taking one freshened copy of each given rule. For comparison, the criteria given in [7] and [19] require the computation of critical pairs for permutative variants of rules, which needs equivariant unification (exponential). Theorems 5.6 and 5.8 apply even if the rules are not closed, as long as we use closed rewriting. Consider the uniform rules () 0 and (()) 0. These rules have no non-trivial fresh overlap, and closed rewriting is confluent, but the standard rewriting relation is not confluent, since the term (()) rewrites to both (0) and 0. Using closed rewriting, the term (()) is a normal form.
6 Conclusion
We have presented easy-to-check criteria for confluence of nominal rewriting theories (Theorem 4.6 and Lemma 4.9, and Theorems 5.6 and 5.8), improving previous criteria [7,19]. The Critical Pair Lemma for closed rewriting yields a completion algorithm for closed rewrite rules [9]. We intend to enlarge the PVS library on term rewriting systems [10] to formalise the results of this paper.
References
[1] F. Baader and T. Nipkow. Term rewriting and all that. Cambridge UP, 1998.
[2] C. Calvès. Complexity and implementation of nominal algorithms, 2010. PhD thesis, King’s College London.
[3] C. Calvès and M. Fernández. Matching and alpha-equivalence check for nominal terms. J. Comput. Syst. Sci., 76(5):283–301, 2010.
[4] J. Cheney. The complexity of equivariant unification. In Automata, Languages and Programming: 31st Int. Colloquium, ICALP 2004, volume 3142 of LNCS, pages 332–344. Springer, 2004.
[5] R. A. Clouston. Closed terms (unpublished notes). Available from http://cs.au.dk/~ranald/closedterms.pdf, 2007.
[6] J. Domínguez and M. Fernández. Relating nominal and higher-order rewriting. In Mathematical Foundations of Computer Science 2014 - 39th Int. Symposium, MFCS 2014. Proc., Part I, volume 8634 of LNCS, pages 244–255. Springer, 2014.
[7] M. Fernández and M. J. Gabbay. Nominal rewriting. Information and Computation, 205(6):917–965, June 2007.
[8] M. Fernández and M.J. Gabbay. Closed nominal rewriting and efficiently computable nominal algebra equality. In Proc. 5th Int. Workshop on Logical Frameworks and Meta-languages: Theory and Practice, LFMTP 2010, pages 37–51, 2010.
[9] M. Fernández and A. Rubio. Nominal Completion for Rewrite Systems with Binders. In Automata, Languages, and Programming, volume 7392 of LNCS, pages 201–213. Springer, 2012.
[10] A.L. Galdino and M. Ayala-Rincón. A Formalization of the Knuth-Bendix(-Huet) Critical Pair Theorem. J. Autom. Reasoning, 45(3):301–325, 2010.
[11] G. P. Huet. Confluent reductions: Abstract properties and applications to term rewriting systems: Abstract properties and applications to term rewriting systems. J. of the ACM, 27(4):797–821, October 1980.
[12] J.-W. Klop, V. van Oostrom, and F. van Raamsdonk. Combinatory reduction systems, introduction and survey. Theoretical Computer Science, 121:279–308, 1993.
[13] D. Knuth and P. Bendix. Simple word problems in universal algebras. In Computational Problems in Abstract Algebra. Pergamon Press, Oxford, 1970.
[14] R. Mayr and T. Nipkow. Higher-order rewrite systems and their confluence. Theoretical Computer Science, 192:3–29, 1998.
[15] M. H. A. Newman. On Theories with a Combinatorial Definition of “Equivalence”. The Annals of Mathematics, 43(2):pp. 223–243, 1942.
[16] A. C. Rocha-Oliveira and M. Ayala-Rincón. Formalizing the confluence of orthogonal rewriting systems. In Proc. 7th Workshop on Logical and Semantic Frameworks, with Applications, LSFA 2012, pages 145–152, 2012.
[17] B. K. Rosen. Tree-manipulating systems and Church-Rosser theorems. J. of the ACM, 20(1):160–187, January 1973.
[18] M.-O. Stehr. CINNI - A Generic Calculus of Explicit Substitutions and its Application to - - and -Calculi. Electronic Notes in Theoretical Computer Science, 36:70–92, 2000. The 3rd Int. Workshop on Rewriting Logic and its Applications.
[19] T. Suzuki, K. Kikuchi, T. Aoto, and Y. Toyama. Confluence of Orthogonal Nominal Rewriting Systems Revisited. In 26th Int. Conf. on Rewriting Techniques and Applications (RTA 2015), volume 36 of LIPIcs, pages 301–317, 2015.
[20] C. Urban, A. M. Pitts, and M. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1- 3):473–497, 2004.
Notes
1 Email: anacrismarie@gmail.com. Author supported by a Ph.D. scholarship from CAPES Brazil. ↩
2 Email: ayala@unb.br. Work partially supported by grant CNPq UNIVERSAL 476952/2013-1. ↩
3 Email: maribel.fernandez@kcl.ac.uk. Work partially supported by grant CsF PVE CAPES 146/2012. ↩
4 Web: gabbay.org.uk ↩
5 This result was independently obtained by T. Suzuki, K. Kikuchi, T. Aoto and Y. Toyama, “On confluence of nominal rewriting systems”, 16th JSSST Workshop on Programming and Programming Languages, 2014, in Japanese. ↩
6 Here we use pair as a term former and apply the definition above. ↩