HTML reading edition · 19 source pages · Open the source PDF
Heriot-Watt University Research Gateway Checking Overlaps of Nominal Rewriting RulesCitation for published version: Ayala-Rincón, M, Fernández, M, Gabbay, J & Rocha-Oliveira, AC 2016, 'Checking Overlaps of Nominal Rewriting Rules', Electronic Notes in Theoretical Computer Science, vol. 323, pp. 39-56. https://doi.org/10.1016/j.entcs.2016.06.004 Digital Object Identifier (DOI): 10.1016/j.entcs.2016.06.004 Link: Link to publication record in Heriot-Watt Research Portal Document Version: Publisher's PDF, also known as Version of record Published In: Electronic Notes in Theoretical Computer ScienceGeneral rights Copyright for the publications made accessible via Heriot-Watt Research Portal is retained by the author(s) and / or other copyright owners and it is a condition of accessing these publications that users recognise and abide by the legal requirements associated with these rights. Take down policy Heriot-Watt University has made every reasonable effort to ensure that the content in Heriot-Watt Research Portal complies with UK legislation. If you believe that the public display of this file breaches copyright please contact open.access@hw.ac.uk providing details, and we will remove access to the work immediately and investigate your claim.Download date: 06. Nov. 2026

Checking Overlaps of Nominal Rewriting Rules

Mauricio Ayala-Rincón a,2 Maribel Fernández b,3

Murdoch James Gabbayc,4 Ana Cristina Rocha-Oliveiraa,1

a Departamentos de Matemática e Ciência da Computação

Universidade de Brasília, Brasília D.F., Brasil

b Department of Informatics

King’s College London, London, UK c School of Mathematics and Computer Sciences

Heriot-Watt University, Einburgh, UK

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; a, b, c, . . . will range over distinct atoms. X, Y, Z, . . . will range over distinct unknowns. f, g, . . . will range over distinct term-formers. We assume that to each f is associated an arity n ≥ 0. A signature Σ is a set of term-formers with their arities.

Definition 2.1

A permutation π is a bijection on atoms such that nontriv(π) = {a | π(a) ≠ a} is finite. We write (a b) for the swapping permutation that maps a to b, b to a and all other c to themselves, and id for the identity permutation, so id(a) = a. The notation π ◦π′ is used for functional composition of permutations, so (π ◦π′)(a) = π(π′(a)), and π−1 for inverse, so π(a) = b if and only if a = π−1(b).

Permutations are represented by lists of swappings; thus, composition is list concatenation, and the inverse is obtained simply by reversing the list.

Definition 2.2

Define (nominal) terms inductively by:

s, t, l, r, u ::= a | π · X | [a]t | f(t1, . . . , tn)

Call π · X a (suspended) variable and [a]t an (atom-)abstraction; it represents ‘x.e’ or ‘x.φ’ in expressions like ‘λx.e’ or ‘∀x.φ’. We write ≡ for syntactic identity.

Definition 2.3

Define π · t a permutation action by:

π · a ≡π(a) π · (π′·X) ≡(π ◦π′) · Xπ · [a]t ≡[π(a)](π · t) π · f(t1, . . . , tn) ≡f(π · t1, . . . , π · tn)

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 X ∉ dom(σ) then σ(X) denotes id · X.

Define tσ a(n unknowns) substitution action by:

aσ ≡a (π · X)σ ≡π · X (X ∉dom(σ))([a]t)σ ≡[a](tσ) (π · X)σ ≡π · σ(X) (X ∈dom(σ))f(t1, . . . , tn)σ ≡f(t1σ, . . . , tnσ)

If σ and θ are substitutions, σ ◦θ maps each X to (Xσ)θ.

Definition 2.4

The set Pos(t) of positions of a term t is defined below. Note that ϵ is the only position in atoms and variables.

(pϵ)ϵ ∈Pos(t)p ∈Pos(t)(p[a])1 · p ∈Pos([a]t)p ∈Pos(ti) (1 ≤i ≤n)(pf)i · p ∈Pos(f(t1, . . . , ti, . . . , tn))

Call t|p a subterm of t at position p when

t|ϵ = t [a]t|1·p = t|pf(t1, . . . , ti, . . . , tn)|i·p = ti|p (1 ≤i ≤n)

If p ∈ Pos(s), then s[p←t] denotes the replacement of s|p by t in s.

Definition 2.5

A freshness (constraint) is a pair a#t of an atom a and a term t. We call a freshness of the form a#X primitive, and a finite set of primitive freshnesses a freshness context. Δ, Γ and ∇ will range over freshness contexts.

We denote by ∇σ the set {a#σ(X)| a#X ∈∇} of freshness constraints.

A freshness judgement is a tuple Δ ⊢a#t of a freshness context and a freshness constraint. An α-equivalence judgement is a tuple Δ ⊢s ≈α t of a freshness context and two terms. The derivable freshness and α-equivalence judgements are defined by the rules in Figure 1, where ds(π, π′) = {a ∈𝔸 | π(a) ≠ π′(a)}. We call ds(π, π′) the difference set of permutations π and π′.

(#ab)Δ ⊢a#b(#[a])Δ ⊢a#[a]t(π-1(a)#X) ∈Δ (#X) Δ ⊢a#π · XΔ ⊢a#t (#[b]) Δ ⊢a#[b]tΔ ⊢a#t1 · · · Δ ⊢a#tn (#f) Δ ⊢a#f(t1, . . . , tn)(≈αa)Δ ⊢a ≈α aΔ ⊢b#t Δ ⊢(b a) · t ≈α u (≈α[b]) Δ ⊢[a]t ≈α [b]ua#X ∈Δ for all a ∈ds(π, π′) (≈αX) Δ ⊢π · X ≈α π′ · XΔ ⊢t ≈α u(≈α[a])Δ ⊢[a]t ≈α [a]uΔ ⊢ti ≈α ui(1 ≤i ≤n)(≈αf)Δ ⊢f(t1, . . . , tn) ≈α f(u1, . . . , un)
Figure 1: Freshness and α-equality
Definition 2.6

The functions atms(t) and unkn(t) will be used to compute the set of atoms and unknowns in a term, respectively. They are defined by:

atms(a) = {a} atms(π · X) = nontriv(π)atms([a]t) = atms(t) ∪{a} atms(f(t1, . . . , tn)) = ⋃i atms(ti)unkn(a) = ∅ unkn(π · X) = {X}unkn([a]t) = unkn(t) unkn(f(t1, . . . , tn)) = ⋃i unkn(ti)

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.

Definition 3.1

A rewrite judgement is a tuple ∇⊢l →r 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 ∇⊢l →r is left-linear if each unknown occurs at most once in l.

Definition 3.2

Define tπ the meta-action of π on t by:

aπ = π(a) (ρ·X)π = ρπ ·X ([a]t)π = [aπ]tπ f(t1, . . . , tn)π = f(tπ 1, . . . , tπ n),

where idπ = id and ((a b) ◦ρ)π = (π(a) π(b)) ◦ρπ.

Extend the meta-action to contexts by ∇π = {π(a)#X| a#X ∈∇}.

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).

Definition 3.3

The equivariant closure of a set Rw of rewrite rules is the closure of Rw by the meta-action of permutations, that is, it is the set of all the permutative variants of rules in Rw. We write eq-closure(Rw) for the equivariant closure of Rw.

Below we write Δ ⊢ (φ1, . . . , φn) for the judgements Δ ⊢φ1, . . . , Δ ⊢φn.

Definition 3.4

Nominal rewriting: Let R = (Σ, Rw) be a rewrite theory. The one-step rewrite relation Δ ⊢sR→t is the least relation such that for every (∇⊢l →r) ∈ Rw, position p, permutation π, and substitution θ,

Δ ⊢(∇πθ, s|p ≈α lπθ, s[p←rπθ] ≈α t)(Rew∇⊢l→r)Δ ⊢s R→t

The notation Δ ⊢s →⟨R,p,π,θ⟩t highlights the fact that the rewrite step from s to t occurs with some specific rule R, position p, permutation π and substitution θ, under the freshness context Δ.

The rewrite relation Δ ⊢R s →t 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 s: Δ ⊢s ≈α s′ implies Δ ⊢R s →s′; and

• for all Δ, s, t, u: Δ ⊢R s →t and Δ ⊢R t →u implies Δ ⊢R s →u.

If Δ ⊢R s →t holds, we say that s rewrites to t 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.

Example 3.5

The following rewrite theory, using a signature containing term-formers λ of arity 1, and app and subst of arity 2, defines β-reduction for the λ-calculus. Below, application is denoted by juxtaposition and subst([a]X, Y ) is written X[a↦ →Y ] as usual (syntactic sugar). In this theory, we can derive ⊢R (λ[a]a)Y →Y and also a#Z ⊢R (λ[a]Z)Y →Z.

(Beta) ⊢(λ[a]X)Y →X[a↦ →Y ](σapp) ⊢(XX′)[a↦ →Y ] →X[a↦ →Y ]X′[a↦ →Y ](σvar) ⊢a[a↦ →X] →X (σlam) b#Y ⊢(λ[b]X)[a↦ →Y ] →λ[b](X[a↦ →Y ]) (σϵ) a#X ⊢X[a↦ →Y ] →X
Definition 3.6

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 if Δ ⊢s R→u and Δ ⊢s R→v implies that there exists w such that Δ ⊢R u →w and Δ ⊢R v →w. It is confluent when, if Δ ⊢R s →t and Δ ⊢R s →t′, then u exists such that Δ ⊢R t →u and Δ ⊢R t′ →u.

We call the situation Δ ⊢s R→u and Δ ⊢s R→v a peak.

Remark 3.7

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 R ∈ Rw, if R and Rπ 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 Δ ⊢s|p ≈α lπθ. 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 Δ ⊢s|p ≈α lθ, 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.

Definition 3.8

A term-in-context is a pair Δ ⊢s of a freshness context and a term. A nominal matching problem is a pair of terms-in-context

(∇⊢l) ?≈(Δ ⊢s) where unkn(∇⊢l) ∩unkn(Δ ⊢s) = ∅.

A solution to this problem is a substitution σ such that Δ ⊢∇σ, Δ ⊢lσ ≈α s, and dom(σ) ⊆ unkn(∇⊢l).

The following structural definition of closedness follows [6,5].

Definition 3.9

Call a term-in-context Δ ⊢t closed when

(i) every occurrence of an atom subterm a in t is under an abstraction of a;

(ii) if π · X occurs under an abstraction of π · a then any occurrence of π′ · X occurs under an abstraction of π′ · a or a#X ∈Δ;

(iii) for any pair π1 · X, π2 · X occurring in t, and a ∈ds(π1, π2), if neither π1 · X nor π2 · X occurs in the scope of an abstraction of π1 · a or π2 · a, respectively, then a#X ∈Δ.

Call R = (∇⊢l →r) closed when ∇⊢ (l, r) 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).

Definition 3.10

A freshened variant tИ of a nominal term t is a term with the same structure as t, except that the atoms and unknowns are replaced by ‘fresh’ atoms and unknowns (so they are not in atms(t) and unkn(t), 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 a#X ∈∇ then aИ#XИ∈∇И, where aИ and XИ 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 ∇И⊢lИ→rИ is a freshened variant of ∇⊢l →r then unkn(∇И⊢ lИ→rИ) ∩ unkn(∇⊢l →r) = ∅.

Proposition 3.11

A term-in-context ∇⊢l is closed if and only if there exists a solution for the matching problem

(∇И⊢lИ)?≈ (∇, atms(∇И, lИ)#unkn(∇, l) ⊢l). (1)

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.

Definition 3.12

Given a rewrite rule R = (∇⊢l →r) and a term-in-context Δ ⊢s, write Δ ⊢s R→c t when there is some RИ a freshened variant of R (so, fresh for R, Δ, s, and t), position p and substitution θ such that

Δ, atms(RИ) # unkn(Δ, s, t) ⊢ (∇Иθ, s|p≈αlИθ, s[p←rИθ]≈αt). (2)

We call this (one-step) closed rewriting.

The closed rewrite relation Δ ⊢R s →c t is the reflexive transitive closure of the one-step closed rewrite relation (as in Definition 3.4, but notice the extended freshness context).

Example 3.13

Any rule with free atoms, such as ⊢ f(a, a) →a, is not closed (it is impossible to match it with a freshened variant). The rule R = ⊢ [a]f(a, X) → 0 is closed, since taking a freshened version RИ= ⊢ [b]f(b, Y ) → 0, it is possible to solve the matching problem ( ⊢ ([b]f(b, Y ), 0)) ?≈ (b#X ⊢ ([a]f(a, X), 0)) with the substitution σ = [Y↦ → (a b) · X]. Notice that b#X ⊢ [b]f(b, (a b) · X) ≈α [a]f(a, X).

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].

Definition 3.14

A nominal unification problem is a set of freshness constraints and pairs of terms, written {a1#t1, . . . , ak#tk, s1 ?≈? u1, . . . , sm ?≈? um}. It is unifiable if there exists a solution ⟨Γ, θ⟩ (freshness context and substitution) such that Γ ⊢ (a1#t1θ, . . . , ak#tkθ, s1θ ≈α u1θ, . . . , smθ ≈α umθ). 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 R1 with a non-variable subterm of the left-hand side of a rule R2 (which could be a copy of R1 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]:

Definition 4.1

(Overlaps and CPs) Let Ri = ∇i ⊢li →ri (i = 1, 2) be copies of rewrite rules in eq-closure(Rw) (so R1 and R2 could be copies of the same rule), where unkn(R1) ∩unkn(R2) = ∅, as usual. If the nominal unification problem ∇1 ∪∇2 ∪{l2 ?≈? l1|p} has a most general solution ⟨Γ, θ⟩ for some position p, then we say that R1 overlaps with R2, and we call the pair of terms-in-context Γ ⊢ (r1θ, l1θ[p←r2θ]) a critical pair. If p is a variable position, or if R1 and R2 are identical modulo renaming of variables and p = ϵ, then we call the overlap and critical pair trivial, otherwise we call it non-trivial.

The critical pair Γ ⊢ (r1θ, l1θ[p←r2θ]) is joinable if there is a term u such that Γ ⊢R r1θ →u and Γ ⊢R (l1θ[p←r2θ]) →u.

We distinguish between different kinds of overlaps and critical pairs:

Definition 4.2

(Permutative Overlaps and CPs) Let Ri = ∇i ⊢li →ri (i = 1, 2) be copies of rewrite rules in eq-closure(Rw), such that there is an overlap. If R2 is a copy of Rπ 1, 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]).

Example 4.3

Consider R = ( ⊢f(X) →f([a]X)). There is an overlap at the root between this rule and its variant R(a b) = ( ⊢f(X) →f([b]X)), i.e., a root-permutative overlap, which is not trivial. It generates the critical pair ⊢ (f([a]X), f([b]X)). Note that the terms f([a]X) and f([b]X) are not α-equivalent. This theory is not confluent; we have for instance:

f(a)⟨R,ϵ,id,[X↦→a]⟩ ⟨R,ϵ,(a b),[X↦→a]⟩f([a]a) ≉αf([b]a)

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 a is not free in s and s rewrites to t then a is not free in t.

Definition 4.4

(Uniformity) We call a nominal rewrite theory R = (Σ, Rw) uniform [7] when if Δ ⊢R s →t and Δ, Δ′ ⊢a#s for some Δ′, then Δ, Δ′ ⊢a#t.

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]:

Definition 4.5

(α-stability) Call a rewrite rule R = ∇⊢l →r α-stable when, for all Δ, π, σ, σ′, Δ ⊢∇σ, ∇πσ′, lσ ≈α lπσ′ implies Δ ⊢rσ ≈α rπσ′.

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

Figure 2: Critical Pair Lemma - case of overlap at a variable position

that closed rules are α-stable. The reverse implication does not hold: for example ⊢f(a) →a is α-stable but not closed.

Theorem 4.6

(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.

Proof

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 ∇⊢s ≈α lπ11 σ1 and s occurs inside lπ22 σ2 under an instance of an unknown (ππ2 · X)σ2 (see Figure 2). Then we can change the action of σ2 over X, replacing s by t, such that ∇⊢t ≈α rπ11 σ1, 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 s by t.

• If there is a root-permutative overlap then joinability follows by α-stability.2

Definition 4.7

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):

Lemma 4.8

Δ ⊢tσ ≈α tθ ⇔∀X ∈unkn(t).Δ ⊢Xσ ≈α Xθ.

Lemma 4.9

If R is a closed rule, then R is α-stable.

Proof

It is sufficient to prove the following property: R = ∇⊢l →r closed and Δ ⊢s ≈α lσ →rσ and Δ ⊢s ≈α lπσ′ →rπσ′ implies Δ ⊢rσ ≈α rπσ′.

The matching problems (∇И⊢ (lИ, rИ)) ?≈ (∇, atms(RИ)#unkn(R) ⊢ (l, r)) and (∇И⊢ (lИ, rИ)) ?≈ (∇π, atms(RИ)#unkn(R) ⊢ (lπ, rπ)) are solvable with solutions θ and θπ, respectively, insofar as R is closed. Hence, we can infer:

• ∇, atms(RИ)#unkn(R) ⊢∇Иθ, (lИθ, rИθ) ≈α (l, r)

• ∇π, atms(RИ)#unkn(R) ⊢∇Иθπ, (lИθπ, rИθπ) ≈α (lπ, rπ)

• Δ ⊢∇σ, ∇πσ′, lσ ≈α lπσ′ =⇒Δ, atms(RИ)#unkn(Rσ) ⊢lИθσ ≈α lИθπσ′

From Lemma 4.8 (⇒), it follows that ∀X ∈unkn(lИ) : Δ, atms(RИ)#unkn(Rσ) ⊢ Xθσ ≈α Xθπσ′.

Since unkn(rИ) ⊆unkn(lИ), Lemma 4.8 (⇐) can be used to demonstrate the equivalences

Δ, atms(RИ)#unkn(Rσ) ⊢rИθσ ≈α rσ, rИθπσ′ ≈α rπσ′, rИθσ ≈α rИθπσ′

and, finally, Δ, atms(RИ)#unkn(Rσ) ⊢rσ ≈α rπσ′ is obtained by transitivity. Notice that atoms in atms(RИ) do not appear in rσ, rπσ′, 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.

Lemma 5.1

Let R = ∇⊢l →r be a rule such that every occurrence of an atom subterm a in l or r is under the scope of an abstraction of a (i.e., no atom occurs free as a subterm in R). Then there exists a minimal context Δ ⊆atms(R)#unkn(R) such that Δ, ∇⊢l →r is closed.

Proof

By definition of closed term (see Definition 3.9), we must check:

(i) Every occurrence of an atom subterm a is under an abstraction of a.

(ii) If π · X occurs under an abstraction of π · a, then any occurrence of π′ · X is in the scope of an abstraction of π′ · a or a#X ∈∇∪Δ.

(iii) For any pair π1 · X, π2 · X occurring in R and a ∈ds(π1, π2), if π1 · a and π1 · a are not abstracted over the respective occurrences of X, then a#X ∈∇∪Δ .

The first point holds by assumption. For the second and third points, if a#X ∉∇ it is sufficient to include a#X in Δ. 2

Lemma 5.2

Suppose R = ∇⊢l →r and R′ = Δ, ∇⊢l →r are rules such that R has no free atom-subterms and Δ ⊆atms(R)#unkn(R) is the minimal set of freshness constraints that makes R′ closed. Then, Γ ⊢s R→c t ⇔ Γ ⊢s R′→c t.

ProofИ The left-to-right direction. If Γ ⊢s R→c t, then Γ, atms(RИ)#unkn(Γ, s, t) ⊢ s R→t, i.e., there is θ such that

Γ, atms(RИ)#unkn(Γ, s, t) ⊢s|p ≈α lИθ, t ≈α s[p←rИθ], ∇Иθ.

Since atms(R) = atms(R′), it suffices to show that Γ, atmsИ(RИ)#unkn(Γ, s, t) ⊢ΔИθ to obtain Γ, atms(RИ)#unkn(Γ, s, t) ⊢s R′→t as required.

To prove Γ, atms(RИ)#unkn(Γ, s, t) ⊢ΔИθ, observe that aИ#XИis in ΔИ if πИ1 · XИ and πИ2 · XИ occur in (lИ, rИ) and at least one of the following holds:

• πИ1 · aИ is abstracted over πИ1 · XИ and πИ2 · aИ is not abstracted over πИ2 · XИ. We know

Γ, atms(RИ)#unkn(Γ, s, t) ⊢πИ2 · aИ#(s|p, t|p), (s|p, t|p) ≈α (lИθ, rИθ).

Then, since πИ2 · aИ is not abstracted over πИ2 · XИ, the same freshness context allows us to derive πИ2 · aИ#πИ2 · XИθ and, consequently, aИ#XИθ.

• aИ is in ds(πИ1, πИ2) and neither πИ1 · aИ nor πИ2 · aИ are abstracted over the respective occurrences of XИ. The same argument is valid in this case.

The right-to-left direction.И If Γ ⊢s R′→c t, then Γ, atms(RИ)#unkn(Γ, s, t) ⊢ s R′→t, i.e., there is θ such that

Γ, atms(R′И)#unkn(Γ, s, t) ⊢s|p ≈α lИθ, t ≈α s[p←rИθ], ∇Иθ, ΔИθ.

So atms(R) = atms(R′). It follows that Γ, atms(RИ)#unkn(Γ, s, t) ⊢s RИ→t. 2

Lemma 5.3

Suppose R = ∇⊢l →r is a nominal rule and there exist Δ, s, t and a closed-rewriting step Δ ⊢s R→c t. Then every occurrence of an atom subterm a in l or r is under an abstraction of a (i.e., no atom occurs free as a subterm in R).

Proof

By contradiction. Assume R has a free atom subterm a; without loss of generality, we assume l|q = a (if it occurs in r we reason in the same way). By definition of closed-rewriting, there exists RИ, a fresh variant of R, such that Δ, atms(RИ)#unkn(Δ, s, t) ⊢s|p ≈α lИθ, t ≈α s[p←rИθ], ∇Иθ. But lИ|q = aИ is free, and aИ does not occur in s, contradicting Δ, atms(RИ)#unkn(Δ, s, t) ⊢s|p ≈α lИθ.2

The following definitions of fresh overlap and fresh critical pair will be used to derive sufficient conditions for confluence of closed rewriting.

Definition 5.4

(Fresh Overlaps and CPs) Let Ri = ∇i ⊢li →ri (i = 1, 2) be freshened versions of rewrite rules in Rw (R1 and R2 could be two freshened versions of the same rule), where unkn(R1)∩unkn(R2) = ∅, as usual. If the nominal unification problem ∇1 ∪∇2 ∪{l2 ?≈? l1|p} has a most general solution ⟨Γ, θ⟩ for some position p, then we say that R1 fresh overlaps with R2, and we call the pair of terms-in-context Γ ⊢ (r1θ, l1θ[p←r2θ]) a fresh critical pair.

If p is a variable position, or if R1 and R2 are equal modulo renaming of variables and p = ϵ, then we call the overlap and critical pair trivial.

If R1 and R2 are freshened versions of the same rule and p = ϵ, 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 Γ ⊢ (r1θ, l1θ[p←r2θ]) is joinable if there is a term u such that Γ ⊢R r1θ →c u and Γ ⊢R (l1θ[p←r2θ]) →c u.

Definition 5.5

Call a rewrite theory R = (Σ, Rw) fresh quasi-orthogonal when all rules are left-linear and there are no proper fresh critical pairs.

Theorem 5.6

(Critical Pair Lemma for Closed Rewriting) Let R = (Σ, Rw) be a rewrite theory where every proper fresh critical pair is joinable. Then the closed rewriting relation generated by R is locally confluent.

Proof

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 Rw do not have free atom-subterms. Consider R′ = (Σ, Rw′) the closed rewrite theory obtained by extending the freshness contexts of rules in Rw, 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 R′. Thus, joinability of proper fresh critical pairs in R implies joinability of proper fresh critical pairs in R′ and it suffices to prove local confluence for the closed rewriting relation generated by R′. Also note that since all rules in Rw′ 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 R1 = ∇И1 ⊢lИ1 →rИ1 and R2 = ∇И2 ⊢lИ2 →rИ2 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 lИ2σ2 with R1 and R2. Without loss of generality, we assume Δ, atms(R1)#unkn(Δ, s) ⊢∇И1σ1, s ≈α lИ1σ1, t ≈α rИ1σ1 and s occurs inside lИ2σ2 under an instance of an unknown (πИ· XИ)σ2. Then we can change the action of σ2 over XИ, replacing s by t, such that ∇1 ⊢t ≈α rπ11 σ1, 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 s by t.

• If there are freshened rules R1 = ∇И1 ⊢lИ1 →rИ1 and R2 = ∇И2 ⊢lИ2 →rИ2 and a term-in-context Δ ⊢s, such that there is a rewrite step at position p1 in s using R1 and at position p2 using R2 then Δ, Γ1 ⊢∇И1σ, lИ1σ ≈α s|p1 and Δ, Γ2 ⊢ ∇И2σ′, lИ2σ′ ≈α s|p2. Without loss of generality we assume that p2 = p1q. Since the sets of variables in the freshened rules are disjoint, without loss of generality we can assume dom(σ) ∩dom(σ′) = ∅, and define the substitution μ = σ ◦σ′ such that dom(μ) = dom(σ) ∪dom(σ′). Then, Δ, Γ1, Γ2 ⊢∇И1μ, ∇И2μ, lИ1|qμ ≈α lИ2μ. Therefore the unification problem ∇И1, ∇И2, lИ1|q ?≈? lИ2 has a solution. Hence, by Definition 5.4, there is a fresh critical pair between R1 and R2. Observe that, if q = ϵ and R1 is a permuted copy of R2 (equal or not), then the terms of divergence t1 and t2 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 (σapp), obtained from ∅⊢ ((λ[a]X)Y )[b↦ →Z], which is not joinable:

∅⊢(((λ[a]X)[b↦ →Z])(Y [b↦ →Z]), (X[a↦ →Y ])[b↦ →Z]).

Next we consider criteria for confluence based on (quasi-) orthogonality. The following lemma is used in the proof of confluence.

Lemma 5.7

Let R = (Σ, Rw) be a closed rewrite theory. Δ ⊢Rs →ct if, and only if, there exist R1, . . . , Rn∈ Rw such that Δ, atms(RИ1, . . . , RИn)#unkn(Δ, s) ⊢R s →t.

Proof

In both directions, the proof is by induction on the number of steps in Δ ⊢R s →c t and Δ, atms(RИ1, . . . , RИn)#unkn(Δ, s) ⊢R s →t, 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 R ∈ Rw can be used in one step Δ, atms(RИ1, . . . , RИn)#unkn(Δ, s) ⊢sR→v. So, the version RИ freshened with respect to Δ, atms(RИ1, . . . , RИn) and all the terms in the rewrite sequence could be taken in this step. Weakening the freshness context, Δ, atms(RИ1, . . . , RИn, RИ)#unkn(Δ, s) ⊢sR→v is obtained. Since the atoms of RИ1, . . . , RИn do not occur in Δ, RИ and in the terms of the rewrite sequence, the freshness context can be strengthened into Δ, atms(RИ)#unkn(Δ, s) ⊢s R→v. Thus, Δ ⊢s R→c v is reached. 2

Theorem 5.8

If R is a fresh-quasi-orthogonal rewrite theory, then the closed rewriting relation generated by R is confluent.

Proof

As in the previous theorem, we prove confluence for the closed rewriting relation generated by R′ = (Σ, Rw′), where Rw′ is obtained by extending the freshness contexts to close the rules of Rw which do not have free atom-subterms (see Lemmas 5.3, 5.1 and 5.2). Since all rules in Rw′ 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 Δ ⊢R′s →ct and Δ ⊢R′s →cv. By Lemma 5.7 (⇒), there exist R1, . . . , Rn ∈Rw′ such that Δ, atms(RИ1, . . . , RИn)#unkn(Δ, s) ⊢R′ s →t and Δ, atms(RИ1, . . . , RИn)#unkn(Δ, s) ⊢R′ s →v. Theorem 28 of [19] guarantees confluence with the context Δ, atms(RИ1, . . . , RИn)#unkn(Δ, s), 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 Δ ⊢R′→c . 2

Example 5.9

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:

⊢¬(X ∧Y ) →¬(X) ∨¬(Y ) and b#X ⊢¬(∀[a]X) →∃[b]¬((b a) · X).

Why write ∃[b]¬((b a)·X) on the right-hand side above, instead of the α-equivalent ∃[a]¬(X)? 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 (b a) 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 ⊢f(a) → 0 and ⊢g(f(b)) → 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 g(f(a)) rewrites to both g(0) and 0. Using closed rewriting, the term g(f(a)) 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. ↩