# Supplementary Material for “Nonlinear magnon polaritons”

Oscar Lee  London Centre for Nanotechnology, University College London, London
WC1H 0AH, United Kingdom  Kei Yamamoto<EMAIL_ADDRESS>Advanced
Science Research Center, Japan Atomic Energy Agency, 2-4 Shirakata, Tokai
319-1195, Japan  Maki Umeda  Advanced Science Research Center, Japan Atomic
Energy Agency, 2-4 Shirakata, Tokai 319-1195, Japan  Institute for Materials
Research, Tohoku University, Sendai 980-8577, Japan  Christoph W. Zollitsch
London Centre for Nanotechnology, University College London, London WC1H 0AH,
United Kingdom  Mehrdad Elyasi  WPI Advanced Institude for Materials Research,
Tohoku University, 2-1-1, Katahira, Sendai 980-8577, Japan  Takashi Kikkawa
Department of Applied Physics, The University of Tokyo, Tokyo 113-8656, Japan
Eiji Saitoh  Advanced Science Research Center, Japan Atomic Energy Agency, 2-4
Shirakata, Tokai 319-1195, Japan  WPI Advanced Institude for Materials
Research, Tohoku University, 2-1-1, Katahira, Sendai 980-8577, Japan
Department of Applied Physics, The University of Tokyo, Tokyo 113-8656, Japan
Institute for AI and Beyond, The University of Tokyo, Tokyo 113-8656, Japan.
Gerrit E. W. Bauer  WPI Advanced Institude for Materials Research, Tohoku
University, 2-1-1, Katahira, Sendai 980-8577, Japan  Hidekazu Kurebayashi
<EMAIL_ADDRESS>London Centre for Nanotechnology, University College
London, London WC1H 0AH, United Kingdom

##  I Experimental geometry and mode profile of the resonator

We employed a combination of the time domain and the eigenmode solvers from
the CST STUDIO SUITE 2021 package to simulate and calculate the response to a
microwave input signal and its corresponding field distributions on the split
ring resonator (SRR) used in our experiments. The schematic and dimensions of
the SRR are shown in Fig. S1(a). A square-shaped resonator that consists an
outer length of $a=10$ mm and an inner width of $b=0.25$ mm with a gap of
distance $c=0.125$ mm has been prepared with a 17.5 $\mu$m double-sided copper
coating, fabricated on a ROGERS RT6010LM substrate of height $h=1.5$ mm with a
relative permittivity $\epsilon_{r}=10.7$ and loss $\tan\delta=2.3\times
10^{-3}$. A 50 $\mathrm{\SIUnitSymbolOhm}$ impedance-matched microstrip line
of width $w=1.5$ mm is inductively coupled to the SRR, separated by a distance
$d=0.125$ mm. Figure S1(b) shows comparison between experimental results of
the microwave absorption parameters $|S_{11}|$ (dotted green) in a vector
network analyser (VNA) and simulated $|S_{11}|$ (blue) and $|S_{21}|$ (red) as
a function of frequency. Between 1 and 4 GHz, two resonance modes at 1.51 and
2.87 GHz are obtained by simulation, which we respectively attribute the lower
and the upper modes as $\omega_{r}{\color[rgb]{0,0,0}/2\pi}$ and $\omega_{\rm
ref}{\color[rgb]{0,0,0}/2\pi}$. From our experimental $|S_{11}|$ data (green)
with the YIG sample placed on the SRR (see Fig. 1(c) in main text), we find
$\omega_{r\rm(exp)}{\color[rgb]{0,0,0}/2\pi}=1.53$ and $\omega_{\rm
ref(exp)}{\color[rgb]{0,0,0}/2\pi}=3.09$ GHz. Although a trivial shift of
$\omega_{\rm ref}$ mode is observed (difference $\approx
7.1\leavevmode\nobreak\ \%$), we notice that the resonance frequency of
$\omega_{r}$ mode is hardly affected (difference $\approx
1.3\leavevmode\nobreak\ \%$) when the sample is introduced. In Figs.
S1(c)-(e), we respectively show the local distributions for different magnetic
field components $H_{x}$, $H_{y}$ and $H_{z}$ of the $|S_{11}|$ mode at
$\omega=\omega_{r}$ (left) and $\omega=\omega_{\rm ref}$ (right). At the
resonance frequency, as the microwave currents are flown through the
microstrip line, the energy transfer of the electromagnetic fields are
absorbed by the SRR, which subsequently induces an oscillating magnetic field
excitation in its local geometry.

Figure S1: (a) Schematic drawing of the SRR used in the experimental setup.
(b) Calculated microwave reflection and transmission spectra ($|S_{11}|$ and
$|S_{21}|$) as a function of frequency of dimensions depicted in (a). (c)-(e)
Surface plots of local magnetic field distribution components for (c) $H_{x}$,
(d) $H_{y}$ and (e) $H_{z}$ of the $|S_{11}|$ mode at the primary
($\omega_{r}/2\pi=1.51$ GHz) (left) and the secondary ($\omega_{\rm
ref}/2\pi=2.87$ GHz) (right) mode frequencies, respectively.

##  II Spin wave dispersion in the YIG film

The YIG film used in the experiment is $d=5\ \mu$m thick with magnetic-field
($\mu_{0}H$) dependent dispersion relation Kalinikos_SPJ1981

$\omega_{n\bm{k}}\left(H\right)=\mu_{0}\gamma\sqrt{\left\\{H+M_{\rm
s}\left(1+\lambda_{\rm ex}k_{n}^{2}-P_{n}\right)\right\\}\left\\{H+M_{\rm
s}\left(\lambda_{\rm ex}k_{n}^{2}+P_{n}\sin^{2}\phi\right)\right\\}}.$ (S1)

Here $M_{\rm s}$, $\gamma$, $\lambda_{\rm ex}$ are the saturation
magnetization, gyromagnetic ratio and stiffness constant, respectively.
$\bm{k}=(k_{x},k_{y})^{T}=k(\cos\phi,\sin\phi)^{T}$ denotes the wavevector in
the plane, $n\pi/d,n\in\mathbb{Z}$ is the quantized out-of-plane component
such that $k_{n}^{2}=k^{2}+(n\pi/d)^{2}$, and

$P_{n}=\frac{k^{2}}{k_{n}^{2}}-\frac{2}{1+\delta_{0n}}\frac{k^{4}}{k_{n}^{4}}\frac{1-(-1)^{n}{\rm
e}^{-kd}}{kd}$ (S2)

for free surface boundary conditions.

To compute the threshold field value $H_{\rm cr}$ for the occurrence of three-
magnon splitting, we study the backward volume wave branch $\phi=0$ without a
node in the thickness direction $n=0$, which has the lowest resonance
frequency. For each given value of $H$, the energy-momentum conservation
requires

$H\left(H+M_{\rm s}\right)=4\left(H+M_{\rm s}\lambda_{\rm
ex}k^{2}\right)\left\\{H+M_{\rm s}\left(\lambda_{\rm ex}k^{2}+\frac{1-{\rm
e}^{-kd}}{kd}\right)\right\\}.$ (S3)

The condition on $k$ for $\omega_{n\bm{k}}\left(H\right)$ to be the bottom of
dispersion is

$\left(4\lambda_{\rm ex}k^{2}+{\rm e}^{-kd}-\frac{1-{\rm
e}^{-kd}}{kd}\right)H+\left(4\lambda_{\rm ex}k^{2}+{\rm e}^{-kd}+\frac{1-{\rm
e}^{-kd}}{kd}\right)M_{\rm s}\lambda_{\rm ex}k^{2}=0.$ (S4)

The simultaneous solution of Eqs. (S3) and (S4) for $(H,k)$ determines $H_{\rm
cr}$ and the associated $k_{\rm cr}$ that minimizes
$\omega_{n\bm{k}}\left(H_{\rm cr}\right)$.

Figure S2: (a) Magnetic field dependence of microwave resonance frequency
$\omega_{0}/2\pi$. The dots indicate the experimental data in combination with
the Kittel fit shown by dashed yellow lines. The solid green curve is the
calculated spin wave dispersion obtained by Eq. (S1) for the lowest energy
mode, $n=0$. The dashed red line represents the onset frequency of the three-
magnons. (b) $\omega_{0}/4\pi$ and ${\color[rgb]{0,0,0}\omega_{\rm b}/2\pi}$
as a function of magnetic field. The intersection point corresponds to the
critical field $\mu_{0}H_{\rm cr}$ for the onset of three-magnon splitting and
half the onset frequency. (c) Magnon dispersion relationships in YIG of
thickness $5\ \mu$m for different external magnetic fields for
$\pm\bm{k}\parallel\bm{H}$ calculated using Eq. (S1).

In order to estimate the value of $M_{s}$ for our sample, we performed
broadband spin wave spectroscopy measurements with our YIG sample placed on a
co-planar waveguide (CPW). $|S_{11}|$ spectra were measured by the VNA for
various magnetic fields. We extracted the ferromagnetic resonance (FMR) peak
frequency $\omega_{0}{\color[rgb]{0,0,0}/2\pi}$ from each scan and plot them
in Fig. S2(a). We first fitted the resonance data with the Kittel formula
$\omega_{0}=\mu_{0}\gamma\sqrt{H(H+M_{\rm s})}$, and extracted $M_{\rm
s}=1.{\color[rgb]{0,0,0}26}\times 10^{5}$ A/m. Note that for $n=0$ and
$k\rightarrow 0$, Eq. (S1) reduces to the Kittel formula.

We now evaluate $H_{\rm cr}$ and $\omega_{0\bm{k}}\left(H_{\rm cr}\right)$. In
Fig. S2(b), we plot half the magnon frequency $\omega_{0}/4\pi$ and the
minimum magnon dispersion frequency $\omega_{\rm b}/2\pi$ as a function of
magnetic field, calculated using Eq. S1 with $\gamma=2\pi\times 28$ GHz/T and
$\lambda_{\rm ex}=3\times 10^{-16}$ m2 Stancil_book2008 . The onset condition
of three-magnon splitting is satisfied when
$\omega_{0}/2={\color[rgb]{0,0,0}\omega_{\rm b}}$, which corresponds to the
crossing point in this plot. The numerical solution of Eqs. (S3) and (S4)
yields

$k_{\rm cr}=5.38\ [{\rm rad/\mu m}],\quad\mu_{0}H_{\rm
cr}={{\color[rgb]{0,0,0}40.9}}\ [{\rm
mT}],\quad\frac{\omega_{0\bm{k}}\left(H_{\rm
cr}\right)}{2\pi}\bigg{|}_{\bm{k}\rightarrow\bm{0}}={{\color[rgb]{0,0,0}2.59}}\
[{\rm GHz}],$ (S5)

which gives the coordinate value of the crossing point. The latter value of
the critical frequency is quoted in the main text. We identify
$\omega_{0\bm{k}}|_{\bm{k}\rightarrow\bm{0}}{\color[rgb]{0,0,0}/2\pi}$ to be
the Kittel mode frequency and denote it by
$\omega_{0}{\color[rgb]{0,0,0}/2\pi}$. Finally, we plot in Fig. S2(c) the spin
wave dispersion for different magnetic fields, i.e. the first anticrossing
(16.8 mT), $\mu_{0}H_{\rm cr}$, and the second anticrossing (60 mT), to
highlight the presence and absence of spin-wave modes with
${\color[rgb]{0,0,0}\omega_{0\bm{k}}=}\omega_{0}/2$.

##  III Data processing methods

To extract the magnetization properties including the resonance frequency
($\omega_{0}{\color[rgb]{0,0,0}/2\pi}$) and the linewidth
(${\color[rgb]{0,0,0}\kappa_{0}}/2\pi$), we initially followed the usual
procedure in which the measured microwave absorption spectra $|S_{11}|$ (dB)
were first translated into a linear scale to obtain $\tilde{|S_{11}|}$ (=
$10^{{\color[rgb]{0,0,0}|S_{11}|}/10}$). Subsequently, the converted data was
fit using a double Lorentzian profile:

${\color[rgb]{0,0,0}\tilde{|S_{11}|}}\propto\frac{A_{1}\Delta\omega_{1}}{(\omega-\omega_{1})^{2}+\Delta\omega_{1}^{2}}+\frac{A_{2}\Delta\omega_{2}}{(\omega-\omega_{2})^{2}+\Delta\omega_{2}^{2}}+C$
(S6)

where $\omega$, $\omega_{n}$, $A_{n}$, $\Delta\omega_{n}$, and $C$ correspond
to the frequency, resonance position, relative amplitude, linewidth, and the
spectra offset, respectively. Here, $n$ denotes the first and the secondary
peaks.

Figure S3: Linear microwave absorption spectra ($\tilde{|S_{11}|}$) as a
function of frequency (a) at various magnetic fields at a fixed microwave
power (-20 dBm) and (b) for different microwave powers at a fixed magnetic
field at the avoided crossing point (16.8 mT). Red curves are the fits by Eq.
(S6).

In Figs. S3(a) and (b), we respectively show the individual fitting results of
the fields used in the main text at -20 dBm, and for different microwave
powers at the avoided crossing field (16.8 mT). As can be seen in Fig.S3(a),
the lines look like a well separated double Lorentzian at $\mu_{0}H=26.1$ mT,
and the linewidth $\Delta\omega_{2}/2\pi$ extracted from this fitting,
interpreted as the linewidth $\kappa_{0}/2\pi$ of uncoupled Kittel magnon, has
been used in Fig. 2(e) in the main text. When the hybridization is strong at
$\mu_{0}H=16.8$ mT, however, the dip between the two peaks is quite shallow
even at low input powers. Comparing Fig. S3(b) with Fig. 2(c) in the main
text, one can recognize that the dB unit (by design) is more suitable for
quantifying the hybridization gap and its closure at high input powers.
Therefore, for the sake of peak frequency determination only, we fitted the dB
unit data by the same double Lorentzian (S6) instead of the linearized data
and used the result for Fig. 2(d). Furthermore, Fig. S3(b) indicates that
beyond 0 dBm, there is essentially a single peak so that the double Lorentzian
fitting is expected to give misleading results. Indeed, we found that the
fitting generates values of $\omega_{2}/2\pi$ wildly off the main peak
frequency $\omega_{1}/2\pi\approx 1.52$ GHz. Whenever this happens, we also
have $\left|A_{2}\right|\ll\left|A_{1}\right|$, which implies that the fitting
of the second peak does not affect the agreement between the curve and the
data points. To avoid confusions, therefore, we removed the experimental data
points for $\omega_{2}$ above 2 dBm in Fig. 4(d).

##  IV Details of the theoretical calculations

In this section, we describe the theory that leads to Eqs. (4) - (6) and Figs.
2(d), 2(e), 4(a) and 4(b) in the main text. For convenience of the reader, we
repeat the model Hamiltonian

$\displaystyle\mathcal{H}=$
$\displaystyle\omega_{0}b_{0}^{\dagger}b_{0}+\sum_{\bm{k}\neq\bm{0}}\omega_{\bm{k}}b_{\bm{k}}^{\dagger}b_{\bm{k}}+\omega_{r}b_{r}^{\dagger}b_{r}+\left[gb_{0}^{\dagger}b_{r}+h{\rm
e}^{-i\omega t}\left(U_{0}b_{0}^{\dagger}+U_{r}b_{r}^{\dagger}\right)+{\rm
h.c.}\right]$
$\displaystyle+\frac{1}{2}\sum_{\bm{k}\neq\bm{0}}\left(\overline{V}_{\bm{k}}b_{0}b_{\bm{k}}^{\dagger}b_{-\bm{k}}^{\dagger}+{\rm
h.c.}\right)+{\color[rgb]{0,0,0}\frac{1}{2}\sum_{\bm{k},\bm{k}^{\prime}}\left(2T_{\bm{k}\bm{k}^{\prime}}b_{\bm{k}}^{\dagger}b_{\bm{k}^{\prime}}^{\dagger}b_{\bm{k}}b_{\bm{k}^{\prime}}+S_{\bm{k}\bm{k}^{\prime}}b_{\bm{k}}^{\dagger}b_{-\bm{k}}^{\dagger}b_{\bm{k}^{\prime}}b_{-\bm{k}^{\prime}}\right)}.$
(S7)

For brevity, we define $\mathcal{H}$ to have the unit of angular frequency.
Throughout this section and the next, “frequency” and “magnetic field” refer
to angular frequency and $\bm{H}$ instead of $\bm{B}=\mu_{0}\bm{H}$
respectively, as is conventional in theoretical literature. The first line
describes the usual linear theory of Kittel mode magnon in a microwave cavity
augmented by the single particle energy of propagating magnons. The first term
in the second line represents the three-magnon interaction arising from the
magnetic dipole-dipole interactions, where the coupling constant in a
sufficiently thick film is given by

$V_{\bm{k}}=\omega_{M}\sqrt{\frac{g_{\rm eff}\mu_{B}}{2\mathcal{V}M_{\rm
s}}}\left(1+\frac{\omega_{\bm{k}}}{A_{\bm{k}}+\left|B_{\bm{k}}\right|}\right)\frac{k_{x}\left(k_{y}+ik_{z}\right)}{k^{2}},\quad\omega_{M}=\mu_{0}\gamma
M_{\rm s},$ (S8)

with $g_{\rm eff}$ the g-factor, $\mu_{B}$ the Bohr magneton, $\mathcal{V}$
the volume of the magnet, $k^{2}=k_{x}^{2}+k_{y}^{2}+k_{z}^{2}$, and
$A_{\bm{k}},B_{\bm{k}}$ the Bogoliubov coefficients for the magnon eigenstates

$A_{\bm{k}}=\mu_{0}\gamma\left(H+M_{\rm s}\lambda_{\rm ex}k^{2}+M_{\rm
s}\frac{k_{y}^{2}+k_{z}^{2}}{2k^{2}}\right),\quad B_{\bm{k}}=\mu_{0}\gamma
M_{\rm s}\frac{\left(k_{y}+ik_{z}\right)^{2}}{2k^{2}},$ (S9)

with which the eigenfrequency can be written as
$\omega_{\bm{k}}=\sqrt{A_{\bm{k}}^{2}-B_{\bm{k}}^{2}}$. This expression could
be significantly modified for film thicknesses of a few micrometers, but the
detailed form is uncomputable as well as unnecessary. We only assume
$V_{-\bm{k}}=V_{\bm{k}}$, which is expected unless the sample shape breaks the
inversion symmetry. We set the $x$-axis along the external static magnetic
field $H$, the $z$-axis along the film normal, and ignore the crystalline
anisotropy so that the ground state magnetization is in the $x$ direction. The
Heisenberg Hamiltonian gives rise to many other nonlinear interaction terms
between different spin waves, which were all neglected in the main text. Most
of them can be removed by a suitable nonlinear transformation of $b_{\bm{k}}$
Zakharov . The only _resonant_ contributions up to fourth order in
$b_{\bm{k}}$, which cannot be dismissed in this way and are relevant under
spatially uniform driving, are the latter two terms in the second line in Eq.
(S7). The expressions for $T_{\bm{k}\bm{k}^{\prime}}$ and
$S_{\bm{k}\bm{k}^{\prime}}$ are complicated L'vov , but their generic order of
magnitude estimate is $T_{\bm{k}\bm{k}^{\prime}}\sim
S_{\bm{k}\bm{k}^{\prime}}\sim\omega_{M}/N\ll
V_{\bm{k}}\sim\omega_{M}/\sqrt{N}$ in the GHz range, where $N$ is the number
of spins in the sample. Therefore, the three-magnon processes usually
dominate, which we assume to be the case. Nevertheless, we do keep
$S_{\bm{k}\bm{k}^{\prime}}$, which gives a minor correction to the spectrum,
but does turn out to improve the agreement with the experimental data. In
contrast, retaining $T_{\bm{k}\bm{k}^{\prime}}$ did not change the result in
any significant way and we discard them for simplicity.

In our convention, the Heisenberg equation of motion reads
$dA/dt=i[\mathcal{H},A]$, which yields

$\displaystyle i\left(\frac{d}{dt}+{\color[rgb]{0,0,0}\kappa_{r}}\right)b_{r}$
$\displaystyle=$ $\displaystyle\omega_{r}b_{r}+\overline{g}b_{0}+hU_{r}{\rm
e}^{-i\omega t}+\xi_{r},$ (S10) $\displaystyle
i\left(\frac{d}{dt}+{\color[rgb]{0,0,0}\kappa_{0}}\right)b_{0}$
$\displaystyle=$
$\displaystyle{\color[rgb]{0,0,0}\left(\omega_{0}+S_{00}\left|b_{0}\right|^{2}\right)}b_{0}+gb_{r}+hU_{0}{\rm
e}^{-i\omega
t}+\frac{1}{2}\sum_{\bm{k}}{\color[rgb]{0,0,0}\left(V_{\bm{k}}+2S_{0\bm{k}}\overline{b_{0}}\right)}b_{\bm{k}}b_{-\bm{k}}+\xi_{0},$
(S11) $\displaystyle i\left(\frac{d}{dt}+\eta_{\bm{k}}\right)b_{\bm{k}}$
$\displaystyle=$
$\displaystyle\omega_{\bm{k}}b_{\bm{k}}+\left(\overline{V_{\bm{k}}}b_{0}+\sum_{\bm{k}^{\prime}}S_{\bm{k}\bm{k}^{\prime}}b_{\bm{k}^{\prime}}b_{-\bm{k}^{\prime}}\right)\overline{b_{-\bm{k}}}+\xi_{\bm{k}}.$
(S12)

In writing down these equations, we have made a few important alterations to
the setup. First of all, the quantum mechanical operators $b_{r,0,\bm{k}}$
have all been relegated to stochastic random variables, and accordingly the
Hermitian conjugation $b^{\dagger}$ has been replaced by the complex
conjugation $\overline{b}$. It is justifiable at room temperature where
quantum fluctuations are overwhelmed by the thermal fluctuations. Second, we
have introduced phenomenologically the relaxation rates
$\kappa_{r,0},\eta_{\bm{k}}$ that are equal to the frequency linewidth of the
respective modes in the linear and uncoupled regime, and added them to the
time derivatives on the left-hand-sides. Corresponding to the relaxation is
the random noise fields $\xi_{r,0,\bm{k}}$ that have vanishing average
$\langle\xi_{r,0,\bm{k}}\rangle=0$. We assume their higher-order correlations
are Gaussian and dictated by the fluctuation-dissipation theorem for
$g=V_{\bm{k}}=S_{\bm{k}\bm{k}^{\prime}}=0$ for simplicity:

$\left\langle\overline{\xi_{\bm{k}}\left(t\right)}\xi_{\bm{k}^{\prime}}\left(t^{\prime}\right)\right\rangle=2\eta_{\bm{k}}N_{\bm{k}}\delta_{\bm{k}\bm{k}^{\prime}}\delta\left(t-t^{\prime}\right),\quad
N_{\bm{k}}=\frac{k_{B}T}{\hbar\omega_{\bm{k}}},$ (S13)

and similarly for
$\langle\overline{\xi_{0}}\xi_{0}\rangle,\langle\overline{\xi_{r}}\xi_{r}\rangle$
with all the other correlations being zero. The number of magnons $N_{\bm{k}}$
is assumed to obey Rayleigh-Jeans distribution in the high-temperature
approximation. Finally, we retained only those nonlinear terms that
potentially are resonant in the three-magnon processes, eliminating some
possible four-magnon terms. It is a working hypothesis in anticipation that
the first-order Suhl instability generically precedes the second-order one for
$H<H_{\rm cr}$.

Experimentally, we measure the microwave reflection which is ideally equal to
1 minus the appropriately normalized work per unit time done by the external
driving $h$. In order to calculate it, we only need the expectation values of
$b_{r,0}$ that oscillate at the driving frequency $\omega$. Therefore, we
follow Suhl Suhl and introduce the rotating frame variables

$c_{r,0}=\left\langle b_{r,0}\right\rangle{\rm e}^{-i\omega t}.$ (S14)

For the traveling magnons, it turns out that the convenient variables are
quadratic correlators

$s_{\bm{k}}=\left\langle b_{\bm{k}}b_{-\bm{k}}\right\rangle,\quad
n_{\bm{k}}=\left\langle\left|b_{\bm{k}}\right|^{2}\right\rangle.$ (S15)

Foreseeing the subsequent development, let us define the critical amplitude
for the Kittel mode by

$c_{\rm
cr}=\frac{1}{V_{\bm{k}}}\left(\omega_{\bm{k}}-\frac{\omega}{2}+i\eta_{\bm{k}}\right).$
(S16)

It turns out that for each given $\omega$, the modes with $\bm{k}$ that
minimizes $\left|c_{\rm cr}\right|$ become unstable first as the input power
(i.e. $\left|h\right|$) is increased. Unless $h$ gets too large beyond a
threshold, these remain the only modes that pick up a non-vanishing
$s_{\bm{k}}$. This conclusion is reached by studying a zero-temperature
formulation which is not a straightforward low-temperature limit of the
nonzero-temperature version used here, so that we do not present the details.
The reader is referred to Ref. L'vov . We just assume that there is only a
single pair $\pm\bm{k}$ of wavevectors that minimizes $\left|c_{\rm
cr}\right|$ and drop the summation over $\bm{k}$. This assumption is
reasonable when the symmetry of the system is low, but cannot be fully
justified due to remaining discrete symmetries, accidental degeneracies, $h$
possibly being significantly above the threshold etc.. We take it as another
working hypothesis, supported again by the good agreement with the
experimental data. We try and find a stationary state, i.e. a non-trivial
time-independent solution for $c_{r,0},s_{\bm{k}},n_{\bm{k}}$. After a
straightforward algebra, ignoring the four-magnon contribution, one obtains

$\left\\{\omega-\omega_{0}+i{\color[rgb]{0,0,0}\kappa_{0}}-\frac{\left|g\right|^{2}}{\omega-\omega_{r}+i{\color[rgb]{0,0,0}\kappa_{r}}}+\frac{V_{\bm{k}}N_{\bm{k}}c_{\rm
cr}}{\left|c_{\rm
cr}\right|^{2}-\left|c_{0}\right|^{2}}\right\\}c_{0}=\left(U_{0}+\frac{gU_{r}}{\omega-\omega_{r}+i{\color[rgb]{0,0,0}\kappa_{r}}}\right)h,$
(S17)

along with Eqs. (5) and (6) in the main text. It further reduces to a real
cubic equation for $\left|c_{0}\right|^{2}$, but the closed-form solution is
not very illuminating. We ultimately resorted to numerical solutions while
restoring the relevant four-magnon terms, which were used to generate Figs.
4(a) and 4(b) in the main text. However, one can guess the qualitative
behavior of the solution as a function of $h$ by inspection. For $h\rightarrow
0$, there is clearly only one positive root for
$\left|c_{0}\right|^{2}\propto\left|h\right|^{2}$ that represents the usual
FMR solution. It remains a good approximation as long as
$\left|c_{0}\right|^{2}\ll\left|c_{\rm cr}\right|^{2}$. When the latter
condition ceases to be valid, the third-term on the left-hand-side starts
growing. Note that this term grows indefinitely as $\left|c_{0}\right|$
approaches $\left|c_{\rm cr}\right|$ from below. Therefore, however large
$\left|h\right|$ becomes on the right-hand-side, there is always a solution
$\left|c_{0}\right|$ that is close to but no greater than $\left|c_{\rm
cr}\right|$. It is easy to convince oneself that this solution continuously
evolves out of the usual FMR solution at low power. Thus we are led to
conclude that the Kittel mode amplitude saturates at $\left|c_{\rm cr}\right|$
in the high-power limit. It also tells that at nonzero temperatures, the
instability is not a clear threshold process, but it occurs continuously as
the input power is increased. The phase information can also be read off from
Eq. (S17) and Eq. (5) in the main text, which yields Eq. (4) of the main text.
Note that as a function of $\omega$, $c_{0}$, and therefore $c_{r}$ and
$n_{\bm{k}},s_{\bm{k}}$, cannot be approximated by simple combinations of
Lorentzian functions since the denominator $\left|c_{\rm
cr}\right|^{2}-\left|c_{0}\right|^{2}$ also gives a rapidly varying
contribution in addition to the usual $\omega-\omega_{0}+i\kappa_{0}$ and
$\omega-\omega_{r}+i\kappa_{r}$.

The discussion above implicitly assumes that the unstable mode has a fixed
$\bm{k}$ independent of the input amplitude $\left|h\right|$. It is in general
false and the value of $\bm{k}$ continuously evolves as $\left|h\right|$
increases according to a complicated optimization dictated by
$\bm{k}$-dependences of $\omega_{\bm{k}},\eta_{\bm{k}}$, and $V_{\bm{k}}$
L'vov . It is practically impossible to be quantitative about all of them,
however. Therefore we ignore these $\bm{k}$-dependences, which is expected to
capture the qualitative trend. Generally, inclusion of the
$\bm{k}$-dependences should slow down the development of instability as a
function of $h$ since the nonlinear correction shifts the unstable $\bm{k}$
value from the one that has the optimal condition exactly at the threshold
power. In Fig. 2(e), the theory overestimated the nonlinear growth of the
linewidth, which may partially be attributed to this simplification in our
model.

We have so far been ambiguous about the driving field amplitude $h$, and it
has to be specified for simulations. Here by convention $h$ is taken to have
the dimension of frequency, which means $U_{r,0}$ are dimensionless. The
threshold value of $h$ for zero temperature is a mess in the general setup. To
provide a theoretically convenient normalization, we introduce the threshold
field $h_{\rm cr}$ defined for $g=0$:

$h_{\rm
cr}=\frac{\omega-\omega_{0}+i{\color[rgb]{0,0,0}\kappa_{0}}}{U_{0}}\frac{\omega/2-\omega_{\bm{k}}+i\eta_{\bm{k}}}{\overline{V_{\bm{k}}}}.$
(S18)

It gives an order of magnitude estimate for the relevant input power range,
but we do not attach a direct physical meaning to it since the absolute value
of $U_{0}$ is not easily obtainable from the experimental data. The ratio
$U_{0}/U_{r}$ affects the lineshape in an essential way, however, as explained
further in the next section. After experimenting with different values, we
fixed $U_{0}/U_{r}={\color[rgb]{0,0,0}0.1+0.3i}$ which gave a reasonable
comparison with Fig. 3(c) in the main text.

To compare the theory with the experimentally measured
${\color[rgb]{0,0,0}\left|S_{11}\right|}=10\log_{10}R$, we need an estimate
for the reflection coefficient $R$ that is the reflected power divided by the
input power. Since there is no transmission line in our device, the reflected
power is equal to the input power $P_{\rm in}$ minus the power dissipated
$P_{d}$ in the device, namely $R=1-P_{d}/P_{\rm in}$. By definition $0<R<1$
and therefore ${\color[rgb]{0,0,0}\left|S_{11}\right|}<0$. The experimental
data suggest that $R\approx 1$ away from the resonance and $R\approx 0$ at the
peak of the resonance. The former implies that the loss from dynamical
entities other than the magnons and photons is very small so that one can
reasonably estimate $P_{d}$ by the dissipation rate of the magnons and
photons:

$P^{\rm
theoretical}_{d}\sim{\color[rgb]{0,0,0}\kappa_{0}}\left|c_{0}\right|^{2}+{\color[rgb]{0,0,0}\kappa_{r}}\left|c_{r}\right|^{2}+2\eta_{\bm{k}}n_{\bm{k}}.$
(S19)

All the quantities on the right-hand-side can be readily computed as functions
of $H,\omega$ and $h$ once the model parameters are fixed. To compare the
calculation with the experiment, however, we need an expression for $P_{\rm
in}$, which is difficult to model theoretically. Here we take a
phenomenological approach by observing that in the experimental data the
minimum value of ${\color[rgb]{0,0,0}\left|S_{11}\right|}$ is roughly -30 dB
regardless of the input power. We choose $P_{\rm in}$ for each $h$ such that
the computed minimum for $|S_{11}|$ is equal to -30 dB:

$S_{11}^{\rm
theoretical}=-10\log_{10}\left(1-\frac{\left(1-10^{-3}\right)P^{\rm
theoretical}_{d}}{\max_{H,\omega}\left[P^{\rm
theoretical}_{d}\right]}\right),$ (S20)

As explained after Eq. (S16), the wave vector $\bm{k}$ of the magnon pair that
become unstable is determined by minimizing $\left|c_{\rm cr}\right|$ for each
$\omega$. Therefore, in computing the $\omega$-dependence of $P_{d}^{\rm
theoretical}$, one in principle has to treat $\bm{k}$ as a function of
$\omega$. To do it, one would again need to know the $\bm{k}$-dependence of
$V_{\bm{k}}$ and $\eta_{\bm{k}}$. As stated above, it is impracticable and we
set both $V_{\bm{k}}$ and $\eta_{\bm{k}}$ as well as
$S_{\bm{k}\bm{k}^{\prime}}$ to be independent of $\bm{k}$ and fix their values
as

$V_{\bm{k}}=\omega_{M}\sqrt{\frac{2g_{\rm eff}\mu_{B}}{\mathcal{V}M_{\rm
s}}},\quad\eta_{\bm{k}}=\alpha\frac{\omega_{0}}{2},\quad{\color[rgb]{0,0,0}S_{\bm{k}\bm{k}}=S_{0\bm{k}}=10S_{00}=\omega_{M}\frac{2g_{\rm
eff}\mu_{B}}{\mathcal{V}M_{s}}}$ (S21)

where the magnon Gilbert damping $\alpha=0.01$ has been introduced and the
sample volume is taken to be

$\mathcal{V}=\frac{2g_{\rm eff}\mu_{B}}{M_{\rm s}}\times 10^{11}.$ (S22)

Note that the prefactor on the right-hand-side would equal twice the volume of
the unit cell if the magnet was a simple ferromagnet. With $V_{\bm{k}}$ and
$\eta_{\bm{k}}$ being constants, the minimum of $\left|c_{\rm cr}\right|$
occurs always at $\omega_{\bm{k}}=\omega/2$. For Kittel mode, we decided to
use a constant damping $\kappa_{0}$ independent of $\omega$ instead of the
Gilbert type as usually assumed, since the FMR linewidth away from the photon-
magnon hybridization appears very weakly dependent of $\omega$, indicating
that the disorder-induced two-magnon conbtribution dominates $\kappa_{0}$.
While the experimental value at $\mu_{0}H=26.1$ mT is $\kappa_{0}=28$ MHz, it
is field-dependent and appears to hit minimum $\kappa_{0}=22$ MHz at
$\mu_{0}H\approx 50$ MHz, which was used in the numerical simulaitons.
Finally, the reference driving field $h_{\rm ref}$ has been taken equal to
$h_{\rm cr}$ evaluated at $\omega=\omega_{0}$ and $\mu_{0}H=15$ mT.

##  V Asymmetry of spectral shapes in the presence of damping

In the experiment, at low input powers where the system should be described by
the linear response theory, we consistently observed that the two peaks of
reflection spectrum as a function of $\omega$ for fixed $H$ have different
heights even when $H$ is tuned such that the distance between the two peaks is
minimized. Further, the peak frequencies do not appear equidistant from the
degenerate resonance frequency in the absence of the coupling, which is equal
to the resonator eigenfrequency at $H=0$ or $H=\infty$. Here we show that this
asymmetry can be attributed to the fact that the system is only marginally in
the strong coupling regime and the distortion of the spectral line shapes by
the nonzero linewidths cannot be ignored.

Since nonlinearity is irrelevant in the present discussion, we begin with the
linearized versions of Eqs. (S10) and (S11);

$\begin{pmatrix}\omega-\omega_{r}+i{\color[rgb]{0,0,0}\kappa_{r}}&-\overline{g}\\\
-g&\omega-\omega_{0}+i{\color[rgb]{0,0,0}\kappa_{0}}\\\
\end{pmatrix}\begin{pmatrix}b_{r}\\\ b_{0}\\\
\end{pmatrix}=h\begin{pmatrix}U_{r}\\\ U_{0}\\\ \end{pmatrix}$ (S23)

Solving it for $b_{r,0}$ yields

$\displaystyle b_{r}$ $\displaystyle=$
$\displaystyle\frac{\left(\omega-\omega_{0}+i\kappa_{0}\right)U_{r}+\overline{g}U_{0}}{\left(\omega-\omega_{r}+i\kappa_{r}\right)\left(\omega-\omega_{0}+i\kappa_{0}\right)-\left|g\right|^{2}}h,$
(S24) $\displaystyle b_{0}$ $\displaystyle=$
$\displaystyle\frac{\left(\omega-\omega_{r}+i\kappa_{r}\right)U_{0}+gU_{r}}{\left(\omega-\omega_{r}+i\kappa_{r}\right)\left(\omega-\omega_{0}+i\kappa_{0}\right)-\left|g\right|^{2}}h.$
(S25)

The total absorbed power should be given by

$P=\kappa_{r}\left|b_{r}\right|^{2}+\kappa_{0}\left|b_{0}\right|^{2},$ (S26)

which is the rate of energy dissipation in the stationary state. We are
interested in the resonance of the two modes where $\omega_{0}=\omega_{r}$.
The power absorption becomes

$\displaystyle P$ $\displaystyle=$ $\displaystyle
h^{2}\left[\left\\{\left(\omega-\omega_{0}\right)^{2}-\kappa_{r}\kappa_{0}-\left|g\right|^{2}\right\\}^{2}+\left(\omega-\omega_{0}\right)^{2}\left(\kappa_{0}+\kappa_{r}\right)^{2}\right]^{-1}$
$\displaystyle\times\left\\{\left(\kappa_{r}\left|U_{r}\right|^{2}+\kappa_{0}\left|U_{0}\right|^{2}\right)\left(\omega-\omega_{0}\right)^{2}+2\left(\kappa_{0}+\kappa_{r}\right)\Re\left[gU_{r}\overline{U_{0}}\right]\left(\omega-\omega_{0}\right)+\left(\kappa_{r}\kappa_{0}+\left|g\right|^{2}\right)\left(\kappa_{0}\left|U_{r}\right|^{2}+\kappa_{r}\left|U_{0}\right|^{2}\right)\right\\}.$

Let us first examine how the peak-frequency positions are affected by the
nonzero linewidths. If $\kappa_{0},\kappa_{r}\ll\left|g\right|$, the first
line in Eq. (V) varies far more rapidly than the second line near the
resonance so that the resonance frequencies would be given by

$\omega_{\pm}=\omega_{0}\pm\sqrt{\left|g\right|^{2}-\frac{\kappa_{0}^{2}+\kappa_{r}^{2}}{2}}\approx\omega_{0}\pm\left|g\right|.$
(S28)

However, when $\kappa_{0},\kappa_{r}$ are comparable to $\left|g\right|$, the
$\omega$-dependence of the second line cannot be ignored _a priori_. A
necessary condition for a resonance frequency is $dP/d\omega=0$, which can be
written as

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\bigg{\\{}\left(\kappa_{r}\left|U_{r}\right|^{2}+\kappa_{0}\left|U_{0}\right|^{2}\right)\left[\left(\omega-\omega_{0}\right)^{4}-\left(\left|g\right|^{2}+\kappa_{r}\kappa_{0}\right)^{2}\right]$
(S29)
$\displaystyle+\left(\kappa_{0}\left|U_{r}\right|^{2}+\kappa_{r}\left|U_{0}\right|^{2}\right)\left(\left|g\right|^{2}+\kappa_{r}\kappa_{0}\right)\left[2\left\\{\left(\omega-\omega_{0}\right)^{2}-\left|g\right|^{2}\right\\}+\kappa_{r}^{2}+\kappa_{0}^{2}\right]\bigg{\\}}\left(\omega-\omega_{0}\right)$
$\displaystyle+\left(\kappa_{r}+\kappa_{0}\right)\Re\left[gU_{r}\overline{U_{0}}\right]\left\\{3\left(\omega-\omega_{0}\right)^{4}-\left(2\left|g\right|^{2}-\kappa_{r}^{2}-\kappa_{0}^{2}\right)\left(\omega-\omega_{0}\right)^{2}-\left(\left|g\right|^{2}+\kappa_{r}\kappa_{0}\right)^{2}\right\\}.$

It gives a fifth order algebraic equation in $\omega$ and does not solve
analytically. Note that to the leading (first) order in
$\kappa_{r},\kappa_{0}$, the real roots for $\omega$ are
$\omega_{0},\omega_{0}\pm\left|g\right|$ in agreement with Eq. (S28). To
identify the perturbation caused by $\kappa_{r},\kappa_{0}$, let us rewrite it
in the dimensionless form as

$0=\left[X^{4}-\left(1+\epsilon_{2}\right)^{2}+2A\left(1+\epsilon_{2}\right)\left\\{X^{2}-1+\epsilon_{1}\right\\}\right]X+B\left\\{3X^{4}-2\left(1-\epsilon_{1}\right)X^{2}-\left(1+\epsilon_{2}\right)^{2}\right\\},$
(S30)

where

$X=\frac{\omega-\omega_{0}}{\left|g\right|},\quad\epsilon_{1}=\frac{\kappa_{r}^{2}+\kappa_{0}^{2}}{2\left|g\right|^{2}},\quad\epsilon_{2}=\frac{\kappa_{r}\kappa_{0}}{\left|g\right|^{2}},\quad
A=\frac{\kappa_{0}\left|U_{r}\right|^{2}+\kappa_{r}\left|U_{0}\right|^{2}}{\kappa_{r}\left|U_{r}\right|^{2}+\kappa_{0}\left|U_{0}\right|^{2}},\quad
B=\frac{\left(\kappa_{r}+\kappa_{0}\right)\Re\left[gU_{r}\overline{U_{0}}\right]}{\left|g\right|\left(\kappa_{r}\left|U_{r}\right|^{2}+\kappa_{0}\left|U_{0}\right|^{2}\right)}.$
(S31)

If $\epsilon_{1}=\epsilon_{2}=0$, $X=\pm
1\Leftrightarrow\omega=\omega_{0}\pm\left|g\right|$ solve the equation
regardless of the values of $A$ and $B$. However, for our system,
$\epsilon_{1}\approx 0.91,\epsilon_{2}\approx 0.63$ so that the perturbations
are not that small. One can nevertheless see that corrections from
$\epsilon_{1}$ and $\epsilon_{2}$ tend to cancel each other by rewriting

$\displaystyle 0$ $\displaystyle=$
$\displaystyle\left[X^{4}-1+2A\left(1+\epsilon_{2}\right)\left(X^{2}-1\right)+2\left\\{A\left(1+\epsilon_{2}\right)\epsilon_{1}-\epsilon_{2}-\frac{\epsilon_{2}^{2}}{2}\right\\}\right]X$
(S32)
$\displaystyle+B\left(3X^{4}-2X^{2}-1+2\epsilon_{1}X^{2}-2\epsilon_{2}-\epsilon_{2}^{2}\right).$

As long as the combinations

$\epsilon_{1}^{\prime}=A\left(1+\epsilon_{2}\right)\epsilon_{1}-\epsilon_{2}-\frac{\epsilon_{2}^{2}}{2},\quad\epsilon_{2}^{\prime}=\epsilon_{1}-\epsilon_{2}-\frac{\epsilon_{2}^{2}}{2}$
(S33)

remain small, $X=\pm 1$ will be good approximate solutions. For our system,
$\epsilon_{1}^{\prime}\approx-0.11,\epsilon_{2}^{\prime}\approx 0.11$, our
resonance frequencies are only slightly shifted from
$\omega_{0}\pm\left|g\right|$. Note that for $B\neq 0$, the corrections to the
upper and lower resonance frequencies do not have to be identical, which
explains the small asymmetry observed in the experiment.

Finally, let us see that $B\neq 0$ also leads to an asymmetry in peak height.
For simplicity, we check the values of $P$ at the unperturbed resonance
frequencies $\omega=\omega_{0}\pm\left|g\right|$, which yields

$P\big{|}_{\omega=\omega_{0}\pm\left|g\right|}=h^{2}\left(\kappa_{r}\left|U_{r}\right|^{2}+\kappa_{0}\left|U_{0}\right|^{2}\right)\frac{\left|g\right|^{2}\pm
2B\left|g\right|^{2}+A\left(\left|g\right|^{2}+\kappa_{r}\kappa_{0}\right)}{\kappa_{r}^{2}\kappa_{0}^{2}+\left|g\right|^{2}\left(\kappa_{r}+\kappa_{0}\right)^{2}}.$
(S34)

It is clear that the peak heights can become asymmetric for $B\neq 0$, which
is about 40 percent for $B\approx 0.13$ in our setup (contrast
$=4B/\left\\{1+A\left(1+\epsilon_{2}\right)\right\\}$), but appears being
enhanced by the conversion to dB unit.

##  VI Additional data

In this section, we show additional data supporting the observation of
nonlinear effects within our experiments. In the first instance, we fully
cover the same SRR (in contrast to $\approx\leavevmode\nobreak\ 70\%$ coverage
in Fig. 2 in main text) as described in Sec. I by the YIG film and conduct
power dependence measurements, whose results are shown in Fig. S4. Here, we
take the same analysis method as described for Fig. 2 in the main text. Figure
S4(a) depicts $|S_{11}|$ data for various $P$ as a function of $\omega/2\pi$
and $\mu_{0}H$, while Figs. S4(b) and S4(c) respectively show the collection
and their individual spectra as a function of $P$ at $\mu_{0}H$ = 15.3 mT.
Subsequently, we show the extracted peak-frequency positions in Fig. S4(d) and
plot their difference in Fig. S4(e). In this configuration, we identify that
the coupling strength in the low power regime is $\approx$ 80 MHz, which is
larger than that of Fig. 2 in the main text by a rough factor of 2. While the
increased gap size can be explained by the larger mode overlap between the
resonator and the YIG film, its closing behavior as a function of $P$ is akin
to that of Fig. 2, demonstrating a strong reproducibility of the nonlinear
effects.

Figure S4: (a) Microwave absorption spectra ($\left||S_{11}|\right|$ (dB)) as
a function of microwave frequency and magnetic field strength for different
microwave powers at 100 $\%$ sample coverage placed on the SRR. (b)
Collections of frequency domain scans for different microwave powers at a
fixed magnetic field, where the mode hybridization is at its minimum. The
corresponding individual spectra are shown in (c). (d) Power evolution of
extracted peak positions of upper and lower modes ($\omega_{1,2}/2\pi$). (e)
The gap size calculated by $\omega_{1,2}/2\pi$.

## References

  * (1) D. D. Stancil and A. Prabhakar, _Spin Waves: Theory and Applications_ (Springer, 2009).
  * (2) B. Kalinikos, Sov. Phys. J. 24, 8, 718-731 (1981).
  * (3) V. E. Zakharov, V. S. L’vov and G. Falkovich, _Kolmogorov Spectra of Turbulence_ (Springer, 1992).
  * (4) V. S. L’vov, _Wave Turbulence Under Parametric Excitation_ (Springer-Verlag, 1994).
  * (5) H. Suhl, Phys. Chem. Solids 1, 209 (1957).


Inria and LS2N, Université de Nantes, France and http://lucas-
webpage.gforge.inria.fr/
Maxime.Lucas@inria.frhttps://orcid.org/0000-0002-9680-7129 Maxime Lucas
[500]Theory of computation Rewrite systems [500]Theory of computation
Equational logic and rewriting

###### Acknowledgements.

I thank Mathieu Anel, Cameron Calk, and Damien Pous for fruitful conversations
during the preparation of this article, Marie Kerjean for helpful advice to
make this article more accessible, and Cyrille Chenavier for both.John Q. Open
and Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016) CVIT
2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Abstract rewriting internalized

Maxime LUCAS

###### Abstract

In traditional rewriting theory, one studies a set of terms up to a set of
rewriting relations. In algebraic rewriting, one instead studies a vector
space of terms, up to a vector space of relations. Strikingly, although both
theories are very similar, most results (such as Newman’s Lemma) require
different proofs in these two settings.

In this paper, we develop rewriting theory internally to a category
$\mathcal{C}$ satisfying some mild properties. In this general setting, we
define the notions of termination, local confluence and confluence using the
notion of reduction strategy, and prove an analogue of Newman’s Lemma. In the
case of $\mathcal{C}=\operatorname{Set}$ or $\mathcal{C}=\operatorname{Vect}$
we recover classical results of abstract and algebraic rewriting in a slightly
more general form, closer to von Oostrom’s notion of decreasing diagrams.

###### keywords:

Rewriting theory, Internal object, Kleene algebras, Termination

###### category:

##  1 Introduction

The goal of this work is to bridge the gap between two major branches of
rewriting theory: abstract rewriting, stemming from the work of Newman, and
algebraic rewriting. In algebraic rewriting, convergent presentations are
called Gröbner basis and were introduced by Buchberger to compute basis of
algebras. In particular, it allows one to solve the ideal membership problem,
which is the linear equivalent of the word problem. Today Gröbner basis are in
particular used in control theory.

The two theories are very similar: both define a notion of terminating,
confluent or locally confluent relation, and prove a diamond Lemma showing
that locally confluent terminating system are confluent (in the case of
algebraic rewriting, this was explicitly done by Bergman [2]). Nevertheless,
we are not aware of any treatment unifying those two theories.

The main difference between algebraic and abstract rewriting is that algebraic
rewriting is not stable by contextual closure. For example, suppose given an
rewriting relation $\to$ on a vector space. If $u\to v$ is a valid rewriting
step, then $u+w\to v+w$ is not necessarily valid. This is necessary to avoid
non-terminating behaviours: otherwise the rewriting step $u-u-v\to v-u-v$
would be valid, but this is just $-v\to-u$, which implies that $v\to u$: in
other words, $\to$ is always symmetric and can never be terminating. The
failure to take this phenomenon into account plagued many early papers
studying the algebraic $\lambda$-calculus, such as [4], and was not recognized
before [11].

While the existence of two rewriting theories is not an issue per se, the
multiplication of applications of higher dimensional rewriting to various
algebraic structures calls for a unified framework. Higher dimensional
rewriting seeks to apply rewriting techniques to study homotopical and
homological properties of algebraic objects. Already existing examples include
monoids [9], algebras [5], string diagrams (encoded as Pros and ProPs) [6],
and term rewriting systems [8]. Future cases of interest include e.g. (non-
symmetric, symmetric or shuffle, linear or set-theoretic) operads or linear
Pros.

All these structures can be represented as monoids inside a category
$\mathcal{C}$: taking $\mathcal{C}=\operatorname{Set}$ we obtain (regular)
monoids, monoid objects in $\mathcal{C}=\operatorname{Vect}_{k}$ are
$k$-algebras, and the different flavors of operads are all monoids in various
categories of collections. This paper constitutes a first step towards a
unified treatment of higher dimensional rewriting for these different objects,
by developing a general theory of rewriting inside a category $\mathcal{C}$,
omitting with the monoid structure for now. In the
$\mathcal{C}=\operatorname{Set}$ and $\mathcal{C}=\operatorname{Vect}_{k}$ we
recover respectively abstract and algebraic rewriting, in a slightly more
general form than the one usually presented. Those two cases have already
presented in earlier works, namely [7] for the case
$\mathcal{C}=\operatorname{Set}$, and [3] for the case
$\mathcal{C}=\operatorname{Vect}_{k}$.

There are two ways to model a relation in abstract rewriting. The first one is
to see a relation $\to$ on an object $E$ as a subset of $E\times E$. The
second one, which is the one suited for higher dimensional rewriting and that
we will generalize here, is to see a relation as a set $R$ equipped with maps
$\sigma_{R},\tau_{R}:R\to E$, associating to any $f\in R$ its source
$\sigma_{R}f$ and target $\tau_{R}f$, and making $(E,R,\sigma_{R},\tau_{R})$ a
directed graph111This can also be seen as a _labelled_ rewriting relation.. We
therefore study the rewriting properties of graphs internal to an arbitrary
category $\mathcal{C}$ satisfying some mild properties. We now describe some
of the content of the paper.

While the notions of reflexivity, symmetry and transitivity can be defined
straightforwardly in this context, the main obstacle lies in defining an
appropriate notion of termination for a graph $R$ on an object $E$. While in
abstract rewriting a relation $R$ is intrinsically terminating, the situation
is more subtle in algebraic rewriting. There, a relation on a vector space
$E=kX$ is said to terminate _with respect to a terminating order on $X$_. In
practice, $kX$ is often the vector space underlying a polynomial algebra, and
the terminating order is a monomial order.

In an arbitrary category $\mathcal{C}$, we proceed similarly, by supposing
that $E$ is endowed with a filtration $E_{0}\subset E_{1}\subset
E_{2}\subset\ldots\subset E$, which encodes the terminating ordering on $E$.
Formally, such a filtration is given by a terminating order $(I,\leq)$ and a
functor $I\to\mathcal{C}$ whose colimit is $E$. From this we can define the
_object of normal forms_ of $E$, denoted $E_{min}$, as the union of the
$E_{i}$ where $i$ is a minimal element of $I$.

A graph $R$ on $E$ is then terminating if it is compatible with this
filtration in a suitable way, expressed through the existence of a local
strategy $h:E\to R$. When $E$ is a set, a local strategy maps any $x\in E$ to
a rewriting step $h(x)$ of source $x$ and whose target is smaller than $x$.
Any local strategy induces a (global) strategy $H$, mapping any $x$ to a path
$H(x)$ to (one of) its normal form, denoted $H^{\tau}(x)$. The end diagram is
the following:

${R}$${E}$${E_{min}}$$\scriptstyle{\sigma_{R}}$$\scriptstyle{\tau_{R}}$$\scriptstyle{H^{\tau}}$$\scriptstyle{H}$$\scriptstyle{\iota}$

and it satisfies the relations:

$\sigma_{R}\circ H=id_{E}\qquad\tau_{R}\circ H=\iota\circ H^{\tau}\qquad
H^{\tau}\circ\iota=Id_{E_{min}}$

This almost makes the previous diagram into a split coequaliser, the only
equation missing being $H^{\tau}\circ\sigma_{R}=H^{\tau}\circ\tau_{R}$. We
define this as our notion of confluence, which implies immediately that if $R$
is a terminating and confluent relation, then the quotient $E/R$ is isomorphic
to the object of normal forms $E_{min}$. When $\mathcal{C}$ is a locally
finitely presented category, We also define a notion of local confluence and
show that, together with termination, it implies confluence, recovering
Newman’s Lemma in this general setting.

### Organisation

In Section 2, we start by recalling some classical definitions and results of
abstract and algebraic rewriting. Those will be useful throughout the paper in
order to compare them to the methods developed in the subsequent sections.

In Section 3, we investigate elementary properties of graphs internal to a
category $\mathcal{C}$, such as reflexivity, symmetry and transitivity. We
also define the notions of reflexive, symmetric and transitive closures of a
relation.

Section 4 is devoted to the notion of termination of a graph. We define
termination of a relation as the existence of a local strategy compatible with
this filtration. We finish this section by examples, showing in particular
that for any terminating (abstract or algebraic) relation induces a
terminating graph.

In Section 5, we define a notion of global strategy for a graph $R$ on a
filtered object $E$, and define when such a strategy is confluent. We show
that whenever there exists a confluent strategy, then the quotient of $E$ by
$R$ is isomorphic to the object of normal forms. We show that any local
strategy induces a global strategy, although not necessarily a confluent one.

Finally in Section 6 we restrict ourselves to the case when $\mathcal{C}$ is a
locally finitely presented category. In this case, we are able to give a
criterion for a local strategy to induce a confluent strategy. Interpreting
this criterion as a form of local confluence, we obtain a general proof of
Newman’s and Bergman’s diamond Lemmas.

##  2 Abstract and algebraic rewriting

In this section, we recall some of the standard results of abstract and
algebraic rewriting. This will be useful in subsequent sections for comparison
with our general theory. Since in Section 5 confluence will only be defined on
terminating graphs, we do not dwell on the case of confluent but non-
terminating relations. None of the results presented here are new, although
perhaps algebraic rewriting is only rarely presented at this level of
generality.

Contrary to the rest of this article, where we will model relations by graphs,
here we stick to the more usual presentation of subsets of $E\times E$. While
this choice is somewhat arbitrary, it will be useful later on in order to
distinguish between termination in the sense of relations, and termination in
the sense of graphs.

######  Definition 2.1.

Let $E$ be a set. By a (set-theoretic) relation, we mean a subset of $E\times
E$. We say that such a relation $\to$ is _terminating_ if there exists no
infinite sequence $a_{0},a_{1},a_{2},\ldots\in E$ such that $a_{0}\to a_{1}\to
a_{2}\to\ldots$.

An element $e\in E$ is said to a normal form for $\to$ if there exists no
$y\in E$ such that $x\to y$. We denote by $NF(\to)$ the set of normal forms
for $\to$.

We denote by $\xrightarrow{=}$, $\xrightarrow{+}$, $\xrightarrow{*}$ and
$\xleftrightarrow{*}$ respectively the reflexive, transitive, reflexive-
transitive and symmetric-reflexive-transitive closure of $\to$.

We say that $\to$ is confluent if for any $u,v,w$ such that
$u\xrightarrow{*}v$ and $u\xrightarrow{*}w$, there exists $z$ such that
$v\xrightarrow{*}z$ and $w\xrightarrow{*}z$.

We say that $\to$ is locally confluent if for any $u,v,w$ such that
$u\rightarrow v$ and $u\rightarrow w$, there exists $z$ such that
$v\xrightarrow{*}z$ and $w\xrightarrow{*}z$.

Finally, we denote by $E/\xleftrightarrow{*}$ the quotient of $E$ by the
equivalence relation generated by $\to$.

######  Proposition 2.2.

Let $\to$ be a terminating relation on a set $E$. The following are
equivalent:

SC1

The relation $\to$ is locally confluent.

SC2

The relation $\to$ is confluent.

SC3

For any $u,v\in E$ such that $u\xleftrightarrow{*}v$, there exists $w$ such
that $u\xrightarrow{*}w$ and $v\xrightarrow{*}w$.

SC4

The canonical map $NF(\to)\longrightarrow(E/\xleftrightarrow{*})$, sending any
normal form to its equivalence class modulo $\xleftrightarrow{*}$, is a
bijection.

######  Remark 2.3.

Property SC3 above is known as the Church-Rosser property, and is equivalent
to confluence even without the hypothesis that $\to$ is terminating.

Throughout this article, we fix $k$ a characteristic $0$ field. We now give a
quick presentation of algebraic rewriting.

######  Definition 2.4.

Let $X$ be a set and let $kX$ denote the vector space spanned by $X$. Any
$u\in kX$ can be written in a unique way as $\sum_{i=1}^{n}\lambda_{i}x_{i}$,
where $\lambda_{i}\neq 0$ and $x_{i}\in X$. The set $\\{x_{1},\ldots,x_{n}\\}$
is called the _support_ of $u$ and is denoted by $\operatorname{supp}(u)$.

An _algebraic relation_ $\to$ on $kX$ is a subset of $X\times kX$ such that
whenever $x\to u$, then $x\notin\operatorname{supp}(u)$. Such a relation
induces two (set-theoretic) relations on $kX$, denoted $\xrightarrow[alg]{}$
and $\xrightarrow[wf]{}$. The first is defined by $\lambda
x+v\xrightarrow[alg]{}\lambda u+v$ for all $\lambda\in k$, $u,v\in kX$ and
$x\in X$ such that $x\to u$.

The second one is the restriction of $\xrightarrow[alg]{}$ to the case when
$\lambda\neq 0$ and $x\notin\operatorname{supp}(v)$.

Let $\leq$ be a terminating order on $X$. We say that $\to$ is _terminating
with respect to $\leq$_ if whenever $x\to u$, then any $y$ appearing in the
support of $u$ is strictly smaller than $x$. This implies in particular that
$\xrightarrow[wf]{}$ is terminating, as a set-theoretic relation.

The set of normal forms for $\xrightarrow[wf]{}$ forms a sub-vector space of
$kX$, a basis of which is given by elements $x\in X$ such that there exists no
$u\in kX$ such that $x\to u$. The vector space of normal forms is denoted
$NF(\to)$.

Finally, we denote by $\xleftrightarrow{*}$ the congruence generated by $\to$
(which is also the equivalence relation generated by $\xrightarrow[alg]{}$).

######  Note 2.5.

The use of a terminating order on $X$ to define the termination of an
algebraic relation above is fairly standard in the literature (and is the one
used by Bergman in [2]), but is actually not really necessary: one could
instead request that $\xrightarrow[wf]{}$ is terminating, as a set-theoretic
relation. This is done for example in [5, Section3.2].

Although this allows one to deduce many results on algebraic rewriting from
abstract rewriting, we argue that it is still not satisfying: the definition
of the relation $\xrightarrow[wf]{}$ is very specific to the category at hand
(here $\mathcal{C}=\operatorname{Vect}_{k}$) and cannot be generalised to
other categories, such as the category of groups.

The following lemma clarifies the relationship between the relations $\to$,
$\xrightarrow[wf]{}$ and $\xrightarrow[alg]{}$.

######  Lemma 2.6.

Let $X$ be a set and $\to$ be an algebraic relation on $kX$.

  * •

For any $x\in X$, the relations $x\to u$ and $x\xrightarrow[wf]{}u$ are
equivalent.

  * •

If $u\xrightarrow[alg]{}v$, there exists $w\in kX$ such that
$u\xrightarrow[wf]{=}w\xleftarrow[wf]{=}v$

######  Proof 2.7.

While the first point is an easy verification, the second is more subtle. A
proof can be found in the proof of [5, Theorem 4.2.1].

######  Proposition 2.8.

Let $X$ be a set equipped with a terminating order $\leq$, and $\to$ be an
algebraic relation on $kX$ which is terminating with respect to $\leq$. The
following are equivalent:

AC1

For any $x\in X$, if $x\to u$ and $x\to v$ then there exists $w$ such that
$u\xrightarrow[wf]{*}w$ and $v\xrightarrow[wf]{*}w$.

AC2

The relation $\xrightarrow[wf]{}$ satisfies the equivalent properties of
Proposition 2.2.

AC3

The canonical map $NF(\to)\longrightarrow(kX/\xleftrightarrow{*})$ sending any
normal form to its equivalence class modulo $\xleftrightarrow{*}$, is an
isomorphism.

######  Example 2.9.

Take $kX=k[x]$: in other words, $X=\\{1,\ldots,x^{n},\ldots\\}$. We can equip
$X$ with the terminating order induced by $x^{i}<x^{i+1}$. Given a unitary
polynomial $P\in k[x]$ we can write $P=x^{n}+\sum_{i=0}^{n-1}x^{i}$. This
induces a (confluent and terminating) algebraic rewriting system
$x^{n}\to-\sum_{i=0}^{n-1}x^{i}$.

The quotient $kX/\xleftrightarrow{*}$ is none other than $k[X]/(P)$, while
$NF(\to)$ is the subspace of polynomials of degree at most $(n-1)$. Taking
$k=\mathbb{R}$ and $P=x^{2}+1$, the isomorphism of property AC3 is none other
than the canonical isomorphism between $\mathbb{R}+x\mathbb{R}$ and
$R[x]/(x^{2}+1)=\mathbb{C}$.

##  3 Graphs as relations

We fix a category $\mathcal{C}$, and suppose that $\mathcal{C}$ is finitely
complete has all countable (including finitary) coproducts.

In this section, we study define some elementary properties of graphs, seen as
generalized relations.

######  Definition 3.1.

Let $\mathcal{C}$ be a category, and $E$ an object of $\mathcal{C}$. We denote
by $\operatorname{Gph}_{E}$ the category of graphs over $E$. Objects are
triples $(R,\sigma_{R},\tau_{R})$ , where $R$ is an object of $\mathcal{C}$
and $\sigma_{R}:R\to E$ and $\tau_{R}:R\to E$ are maps in $\mathcal{C}$.

${R}$${E}$${E}$$\scriptstyle{\sigma_{R}}$$\scriptstyle{\tau_{R}}$

A morphism of graphs from $(R,\sigma_{R},\tau_{R})$ to
$(S,\sigma_{S},\tau_{S})$ is a map $R\to S$ commuting with $\sigma$ and
$\tau$.

We will often denote a graph $(R,\sigma_{R},\tau_{R})$ simply by $R$.

######  Definition 3.2.

Let $E$ be an object of $\mathcal{C}$, and let $R,S$ be two graphs over $E$.

  * •

$E$ canonically inherits the structure of a graph using $\sigma_{E}=id_{E}$
and $\tau_{E}=id_{E}$.

  * •

The product of $R$ and $S$, denoted $RS$, is the graph defined by the
following pullback, with $\sigma_{RS}=\sigma_{R}\circ\pi_{1}$ and
$\tau_{RS}=\tau_{R}\circ\pi_{2}$:

${RS}$${R}$${S}$${E}$${E}$${E}$$\scriptstyle{\pi_{1}}$$\scriptstyle{\pi_{2}}$${\llcorner}$$\scriptstyle{\sigma_{R}}$$\scriptstyle{\tau_{R}}$$\scriptstyle{\sigma_{S}}$$\scriptstyle{\tau_{S}}$

  * •

The sum of $R$ and $S$, denoted $R+S$, is the graph $(R\coprod
S,\sigma_{R}\coprod\sigma_{S},\sigma_{R}\coprod\sigma_{S})$, where $\coprod$
denotes the coproduct in $\mathcal{C}$.

  * •

The transitive closure of $R$, denoted $R^{+}$, is the graph over $E$ with
underlying object the countable coproduct
$\coprod_{i=1}^{\infty}R^{\times_{E}i}$, with $\sigma_{R^{+}}$ (resp.
$\tau_{R^{+}}$) defined on the component $R^{\times_{E}i}$ as the composite
$\sigma_{R}\circ\pi_{1}$ (resp. $\tau_{R}\circ\pi_{i}$) for any $i\geq 1$.

  * •

The transitive reflexive closure of $R$, denoted $R^{*}$, is the graph
$R^{+}+E$.

  * •

The opposite of $R$, denoted $R^{\circ}$, is the graph obtained by reversing
the source and target of $R$: $\sigma_{R^{\circ}}=\tau_{R}$ and
$\tau_{R^{\circ}}=\sigma_{R}$.

  * •

The reflexive symmetric transitive closure of $R$, denoted $R^{\mathcal{S}}$,
is the graph $(R+R^{\circ})^{*}$.

######  Definition 3.3.

Let $R$ be a graph over an object $E$ in a category $\mathcal{C}$. We say that
$R$ is:

  * •

reflexive if there exists a map (of graphs) $u_{R}:E\to R$,

  * •

transitive if there exists a map $m_{R}:RR\to R$,

  * •

symmetric if there exists a map $s_{R}:R^{\circ}\to R$.

The closure terminology of Definition 3.2 is justified by the following lemma:

######  Lemma 3.4.

Let $R$ be a graph over an object $E$ in a category $\mathcal{C}$. Then $R+E$
is a universal among the reflexive graphs under $R$, in the sense that $R+E$
is reflexive, and for any map $f:R\to S$ in $\operatorname{Gph}_{E}$, where
$S$ is a reflexive graph, then there exists a unique map $\tilde{f}:R+E\to S$
preserving the reflexive structure such that the composite with the inclusion
$R\to R+E$ yields $f$.

Similarly:

  * •

The graph $R+R^{\circ}$ is universal among symmetric graphs under $R$.

  * •

The functor $R^{+}$ is universal among transitive graphs under $R$.

  * •

The functor $R^{*}$ is universal among reflexive transitive graphs under $R$.

  * •

The functor $R^{\mathcal{S}}$ is universal among reflexive transitive
symmetric graphs under $R$.

######  Example 3.5.

In the case $\mathcal{C}=\operatorname{Set}$, a graph over a set $E$ is just a
graph with set of objects $E$, and reflexivity and symmetry coincide with the
usual terminology.

If $\mathcal{C}$ is a Mal’cev variety, that is $\mathcal{C}$ is the category
of models of an algebraic theory containing a ternary operation $t$ such that
$t(x,x,y)=y$ and $t(x,y,y)=x$, then reflexivity implies symmetry and
transitivity. Mal’cev varieties include $\mathcal{C}=\operatorname{Gp}$, the
category of groups, whose where the ternary operation is given by
$t(x,y,z)=xy^{-1}z$. Other examples also include the category of abelian
groups, vector spaces, or the one of heaps.

In the case of $\mathcal{C}=\operatorname{Vect}_{k}$, the category of
$k$-vector spaces (or indeed any abelian category), then a truncation of the
Dold-Kan correspondence shows that the category of reflexive graphs is
equivalent to the category of chain complexes concentrated in degrees $0$ and
$1$.

Moving from a graph $R$ to one of its closure does not change the equivalence
relation presented by $R$. This is made formal by the following lemma.

######  Lemma 3.6.

If $R$ is a graph on an object $E$ of $\mathcal{C}$, let us denote by $E/R$
the coequaliser of the diagram $\sigma_{R},\tau_{R}:R\to E$.

Then for any graph $R$ over $E$, there are canonical isomorphisms
$E/R=E/R^{*}=E/R^{\mathcal{S}}$.

##  4 Internalizing termination

We fix a category $\mathcal{C}$ with all pullbacks and countable coproducts.

In this section, we define what it means for a graph to be terminating. This
property is expressed in term of a rewriting strategy. When
$\mathcal{C}=\operatorname{Set}$, such a strategy associates to any $x$ which
is not a normal form a rewriting step of source $x$. We show how the examples
of terminating rewriting relations of Section 2 fit into the general
definition, but also that some non-terminating relations can be terminating as
graphs.

######  Note 4.1.

If $I$ is partially ordered set, we silently see $I$ as a category, with an
arrow $x\to y$ whenever $x\leq y$ in $I$.

######  Definition 4.2.

A _directed set_ is a non-empty partially ordered set $I$ such that for all
$x,y\in I$, there exists $z$ such that $x,y\leq z$.

Let $E$ be an object of $\mathcal{C}$. A _directed structure_ on $E$ is the
data of a directed set $I$ together with a functor
$E_{\bullet}:I\to\mathcal{C}$ and a natural transformation
$\iota_{\bullet}:E_{\bullet}\to E$ exhibiting $E$ as the colimit of
$E_{\bullet}$. If $I$ is a directed set, the data of $E_{\bullet}$ and
$\iota_{\bullet}$ is called an _$I$ -filtration_ of $E$, and we slightly abuse
notations by saying that $E$ is an _$I$ -filtered object_ if it comes equipped
with an $i$-filtration $(E_{\bullet},\iota_{\bullet})$.

A morphism of $I$-filtered object from $E$ to $F$ is the data of a natural
transformation $\eta:E_{\bullet}\Rightarrow F_{\bullet}$. Note that this
induces a map from $E$ to $F$.

We denote by ${I\text{-}\operatorname{Filt}}_{\mathcal{C}}$ the category of
$I$-filtered objects in $\mathcal{C}$.

######  Note 4.3.

Identifying an object $E$ of $\mathcal{C}$ with a functor from the terminal
category $\top\xrightarrow{E}\mathcal{C}$, the data of a filtered object in
$\mathcal{C}$ fits into the following diagram:

${I}$${\mathcal{C}}$${\top}$$\scriptstyle{E_{\bullet}}$$\scriptstyle{\iota_{\bullet}}$$\scriptstyle{E}$

######  Definition 4.4.

Let $I$ be a directed set. For any $i\in I$ we denote by $I_{<i}$ the subset
of elements of $I$ smaller than $i$, and by $I_{min}$ the set of minimal
elements of $I$.

If $E$ is an $I$-filtered object of a category $\mathcal{C}$, then for any
$i\in I$, we denote by $E_{<i}$ (resp. $E_{min}$) the colimit of the
restriction of the functor $E_{\bullet}$ to $I_{<i}$ (resp. $I_{min}$). For
$i\in I_{min}$, we define $E_{<i}$ as $E_{i}$. This defines a functor
$E_{<\bullet}:I\setminus I_{min}\to\mathcal{C}$. The universal property of the
colimit induces a natural transformation $\iota_{<i}:E_{<i}\to E$.

If $f:E\to F$ is a map in $\mathcal{C}$, it induces a natural transformation
$f_{\bullet}:E_{\bullet}\Rightarrow F$. For any $i\in I\setminus I_{min}$,
restricting $f_{\bullet}$ to $I_{<i}$ and passing to the colimit induces a map
$f_{<i}:E_{<i}\to F$, which we extend for $i\in I_{min}$ by setting
$f_{<i}:=f\circ\iota_{i}$. This defines a natural transformation
$f_{<\bullet}:E_{<\bullet}\Rightarrow F$.

######  Note 4.5.

By definition, $I_{min}$ is a discrete partially ordered set (i.e. for all
$i,j\in I_{min}$, if $i\leq j$ then $i=j$). As a result $E_{min}$ is actually
given by the coproduct $E_{min}=\coprod_{i\in I_{min}}E_{i}$.

######  Definition 4.6.

A terminating graph on an $I$-filtered object $E$ of a category $\mathcal{C}$
is the data of a graph $R\in\operatorname{Gph}_{E}$, together with a map
$h:E\to R+E$ and a natural transformation
$h^{\tau}_{\bullet}:E_{\bullet}\Rightarrow E_{<\bullet}$ such that

TG1

$I$ is a terminating order.

TG2

For all $i\in I$, $\sigma_{R+E}\circ h=id_{E}$.

TG3

For all $i\in I_{min}$, $h\circ\iota_{i}=u_{R+E}\circ\iota_{i}$.

TG4

For all $i\in I$, $\tau_{R+E}\circ h\circ\iota_{i}=\iota_{<i}\circ
h^{\tau}_{i}$.

The last two axioms can be represented by the following diagram:

$I$$\top$$\mathcal{C}$$E_{\bullet}$$!$$E$$\iota_{\bullet}$$R+E$$h$$I$$\top$$\mathcal{C}$$E_{\bullet}$$!$$R+E$$E$$\iota_{\bullet}$$=$

$I$$\top$$\mathcal{C}$$E_{\bullet}$$!$$R+E$$\iota_{\bullet}$$E$$E$$h$$\tau_{R}$$I$$\mathcal{C}$$\top$$E_{\bullet}$$E_{<\bullet}$$!$$E$$h^{\tau}_{\bullet}$$\iota_{<\bullet}$$=$

######  Note 4.7.

Note also the last two axioms imply that for all $i\in I_{min}$,
$h_{i}^{\tau}=id_{E_{i}}$.

######  Example 4.8.

While in terminating relations _every_ rewriting step is supposed to be
decreasing, the definition of terminating graph defined above only requires
that there exists a decreasing rewriting step of source $x$ whenever $x$ is
not a normal form. For example, the following graph is terminating:

${a}$${b}$${c}$${d}$$\scriptstyle{f_{1}}$$\scriptstyle{f_{3}}$$\scriptstyle{f_{2}}$$\scriptstyle{f_{4}}$

Formally, we take $I=\\{0,1\\}$, $E_{0}=\\{c,d\\}$ and
$E_{1}=E=\\{a,b,c,d\\}$. As a result, the set of normal forms is
$E_{min}=\\{c,d\\}$.

Defining a strategy $(h,h^{\tau})$ on $R=\\{f_{1},f_{2},f_{3},f_{4}\\}$
amounts to choosing for any $x\in E$ that is not a normal form a rewriting
step $h(x):x\to h^{\tau}(x)$. The fact that $h^{\tau}$ lands in $E_{<i}$
rather than $E$ witnesses the fact that $h^{\tau}(x)$ is in some sens
“smaller” than $x$. On normal forms, axiom TG3 forces $h(c)=1_{c}$ and
$h(d)=1_{d}$, and by axiom TG4, we necessarily have $h^{\tau}_{0}(c)=c$ and
$h^{\tau}_{0}(d)=d$.

For $i=1$ by naturality of $h_{\bullet}^{\tau}$ we still have
$h_{1}^{\tau}(c)=c$ and $h_{1}^{\tau}(d)=d$. Finally we set $h(a)=f_{3}$ and
$h(b)=f_{4}$, which forces $h^{\tau}(a)=c$ and $h^{\tau}(b)=d$.

We represent the situation by the diagram on the left hand side of the
following picture. The horizontal bar denotes the filtration of $E$ induced by
$I$, while the thick red arrows denote the arrows selected by the local
strategy.

$a$$b$c$d$$f_{1}$$f_{2}$$f_{3}$$f_{4}$ $a$$b$c$d$$f_{1}$$f_{2}$$f_{3}$$f_{4}$

The fact that $h^{\tau}_{i}$ lands in $E_{<i}$ is represented by the fact that
the chosen arrows each go one step lower in the filtration.

The diagram on the right hand side of the figure above pictures another
filtration of $E$ (given by $I=\\{0<1<2\\}$, with $E_{0}=\\{c,d\\}$,
$E_{1}=\\{b,c,d\\}$ and $E_{2}=\\{a,b,c,d\\}$) and another local strategy,
given by $h(a)=f_{1}$ and $h(b)=f_{4}$.

The following example explains how any terminating relation on a set $E$
induces both a filtration of $E$, and a terminating graph on $E$.

######  Example 4.9.

Let $(E,\to)$ be a set equipped with a terminating relation. Then $E$ is
naturally equipped with a structure of an $\mathbb{N}$-filtered set as
follows:

$E_{0}=NF(\to)\qquad E_{i+1}=\\{x\in E|\exists y\in
E_{i},x\xrightarrow{=}y\\}$

Notice that for all $i\in\mathbb{N}$, $\mathbb{N}_{<i+1}$ has a terminal
element (namely $i$), and so $E_{<i+1}$ is simply $E_{i}$.

In addition, $\to$ induces a terminating graph $(R,h,h^{\tau})$ on $E$, where:

  * •

$R=\\{(x,y)|x\to y\\}$ with operations $\sigma_{R}$ and $\tau_{R}$ given by
the first and second projections respectively.

  * •

For $x\in E_{0}$, i.e. $x$ is a normal form, we set $h^{\tau}_{0}(x)=x$.

  * •

For any $i\in\mathbb{N}$, take $x\in E_{i+¡}$. If $x\in E_{i}$, then we pose
$h^{\tau}_{i+¡}(x)=h^{\tau}_{i}(x)$. Otherwise, by definition there exists
$y\in E_{i}$ such that $x\xrightarrow{}y$, and we pose $h^{\tau}_{i+1}(x)=y$.

  * •

Finally, $h(x)$ is given by the pair $(x,h^{\tau}_{i}(x))$, which does not
depend on $i$ by definition of $h^{\tau}_{\bullet}$.

The next lemma will allow us to easily build filtered objects in categories
other than sets.

######  Lemma 4.10.

Let $F:\mathcal{C}\to\mathcal{D}$ be a cocontinuous functor. Then for any
directed set $I$, $F$ induces a functor

${I\text{-}\operatorname{Filt}}_{F}:{I\text{-}\operatorname{Filt}}_{\mathcal{C}}\to{I\text{-}\operatorname{Filt}}_{\mathcal{D}}.$

In addition, for any $I$-filtered object $E$, $F(E)_{i}=F(E_{i})$,
$F(E)_{min}=F(E_{min})$ and $F(E)_{<i}=F(E_{<i})$.

######  Proof 4.11.

Let $E$ be an $I$-filtered object in $\mathcal{C}$. Since $F$ preserves
colimits, $(F(E),I,F\circ E_{\bullet},F\circ\iota_{\bullet})$ is a filtered
object in $\mathcal{D}$. The image of maps by $F$ is as straightforward.

######  Example 4.12.

Let $X$ be a set equipped with a terminating order $\leq$, and let $\to$ be an
algebraic relation on $kX$ which is terminating with respect to $\leq$.

To exhibit a filtration on $kX$, we first define an map
$\operatorname{ht}:X\to\mathbb{N}$, by induction on $x\in X$, using the order
$\leq$. Without loss of generality, we can suppose that $NF(\to)$ is equal to
the subspace of $kX$ spanned by the $x\in X$ which are minimal for $\leq$
(otherwise, replace $\leq$ by the relation $x\prec y$ defined by $x<y$ and
$y\notin NF(\to)$).

  * •

If $x$ is minimal for $\leq$, i.e. $x$ is a normal from, we define
$\operatorname{ht}(x)=0$.

  * •

Otherwise, we define:

$\operatorname{ht}(x):=\min_{\begin{subarray}{c}u\in kX\\\ x\to
u\end{subarray}}\left\\{\max_{y\in\operatorname{supp}(u)}\operatorname{ht}(y)\right\\}+1$

We finally define a $\mathbb{N}$-filtration on $X$ by setting $X_{i}=\\{x\in
X|\operatorname{ht}(x)\leq i\\}$. By the previous lemma, this filtration can
be transported to $kX$. More precisely, a linear combination $u\in kX$ lies in
$kX_{i}$ if and only if $\operatorname{supp}(u)\subseteq X_{i}$.

Then $\to$ induces a reflexive graph $R$, which is the subspace of $kX\times
kX$ generated by the pairs $(x,u)$ such that $x\xrightarrow{=}u$. To show that
this graph is terminating, we define $h^{\tau}$ and $h$ as follows:

  * •

Let $x\in X_{0}$, that is $x$ is a normal form. We then define
$h^{\tau}(x)=x$, and extend it to $kX_{0}$ by linearity.

  * •

For any $i\in I$, let $x\in X_{i+1}$. If $x\in X_{i}$, then we simply define
$h^{\tau}_{i+1}(x)=h_{i}^{\tau}(x)$. Otherwise, by definition there exists
$u\in kX_{i}$ such that $x\to u$, and we define $h_{i+1}^{\tau}(x)=u$. We
finally extend $h_{i+1}^{\tau}$ to $kX_{i+1}$ by linearity.

  * •

For any $x\in X$, we finally define $h(x)=(x,h^{\tau}(x))$, and extend it to
$kX$ by linearity.

######  Remark 4.13.

Let $(R,h_{\bullet},h_{\bullet}^{\tau})$ be a terminating graph on an a
filtered object $E$, and $S$ be an other graph over $E$. For any arrow $f:R\to
S$, $(S,f\circ h_{\bullet},h^{\tau}_{\bullet})$ is a terminating graph over
$E$. In particular, the various closures of $R$ defined in Section 3 all
inherit a canonical structure of terminating graph over $E$, which we still
denote $h_{\bullet}$ and $h_{\bullet}^{\tau}$.

##  5 Confluence and strategies

In this section, we define the notion of confluence and local confluence of a
graph. Our criterion for confluence is that a for a confluent and terminating
graph, the quotient by the graph should be isomorphic to the object of normal
forms. We show this property, and prove that local confluence together with
termination imply confluence: this is Newman’s Lemma.

######  Definition 5.1.

Let $\mathcal{C}$ be any category. A split coequalizer in $\mathcal{C}$ is a
diagram

${A}$${B}$${C}$$\scriptstyle{f}$$\scriptstyle{g}$$\scriptstyle{e}$$\scriptstyle{t}$$\scriptstyle{s}$

such that:

$e\circ f=e\circ g\qquad e\circ s=id_{C}\qquad s\circ e=g\circ t\qquad f\circ
t=id_{B}$

For any such diagram, $e$ is necessary a coequalizer of $f$ and $g$, which we
denote by $B/A=C$. In addition, such a coequaliser is absolute, meaning that
it is preserved by any functor.

######  Definition 5.2.

Let $R$ be a graph on a filtered object $E$. A _(global) strategy_ for $R$ is
the data of a pair of morphisms $H:E\to R$ and $H^{\tau}:E\to E_{min}$ such
that the following equations hold:

$\sigma_{R}\circ H=id_{E}\qquad\tau_{R}\circ H=\iota_{min}\circ H^{\tau}\qquad
H^{\tau}\circ\iota_{min}=Id_{E_{min}}$

A strategy $(H,H^{\tau})$ is said to be _confluent_ if
$H^{\tau}\circ\sigma_{R}=H^{\tau}\circ\tau_{R}$

The following proposition immediately follows from the definition of confluent
strategy.

######  Proposition 5.3.

Let $R$ be a graph over a filtered object $E$. If there exists a confluent
strategy $(H,H^{\tau})$ for $R$ then the diagram

${R}$${E}$${E_{min}}$$\scriptstyle{\sigma_{R}}$$\scriptstyle{\tau_{R}}$$\scriptstyle{H^{\tau}}$$\scriptstyle{H}$$\scriptstyle{\iota_{min}}$

forms a split coequalizer. In particular, $E/R=E_{min}$.

######  Theorem 5.4.

Let ($R,h_{\bullet},h^{\tau}_{\bullet})$ be a terminating graph on an
$I$-filtered object $E$.

Then there is a strategy $(H,H^{\tau})$ for $R^{\mathcal{S}}$, which satisfy
the additional equations:

$H=\mu_{R}\circ\langle h,H\circ\tau_{R+E}\circ h\rangle\qquad
H^{\tau}=H^{\tau}\circ\tau_{R+E}\circ h$

Where $\mu_{R}$ denotes the canonical map $RR^{\mathcal{S}}\to
R^{\mathcal{S}}$.

######  Proof 5.5.

Since $E$ is the colimit of the functor $E_{\bullet}$, it is enough to define
natural transformations $H_{\bullet}:E_{\bullet}\Rightarrow R^{\mathcal{S}}$
and $H^{\tau}_{\bullet}:E_{\bullet}\Rightarrow E_{min}$ satisfying the
following equations:

$\sigma_{R^{\mathcal{S}}}\circ
H_{\bullet}=\iota_{\bullet}\qquad\tau_{R^{\mathcal{S}}}\circ
H_{\bullet}=\iota_{min}\circ H_{\bullet}^{\tau}\qquad
H^{\tau}_{i}=\iota_{i}\text{, where $i\in I_{min}$.}$
$H_{\bullet}=\mu_{R}\circ\langle h\circ\iota_{\bullet},H\circ\tau_{R+E}\circ
h\circ\iota_{\bullet}\rangle\qquad
H^{\tau}_{\bullet}=H^{\tau}\circ\tau_{R+E}\circ h\circ\iota_{\bullet}$

Note that using the equations relating $h$ to $h^{\tau}$, the last two
relations can be rewritten as:

$H_{\bullet}=\mu_{R}\circ\langle h\circ\iota_{\bullet},H_{<\bullet}\circ
h_{\bullet}^{\tau}\rangle\qquad H^{\tau}_{\bullet}=H^{\tau}_{<\bullet}\circ
h_{\bullet}^{\tau}$

We proceed by induction on $i\in I$ to build such natural transformations. If
$i$ is minimal, then the third equation entirely determines $H^{\tau}_{i}$,
and we take $H_{i}:=u_{R^{\mathcal{S}}}\circ\iota_{i}$. Then the first
equation holds because $\sigma_{R^{\mathcal{S}}}\circ
H_{i}=\sigma_{R^{\mathcal{S}}}\circ
u_{R^{\mathcal{S}}}\circ\iota_{i}=\iota_{i}$, while for the second we have
$\tau_{R^{\mathcal{S}}}\circ H_{i}=\iota_{i}=\iota_{min}\circ\iota_{i}$, where
the second equality holds because $i$ is minimal.

Suppose now that $H_{\bullet}$ and $H^{\tau}_{\bullet}$ are defined for all
$j<i$, naturally in $j$. Then they induce functors $H_{<i}:E_{<i}\to
R^{\mathcal{S}}$ and $H^{\tau}_{<i}:E_{<i}\to E_{min}$. By induction
hypothesis those satisfy the following equations:

$\sigma_{R^{\mathcal{S}}}\circ
H_{<i}=\iota_{<i}\qquad\tau_{R^{\mathcal{S}}}\circ H_{<i}=\iota_{min}\circ
H_{<i}^{\tau}\qquad H_{<i}^{\tau}\circ\iota_{j}=\iota_{j}\text{, where $j\in
I_{min}$.}$

Before defining $H_{i}$ let us consider the two maps $h_{i}$ and $H_{<i}\circ
h_{i}^{\tau}$, from $E_{i}$ to respectively $R$ and $R^{\mathcal{S}}$. Notice
that we have $\tau_{R}\circ h_{i}=\iota_{<i}\circ
h^{\tau}_{i}=\sigma_{R^{\mathcal{S}}}\circ H_{<i}\circ h^{\tau}_{i}$, and so
these two maps induce a map $\langle h_{i},H_{<i}\circ
h_{i}^{\tau}\rangle:E_{i}\to RR^{\mathcal{S}}$. We finally define:

$H_{i}:=m_{R}\circ\langle h_{i},H_{<i}\circ h_{i}^{\tau}\rangle\qquad
H^{\tau}_{i}:=H^{\tau}_{<i}\circ h^{\tau}_{i}.$

The fact that $H_{i}$ and $H_{i}^{\tau}$ satisfy the required equations in all
cases is then a straightforward verification.

##  6 From local to global confluence

The goal of this section is to give a local confluence criteria in order to
prove confluence. In this section, we suppose that $\mathcal{C}$ is a locally
finitely presentable category.

######  Definition 6.1.

Let $(R,h,h^{\tau})$ be a terminating graph over a filtered object $E$. A
_local-confluence structure_ (or _lc-structure_ for short) on $(R,h,h^{\tau})$
is the structure of a $J$-filtered object on $R$, where $J$ is the category
associated to a total terminating order such that $R_{min}=\emptyset$, and a
natural transformation $c_{\bullet}:R_{\bullet}\Rightarrow
R_{<\bullet}^{\mathcal{S}}$ satisfying the equations:

$\sigma_{R^{\mathcal{S}}}\circ\iota^{\mathcal{S}}_{<\bullet}\circ
c_{\bullet}=\tau_{R+E}\circ
h\circ\sigma_{R_{\bullet}}\qquad\tau_{R^{\mathcal{S}}}\circ\iota^{\mathcal{S}}_{<\bullet}\circ
c_{\bullet}=\tau_{R_{\bullet}}$

The reason for the restriction to the case where $\mathcal{C}$ is locally
finitely presentable, and $J$ is total is the following lemma, that we
implicitly use in the proof of Theorem 6.4.

######  Lemma 6.2.

Let $\mathcal{C}$ be a locally finitely presented category, and let $R$ be a
graph on a filtered object $E$. Suppose that $R$ is $J$-filtered. Then

  * •

The functor $(R_{\bullet})^{*}:J\to\mathcal{C}$ is a $J$-filtration of
$R^{*}$.

  * •

If $J$ is total, then for any $j\in J$, $(R_{<j})^{\mathcal{S}}=(R^{*})_{<j}$.

In addition, the same properties hold for $R+R^{\circ}$, and thus for
$R^{\mathcal{S}}$.

######  Proof 6.3.

Since colimits commute with colimits, we just have to prove that
$\operatorname{colim}_{j}R_{j}^{\times_{E}n}=R^{\times_{E}n}$. For $n=0,1$
this is clear. Let us treat the case $n=2$, the general case being similar.
Note first that since $J$ is directed the inclusion $J\to J\times J$ is final,
and so
$\operatorname{colim}_{j}R_{j}\times_{E}R_{j}=\operatorname{colim}_{i,j}R_{i}\times_{E}R_{j}$.
Finally in a locally finitely presentable category pullbacks preserve directed
colimits [1, Proposition 1.59], and so we get:

$\operatorname{colim}_{j}R_{j}\times_{E}R_{j}=\operatorname{colim}_{i}(\operatorname{colim}_{j}(R_{i}\times_{E}R_{j}))=\operatorname{colim}_{i}(R_{i}\times_{E}R)=R\times_{E}R$

To compute $(R_{<j})^{*}$ we use the same technique, using the face that since
$J$ is total then $I_{<j}$ is still directed.

The case of $R+R^{\circ}$ is clear since colimits commute with colimits, and
the case of $R^{\mathcal{S}}$ follows by combining the two previous cases.

######  Theorem 6.4 (Newman’s Lemma for graphs).

Let $(R,h,h^{\tau})$ be a terminating graph over a filtered object $E$,
equipped with an lc-structure. Then the strategy induced by $(R,h,h^{\tau})$
on $R^{\mathcal{S}}$ is confluent.

In particular, $E/R=E/R^{\mathcal{S}}=E_{min}$.

######  Proof 6.5.

Let us prove by induction on $j\in J$ that the equality
$H^{\tau}\circ\sigma_{R_{j}^{\mathcal{S}}}=H^{\tau}\circ\tau_{R_{j}^{\mathcal{S}}}$
holds.

Suppose first that $j$ minimal. Since $R_{min}=\coprod_{j\in
J_{min}}R_{j}=\emptyset$, then $R_{j}=\emptyset$. The required equation thus
holds by unicity of the maps from the initial object.

Otherwise, by induction we have
$H^{\tau}\circ\sigma_{R_{<j}^{\mathcal{S}}}=H^{\tau}\circ\tau_{R_{<j}^{\mathcal{S}}}$.
Then we get $H^{\tau}\circ\sigma_{R_{j}}=H^{\tau}\circ\tau_{R_{j}}$. Indeed we
have:

$\displaystyle H^{\tau}\circ\sigma_{R_{j}}$
$\displaystyle=H^{\tau}\circ\tau_{R+E}\circ h\circ\sigma_{R_{j}}$
$\displaystyle=H^{\tau}\circ\sigma_{R^{\mathcal{S}}}\circ\iota^{\mathcal{S}}_{<j}\circ
c_{j}$
$\displaystyle=H^{\tau}\circ\tau_{R_{j}^{\mathcal{S}}}\circ\iota_{<j}\circ
c_{j}$ $\displaystyle=H^{\tau}\circ\tau_{R_{j}}$

By exchanging the roles of $\sigma_{R_{j}}$ and $\tau_{R_{j}}$, the same
equality holds for $R_{j}^{\circ}$. Let us denote by $T$ the sum
$R_{j}+R_{j}^{\tau}$ and by $T^{n}$ the limit $T^{\times_{E}n}$, and let us
show that for all $n\in\mathbb{N}$,
$H^{\tau}\circ\sigma_{T^{n}}=H^{\tau}\circ\tau_{T^{n}}$. For $n=1$ this is the
previous discussion. For $n=0$ $\sigma_{T^{0}}$ and $\tau_{T^{0}}$ coincide
and the equality holds. Finally for $n\geq 2$ we have, using repeatedly $n=1$:

$H^{\tau}\circ\sigma_{T^{n}}=H^{\tau}\circ\sigma_{T}\circ\pi_{1}=H^{\tau}\circ\tau_{T}\circ\pi_{1}=H^{\tau}\circ\sigma_{T}\circ\pi_{2}=\ldots=H^{\tau}\circ\tau_{T}\circ\pi_{n}=H^{\tau}\circ\tau_{T^{n}}.$

Putting all those equalities together we finally get
$H^{\tau}\circ\sigma_{R^{\mathcal{S}}_{j}}=H^{\tau}\circ\tau_{R^{\mathcal{S}}_{j}}$,
and by colimit
$H^{\tau}\circ\sigma_{R^{\mathcal{S}}}=H^{\tau}\circ\tau_{R^{\mathcal{S}}}$.
Hence $H$ is indeed a confluent strategy on $R^{\mathcal{S}}$. The equality
$E/R^{\mathcal{S}}=E_{min}$ follows by Proposition 5.3, and
$E/R=E/R^{\mathcal{S}}$ by Lemma 3.6.

######  Example 6.6.

Let $(E,\to)$ be a set equipped with a terminating relation. Following Example
4.9, we can equip $E$ with an $\mathbb{N}$-filtered structure, and $\to$
induces a terminating graph $R=\\{(x,y)|x\to y\\}$ on $E$. Then there is a
canonical filtration of $R$ given by the following pullback:

${R_{j}}$${E_{j}}$${R}$${E.}$$\scriptstyle{\iota_{j}}$$\scriptstyle{\sigma_{R}}$

Since $\operatorname{Set}$ is locally finitely presented, pullbacks preserve
directed colimits and thus $\operatorname{colim}_{j}R_{j}=R$. More precisely,
$(x,y)\in R$ lies in $R_{j}$ if and only if $x$ lies in $E_{j}$. In particular
$R_{0}=\emptyset$ since $E_{0}$ is the set of normal forms of $\to$.

Then the existence of an lc-structure $c_{\bullet}$ on $R$ is equivalent to
the existence for any $r=(x,y)\in R$ of some equivalence path
$c(r):h^{\tau}(x)\xleftrightarrow{*}y$ of shape:

${x}$${y}$${h^{\tau}(x)}$$\scriptstyle{r}$$\scriptstyle{h(x)}$$\scriptstyle{c(r)}$

such that any rewriting step occurring in $c(x)$ has source smaller than $x$.
This is true whenever $\to$ is locally confluent, and Theorem 6.4 recovers
that $R$ is confluent.

The same phenomenon applies to the case $\mathcal{C}=\operatorname{Ab}$, which
is also locally finitely presented.

######  Note 6.7.

The idea of ordering the relations is not new in abstract rewriting, and is
for example the main idea behind van Oostrom’s notion of decreasing diagrams
[10]. In fact when specialised to the case $\mathcal{C}=\operatorname{Set}$,
Theorem 6.4 (which is more general than Newman’s Lemma since, as noted in
Example 4.8, termination in the sense of Definition XX is more geenral than
the ususal termination of relations) is a direct consequence of [10, Theorem
3.7]

## References

  * [1] Jiří Adámek and Jiří Rosický.  Locally presentable and accessible categories, volume 189 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 1994.  URL: https://doi.org/10.1017/CBO9780511600579, doi:10.1017/CBO9780511600579.
  * [2] George M. Bergman.  The diamond lemma for ring theory.  Adv. in Math., 29(2):178–218, 1978.  URL: https://doi.org/10.1016/0001-8708(78)90010-5, doi:10.1016/0001-8708(78)90010-5.
  * [3] Cyrille Chenavier and Maxime Lucas.  The diamond lemma for non-terminating rewriting systems using deterministic reduction strategies.  2019\.
  * [4] Thomas Ehrhard and Laurent Regnier.  The differential lambda-calculus.  Theoret. Comput. Sci., 309(1-3):1–41, 2003.  URL: https://doi.org/10.1016/S0304-3975(03)00392-X, doi:10.1016/S0304-3975(03)00392-X.
  * [5] Yves Guiraud, Eric Hoffbeck, and Philippe Malbos.  Convergent presentations and polygraphic resolutions of associative algebras.  Math. Z., 293(1-2):113–179, 2019.  URL: https://doi.org/10.1007/s00209-018-2185-z, doi:10.1007/s00209-018-2185-z.
  * [6] Yves Guiraud and Philippe Malbos.  Higher-dimensional categories with finite derivation type.  Theory Appl. Categ., 22:No. 18, 420–478, 2009.
  * [7] Maxime Lucas.  Cubical categories for homotopy and rewriting.  Theses, Université Paris 7, Sorbonne Paris Cité, December 2017\.  URL: https://hal.archives-ouvertes.fr/tel-01668359.
  * [8] Philippe Malbos and Samuel Mimram.  Homological computations for term rewriting systems.  In 1st International Conference on Formal Structures for Computation and Deduction, volume 52 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 27, 17. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016.
  * [9] Craig C. Squier, Friedrich Otto, and Yuji Kobayashi.  A finiteness condition for rewriting systems.  Theoret. Comput. Sci., 131(2):271–294, 1994.  URL: https://doi.org/10.1016/0304-3975(94)90175-9, doi:10.1016/0304-3975(94)90175-9.
  * [10] Vincent van Oostrom.  Confluence by decreasing diagrams converted.  In Rewriting techniques and applications, volume 5117 of Lecture Notes in Comput. Sci., pages 306–320. Springer, Berlin, 2008.  URL: https://doi.org/10.1007/978-3-540-70590-1_21, doi:10.1007/978-3-540-70590-1_21.
  * [11] Lionel Vaux.  The algebraic lambda calculus.  Math. Structures Comput. Sci., 19(5):1029–1059, 2009.  URL: https://doi.org/10.1017/S0960129509990089, doi:10.1017/S0960129509990089.