# Critical properties of the quantum Ashkin-Teller chain with chiral
perturbations

Bernhard E. Lüscher  Institute of Physics, University of Zürich, Rämistrasse
71, 8006 Zürich, Switzerland  Frédéric Mila  Institute of Physics, Ecole
Polytechnique Fédérale de Lausanne (EPFL), CH-1015 Lausanne, Switzerland
Natalia Chepiga  Kavli Institute of Nanoscience, Delft University of
Technology, Lorentzweg 1, 2628 CJ Delft, The Netherlands

(August 31, 2024)

###### Abstract

We investigate the nature of the phase transitions in the quantum Ashkin-
Teller chain in the presence of chiral perturbations. We locate the Lifshitz
line separating a region of direct chiral transitions from the region where
the transition is through an intermediate floating phase. Furthermore, we
identify a small region in the vicinity of the four-state Potts point where
chiral perturbations are irrelevant and where the transition remains
conformal. Implications to Rydberg atoms experiments are briefly discussed.

###### pacs:

75.10.Jm,75.10.Pq,75.40.Mg

##  I Introduction

The theory of quantum phase transitions in low-dimensional systems plays a
central role in modern condensed matter physicsGiamarchi (2004); Tsvelik
(2003). One of the most challenging and long-standing problems is the
commensurate-incommensurate (C-IC) melting of a period-$p$ phase originally
formulated in the context of absorbed monolayersHuse and Fisher (1982); Selke
and Yeomans (1982); Schulz (1983); Haldane  _et al._ (1983); Huse and Fisher
(1984); Schreiner  _et al._ (1994). Huse and Fisher noticed that domain walls
between different ordered domainsHuse and Fisher (1982, 1984), for instance
$A|B$ and $B|A$, might have different free energy contributions, introducing
chiral perturbations into the problem. For the period-2 phase these chiral
perturbations are irrelevant and the transition is in the Ising universality
class. For period-$p$ phases with $p\geq 5$ the transition is always through
an intermediate critical phase separated from the ordered phase by a
Pokrovsky-TalapovPokrovsky and Talapov (1979) and from the disordered phase by
a Kosterlitz-ThoulessKosterlitz and Thouless (1973) transition.

The most interesting cases, however, are transitions out of the period-3 and
period-4 phases. In the absence of chiral perturbations the transition out of
the $p=3$ phase is in the 3-state Potts universality class that, as the Ising
transition, can be described by a corresponding minimal model of the conformal
field theoryDi Francesco  _et al._ (1997). For strong chiral perturbations,
the transition is a two-step process via an intermediate critical phase, as
for $p\geq 5$. However, in the presence of weak chiral perturbations, the
transition is believed to be a direct one in a new chiral universality
classHuse and Fisher (1984). The melting of the $p=4$ phase, encapsulated by
the physics of the Ashkin-Teller model, is even more complicated. Again, in
the absence of chiral perturbation, the transition belongs to the Ashkin-
Teller universality class that can be described by a conformal field theory
with central charge $c=1$Di Francesco  _et al._ (1997). However, in this case
weak chiral perturbations may or may not give rise to a direct chiral
transitionden Nijs (1988) depending on the properties of the Ashkin-Teller
point itself. For instance, in the limit of the Ashkin-Teller model equivalent
to two decoupled Ising chains, a chiral perturbation immediately opens up an
intermediate incommensurate Luttinger liquid phase with a diverging
correlation length, a phase known as a floating phaseOstlund (1981); Nelson
and Halperin (1979). In the opposite limit equivalent to the symmetric four-
state Potts model, field theory arguments predict that weak chiral
perturbations are irrelevant and that the transition remains direct and
conformalSchulz (1983). But what happens between these two limits? According
to Huse and FisherHuse and Fisher (1984) there might be room for a chiral
transition and numerical results in the context of Rydberg atoms have given
the first evidence that this is indeed the caseChepiga and Mila (2021a). This
scenario is further supported by numerical simulations of the classical
symmetric two-dimensional (2D) Ashkin-Teller model on a square lattice where
the Lifshitz line - the boundary of chiral transition - was accurately located
with a Corner Transfer Matrix Renormalizationgroup (CTMRG) algorithm Nyckees
and Mila (2022). Yet another feature of the melting out of a $p=4$ phase - the
possibility of a conformal transition for a non-vanishing chiral perturbation
- remains unexplored. If the transition remains conformal even in the presence
of chiral perturbations, the dynamical critical exponent $z$ must keep its
value $z=1$, and there must be a quantitative correspondence between the
classical 2D chiral Ashkin-Teller model on a square lattice and its quantum 1D
version on a chain.

Recent progress in Rydberg atoms experimentsBernien  _et al._ (2017); Keesling
_et al._ (2019) brings this old problem into the main focus of theoretical
research now in the context of quantum 1D chains. The phase diagram of a
Rydberg atoms array is dominated by lobes of integer periodicities
$p=2,3,4,5...$Keesling  _et al._ (2019); Rader and Läuchli (2019) while the
distance-dependent van der Waals interaction makes the disorder phase
surrounding these ordered lobes incommensurate. This makes a 1D array of
Rydberg atoms an ideal playground to probe quantum commensurate-incommensurate
meltingWhitsitt  _et al._ (2018a); Chepiga and Mila (2019a, b); Giudici  _et
al._ (2019); Whitsitt  _et al._ (2018b); Chepiga and Mila (2021b, a); Maceira
_et al._ (2022). Numerical simulations of quantum phase transitions out of the
period-4 lobe in Rydberg chains show that they are qualitatively very similar
to the transition out of the period-3 phaseChepiga and Mila (2021a): the
conformal transition is realized at a single point and is surrounded by a
direct chiral transition before the floating phase opens. The new developments
in Rydberg atoms open the way to tune the conformal point within the Ashkin-
Teller family and, in principle, can bring it to the point where the floating
phase opens up immediately or to the point where the conformal transition
extends to a finite interval.

In the present paper we provide numerical evidence that a conformal transition
can be realized even in the presence of weak chiral perturbations and define a
scale on which interactions can be treated as weak for the quantum Ashkin-
Teller model. We also locate the Lifshitz line, i.e. the position in the phase
diagram where the direct chiral transition is replaced by the floating phase.
Our main results are summarized in the phase diagram presented in Fig.1. The
rest of the paper is organized as follows. In Section II we define the Ashkin-
Teller model and provide the details of the numerical algorithm. In Section
III we present our results including the detailed overview of the phase
diagram and we provide numerical evidence in favour of a conformal transition
in the presence of non-zero chiral perturbations. In Section IV we summarized
the results and put them into perspective.

Figure 1: Nature of the quantum phase transition between the ordered phase
with a four-fold degenerate ground state and the disordered phase of the
quantum Ashkin-Teller model defined by the Hamiltonian 2 as a function of
$\lambda$ and $\delta$. Along $\delta=0$ the transition is in the Ashkin-
Teller universality class. For $\lambda\lesssim 0.5$ we observe an
intermediate floating phase (green) for any non-zero value of chiral coupling
$\delta$. For $\lambda\gtrsim 0.5$ the transition is direct in the chiral
universality class (light blue) below the Lifshitz line (red) and through the
floating phase above it. For $\lambda\gtrsim 0.977$ we find that the
transition remains direct and conformal in the Ashkin-Teller universality
class (dark blue) for $\delta\lesssim 0.04$.

##  II Model & Methods

###  II.0.1 The Quantum Ashkin-Teller Model

In the quantum Ashkin-Teller model two Ising spins per site,
$\hat{\sigma}_{i}$ and $\hat{\tau}_{i}$, are introduced and embedded into a
Hamiltonian of the form

$\begin{split}\hat{H}_{0}=-&\sum_{i}\left(\hat{\sigma}^{x}_{i}+\hat{\tau}^{x}_{i}+\lambda\hat{\sigma}^{x}_{i}\hat{\tau}^{x}_{i}\right)\\\
-\beta&\sum_{i}\left(\hat{\sigma}^{z}_{i}\hat{\sigma}^{z}_{i+1}+\hat{\tau}^{z}_{i}\hat{\tau}^{z}_{i+1}+\lambda\hat{\sigma}^{z}_{i}\hat{\sigma}^{z}_{i+1}\hat{\tau}^{z}_{i}\hat{\tau}^{z}_{i+1}\right).\end{split}$
(1)

This model displays Kramers-Wannier self-duality at $\beta=1$. This point
corresponds to a quantum phase transition between an ordered phase at large
$\beta$ and a disordered phase at small $\beta$Kohmoto  _et al._ (1981). It is
in the Ashkin-Teller universality class with exponents that vary continuously
with $\lambda$.

A chiral perturbation can be introduced by complementing (1) with a term
$-\delta\sum_{i}\left(\hat{\sigma}^{z}_{i}\hat{\tau}^{z}_{i+1}-\hat{\tau}^{z}_{i}\hat{\sigma}^{z}_{i+1}\right)$
Schulz (1983) to give

$\hat{H}=\hat{H}_{0}-\delta\sum_{i}\left(\hat{\sigma}^{z}_{i}\hat{\tau}^{z}_{i+1}-\hat{\tau}^{z}_{i}\hat{\sigma}^{z}_{i+1}\right).$
(2)

At non-zero $\delta$ the model is no longer self-dual, and the location of the
quantum phase transition as a function of $\beta$ is not known exactly.
Regarding the nature of the transition, on theoretical grounds it is known
that the crossover exponent $\phi$ for the chiral perturbation is given by
Schulz (1983)

$\phi=\frac{3\nu}{2}+\frac{1}{4}-\frac{\nu^{2}}{2\nu-1}.$ (3)

Here, $\nu$ is the correlation length critical exponent which, in the case of
vanishing chiral perturbation $\delta=0$, is known exactly as a function of
the parameter $\lambda$,

$\nu=\frac{1}{2-\frac{\pi}{2}\left[\arccos\left(-\lambda\right)\right]^{-1}}.$
(4)

The chiral perturbation $\delta$ is relevant if $\phi>0$, which is the case
for $\nu>\nu_{c}=\left(1+\sqrt{3}\right)/4\simeq 0.683$. This leads to a
critical value of $\lambda$Kohmoto  _et al._ (1981); O’Brien  _et al._ (2015),

$\lambda_{c}=-\cos\frac{\pi\left(\sqrt{3}+1\right)}{4\left(\sqrt{3}-1\right)}\simeq
0.9779,$ (5)

below which the chiral perturbation $\delta$ is always relevant. In the
aforementioned numerical simulation of the Rydberg chain, it was found that
away from the commensurate line, the melting of the period-four phase
immediately occurs in the chiral universality class Chepiga and Mila (2021a)
introduced by Huse and FisherHuse and Fisher (1982). It is found that the
conformal transition along the commensurate line is of the Ashkin-Teller type
with a critical exponent of $\nu\simeq 0.78$Chepiga and Mila (2021a); Maceira
_et al._ (2022), i.e. with a value well into the regime where the chiral
perturbation is relevant. Consistently it is found that away from the
commensurate line, the chirality of the problem immediately drives the
transition into the chiral universality class. Considering the Ashkin-Teller
model however, there should be a region in the phase diagram
($\lambda_{c}<\lambda\leq 1$) where $\delta$ is non-vanishing, but the C-IC
transition remains in the Ashkin-Teller universality class. The phase diagram
is presented in Figure 1.

Originally, the Ashkin-Teller model was introduced as a classical model in
statistical physics Ashkin and Teller (1943). Via the well established 2D
classical to 1D quantum correspondence, the Hamiltonian of the quantum Ashkin-
Teller model can be obtained by considering the highly anisotropic limit of
the 2D classical model on a square latticeKohmoto  _et al._ (1981) . Numerical
results on the classical ferromagnetic chiral Ashkin-Teller model on the
square lattice obtained with a CTMRG algorithmNyckees and Mila (2022) are in
qualitative agreement with the phase diagram presented in Fig. 1. In this
paper we explore the vicinity of the four-state Potts point where the main
field theory prediction that chiral perturbations are irrelevant is still
waiting for numerical verification.

###  II.0.2 Algorithm

We address the problem numerically with state-of-the art density matrix
renormalization group algorithmWhite (1992); Schollwöck (2005); Östlund and
Rommer (1995); Schollwöck (2011). To obtain the ground state in MPS-form we
use a two-site DMRG algorithm, see for instance Ref.Schollwöck, 2011. The fact
that we are dealing with a local Hilbert space of dimension $d=4$
significantly increases the complexity of the algorithm and in turn limits the
maximum bond dimension $D$ that we can reach to $D_{\mathrm{max}}=200-500$. To
ensure convergence both in bond dimension and in the number of sweeps, the
bond dimension was increased after every half-sweep in steps of 20 to arrive
at $D_{\mathrm{max}}$. We treat the wave-function as converged when the
ground-state energy does not change more than by $10^{-6}$ during one sweep.

A boundary term
$-\epsilon\left(\hat{\sigma}_{1}^{z}+\hat{\sigma}_{1}^{z}\hat{\tau}_{1}^{z}+\hat{\sigma}_{N}^{z}+\hat{\sigma}_{N}^{z}\hat{\tau}_{N}^{z}\right)$,
where $N$ is the system size and epsilon some positive constant of the order
of the ground state energy density per site, was introduced to break the
4-fold degeneracy of the ground state and to make sure one ends up in a state
with non-vanishing local magnetization $\left<\hat{\sigma_{i}^{z}}\right>$.

With this DMRG algorithm we could simulate quantum chains with sufficient
accuracy to distinguish chiral and conformal transitions in the vicinity of
the four-state Potts point and in the presence of chiral perturbations.

###  II.0.3 Distinguishing chiral transition and floating phase

To distinguish the different types of phase transitions, one needs a quantity
that reliably sets the transitions apart from one another. Huse and Fisher
argue that such a quantity is provided by the product of the
incommensurability wave vector $q$ and the correlation length $\xi$. Generally
it is expected that the wave vector $q$ approaches the commensurate value $0$
with an exponent $\bar{\beta}$. While this exponent is not exactly known in
the case of the Ashkin-Teller model, it is argued that $\bar{\beta}>\nu$ as
soon as the transition is conformal. This implies that upon approaching the
transition the product $q\times\xi$ will decay to 0. In contrast, for a chiral
transition $\bar{\beta}=\nu$ and the product $q\times\xi$ remains finite upon
approaching the transition. Since the chiral transition is direct, the
exponent $\nu$ should be the same coming from either side of the transition.
In the case of a floating phase, the system is critical, i.e. it has a
diverging correlation length, while $q$ is still non-vanishing. This implies
that on the incommensurate side one will observe $q\times\xi$ to be diverging
towards the transition. Coming from the commensurate side, the transition will
occur via a Pokrovsky-Talapov transition, implying a correlation length
diverging with an exponent $\nu=\frac{1}{2}$ Pokrovsky and Talapov (1979).

###  II.0.4 Extraction of the correlation length and of the wave vector

Using the notation introduced in Eq. (1), we consider the connected
correlation function of the operators $\sigma^{z}_{i}$:

$C^{\sigma}_{ij}=\left<\hat{\sigma}^{z}_{i}\hat{\sigma}^{z}_{j}\right>-\left<\hat{\sigma}^{z}_{i}\right>\left<\hat{\sigma}^{z}_{j}\right>,$
(6)

where $i$ and $j$ denote the different sites. The correlation length $\xi$ as
well as the wave vector $q$ are extracted by fitting the correlation function
to the Ornstein-Zenicke formOrnstein and Zernike (1914),

$C^{\sigma}_{ij}\propto\frac{\exp\left(-\frac{|i-j|}{\xi}\right)}{\sqrt{|i-j|}}\cos\left(q|i-j|+\varphi\right).$
(7)

This is attained by first fitting the correlation length, as is indicated in
Figure (2a). When considering $\log\left(C^{\sigma}_{ij}\right)$, one easily
sees that within the bulk, the maxima of the oscillations decay linearly as a
function of $|i-j|$, with a slope of $-\frac{1}{\xi}$. Making use of this, one
can then rescale $C^{\sigma}_{ij}$ with a factor
$\exp\left(\frac{|i-j}{\xi}|\right)$, which then allows to fit the wave vector
$q$, as indicated in Figure (2b).

Figure 2: Example of (a) the logarithm of $C^{\sigma}_{ij}$ as a function of
the distance of two sites $|i-j|$ including a fit for the “crest” of the
oscillations and of (b) the corresponding rescaled correlation function, which
is then used to extract $q$.

This procedure works very well for most of the points of the phase diagram. A
problem arises when $q$ is very small, which is the case at the points close
to the Ashkin-Teller line. The problem is due to the fact that for small $q$,
the correlation function reaches machine precision before the elapse of a
whole period, making it very difficult to properly fit the oscillations with a
wave vector $q$. The way this issue was dealt with was by approaching the
transition from a direction in parameter space where the oscillation period
was smaller.

###  II.0.5 Identifying the Lifshitz Line

As already mentioned, the estimate of the Lifshitz line was obtained by
scanning the phase diagram along the $\delta$-axis for given values of
$\lambda$. The estimate was then made by considering the behaviour of $\xi$
and $q\times\xi$ at the transition for different values of $\delta$. We know
that at a chiral transition, the critical exponents for the correlation length
coming from either the commensurate or the incommensurate phase ($\nu_{left}$
and $\nu_{right}$) should match. Also if there is an intermediate floating
phase there should be a change in curvature on the $\frac{1}{\xi}$-plot due to
the scaling of the correlation length
$\xi\sim\exp(\frac{c}{\sqrt{\beta-\beta_{c}}})$, as well a diverging behaviour
in $q\times\xi$ close to criticality. Figure (3) shows two plots along the
$\delta$-axis for $\lambda=1$.

Figure 3: Plots of $\frac{1}{\xi}$ and $q\times\xi$ around criticality at
$\lambda=1$ and $\delta=1.1$ (a and b), as well as at $\delta=1.0$ (c and d)
and $\delta=0.7$ (e and f). The simulations were carried out on three
different system sizes $N=400$, $N=700$ and $N=1000$. In (a) and (b) one can
see indications of an intermediate floating phase, namely the mismatch of the
critical exponents $\nu_{left}$ and $\nu_{right}$ as well as a tendency to a
convex behaviour close to the criticality coming from the left. There is also
a clear increase in $q\times\xi$ close to the critical point. In (c) and (d)
the results can be seen to be inconclusive as to whether the transition occurs
in the chiral universality class or via a floating phase. In (e) and (f)
everything points towards a chiral transition.

Whereas in the Figure (3a) and (3b) everything points toward a critical
floating phase at $\lambda=1$, $\delta=1.1$, Figures (3e) and (3f) point
towards a chiral transition at $\lambda=1$, $\delta=0.7$. Considerations like
these enable one to map out the different phases and put an estimate, albeit a
very approximate one, for the Lifshitz point.

##  III Results

###  III.0.1 Phase Diagram

The qualitative phase diagram we found is presented in Figure 1. This diagram
should be understood as follows. For every pair of parameters
$(\lambda,\delta)$ displayed in the two-dimensional plot there is a particular
value of the parameter $\beta$, introduced in (1), where the C-IC transition
occurs. One can understand Figure 1 as the depiction of the nature of phase
transitions occurring on a two-dimensional critical surface embedded in a
three-dimensional parameter space. This is further illustrated in Figure (4).

Figure 4: Qualitative sketch of the nature of the quantum phase transitions
between the ordered phase with a four-fold degenerate ground state and the
disordered phase of the quantum Ashkin-Teller model defined by the Hamiltonian
of Eq.(2) as a function of $\lambda$, $\beta$, and $\delta$.

Around $\lambda\simeq 0.5$ we find that a non-vanishing value of $\delta$
immediately causes a floating phase to open up, whereas for
$0.5\lesssim\lambda\lesssim 0.98$ the transition remains direct but in the
chiral universality class once a non-vanishing chiral perturbation is
introduced. Furthermore, we identify a small region $\lambda_{c}<\lambda\leq
1$ in which the transition occurs in the Ashkin-Teller universality class for
small but non-zero values of $\delta$.

###  III.0.2 $\lambda=1$

At $\lambda=1$ it is conjectured that with increasing $\delta$, different
phase transitions can be observed. As mentioned above, for
$0.9779\leq\lambda\leq 1$ it is expected that when introducing a small but
finite perturbation $\delta$, the incommensurate-commensurate transition still
occurs in the Ashkin-Teller universality class. To examine this, simulations
were carried out at $\lambda=1$ for different values of $\delta$. For a given
pair of $\lambda$ and $\delta$, the critical point $\beta_{c}$ was identified,
and in its proximity the incommensurability wave vector $q$ as well as the
correlation length $\xi$ were extracted in order to consider the quantity
$q\times\xi$ close to the transition. For $\lambda=1$ simulations across the
critical surface were carried out for a multitude of values of $\delta$. Each
critical point was approached at 3 different angles and the scaling of
$q\times\xi$ of the different cuts was compared. The value of $q\times\xi$ for
each cut at the transition (intercept) was extracted. The average intercept
for the three cuts was then computed.

Figure 5: $q\times\xi$ at the C-IC transition as a function of chiral coupling
$\delta$ for (a) $\lambda=1$, (b) $\lambda=0.98$, and (c) $\lambda=0.8$. The
dashed lines in (a) and (b) indicate the value of $\delta^{c}$ associated with
the point where $q\times\xi$ vanishes and below which the transition is
conformal. The dotted line is a linear fit.

As can be seen in Figure (5a), as $\delta$ decreases, so does the value of the
intercepts. Taking the errors into consideration, this suggests that
$q\times\xi$ goes to zero around $\delta\simeq 0.05$. This would suggest that
for $\delta$ smaller than this value, the incommensurate-commensurate
transition actually occurs via an Ashkin-Teller type transition. In Figure
(6b) we can see $q\times\xi$ going to zero at the transition at $\lambda=1$
and $\delta=0.04$.

Figure 6: The scaling of the quantity $q\times\xi$ with the distance to the
C-IC transition at (a) $\lambda=0.98$, $\delta_{crit}=0.04$ and at (b)
$\lambda=1$, $\delta_{crit}=0.04$

###  III.0.3 $\lambda=0.98$

The same procedure was carried out for $\lambda=0.98$. As for $\lambda=1$, we
find $q\times\xi$ going to zero around $\delta\simeq 0.05$, Figure (5b).
Figure (6a) seems to confirm that the incommensurate-commensurate transition
for $\lambda=0.98$ and $\delta=0.04$ occurs in the Ashkin-Teller universality
class. As a comparison, we carried out the same procedure for $\lambda=0.8$
where we know the chiral perturbation to be immediately relevant. In Figure
(5c) we see that, by contrast to $\lambda=1$ and $\lambda=0.98$, the quantity
$q\times\xi$ at the transition only vanishes for $\delta=0$

###  III.0.4 Chiral Transition

It is conjectured that for $\lambda$ and $\delta$ large enough there will be a
region in the phase diagram where the IC-C transition occurs via a chiral
transition, characterized by the convergence of $q\times\xi$ upon approaching
the transition. Indeed, the results of Section 1 seem to confirm this
conjecture in the region of the phase diagram with $\lambda\simeq 1$ and
$\delta\geq 0.05$. This can be examplified by considering the value
$\delta=0.4$ at $\lambda=1$. This $\delta$-value is considerably larger than
$\delta=0.05$, but still small enough that the transition does not occur via a
floating phase. The results of the simulation for $q\times\xi$ of three
different cuts are shown in Figure (7a). Independent of the angle at which the
transition was approached in parameter space, $q\times\xi$ approaches the same
value.

Figure 7: (a) $q\times\xi$ as the IC-C transition is approached at
$\lambda=1$, $\delta=0.4$. Every cut stands for a different direction in the
plane spanned by the parameters ($\delta,\beta$) at which the transition is
approached. (b) The inverse of the correlation length across the IC-C
transition at $\lambda=1$, $\delta=0.4$. For the fit, the two exponents
$\nu_{left}$ and $\nu_{right}$ as well as the point $\beta_{critical}$, at
which the transition occurs, were fitted simultaneously.

To further substantiate the nature of this transition as chiral, the behaviour
of the correlation length was considered on both sides of the transition.
Figure (7b) shows that the critical exponents $\nu$ of the correlation length
for both sides of the transition match, as predicted by Huse and Fisher.

###  III.0.5 Lifshitz Line

For any value of $\lambda$ there is a $\delta$ large enough to open up a
floating phase. Since every point where the floating phase opens up stands at
the boundary of 3 different phases, we refer to the set of those points as
Lifshitz line. An accurate location of the Lifshitz line is an extremely
challenging task and the Lifshitz line presented in the Fig.1 is defined up to
an error $\Delta\delta\pm 0.05$. In agreement with classical results, we
observe that for $\lambda\lesssim 0.5$ a floating phase opens up immediately
once a chiral perturbation $\delta$ is introduced. Also, the diagram indicates
the small region close to $\lambda=1$ where we observe an Ashkin-Teller
transition for finite $\delta$.

To obtain a qualitative idea of the phase diagram including the Lifshitz-line,
simulations were also carried out for values of $\lambda$ smaller than $1$.
The exact determination of the Lifshitz point for a given $\lambda$ is
virtually impossible with the methods we used. One can however end up with a
reasonable estimate by simply scanning the phase diagram.

In Figure 1 one can see a qualitative diagram indicating the range in
parameter space of the different types of transitions.

##  IV Discussion

In the present paper we have investigated the critical properties of the
quantum Ashkin-Teller model on a 1D chain with chiral perturbations. The
resulting phase diagram is in qualitative agreement with the previously
reported phase diagram of the classical symmetric 2D chiral Ashkin-Teller
model on the square lattice. We find clear evidence of the presence of a
region where the C-IC transition occurs in the chiral universality class
predicted by Huse and Fisher. Consistent with the underlying theory we find
that for $\lambda\lesssim 0.98$ a chiral perturbation immediately drives the
C-IC transition out of the Ashkin-Teller universality class into either the
chiral universality class ($0.5\lesssim\lambda$) or the melting via a critical
floating phase ($\lambda\lesssim 0.5$). We map out the location of the
Lifshitz line indicating the boundary between the chiral transition and the
floating phase.

Furthermore, our methods allowed us to examine the effect of a chiral
perturbation in the region $0.98\lesssim\lambda\lesssim 1$, where, on
theoretical grounds, it is known that the perturbation is irrelevant. Indeed
we are able to identify a small domain in the phase diagram where we observe a
C-IC transition in the Ashkin-Teller universality class for finite
perturbations up to the value $\delta\simeq 0.04$. This region has so far not
been observed in the 2D classical chiral Ashkin-Teller model. It would be
interesting to see if the boundary of this phase indeed corresponds to the
critical value $\nu=\nu_{c}=\left(1+\sqrt{3}\right)/4\simeq 0.683$, but with
our current algorithm the precision on $\nu$ is not sufficient to check this
prediction, and this point is left for future investigation.

Finally, let us briefly comment on possible experimental realizations of this
phase diagram with arrays of Rydberg atoms trapped in optical tweezers. As
stated above, the conformal point at the boundary of the period-4 lobe in the
simplest array of Rydberg atoms is characterized by the critical exponent
$\nu\approx 0.78$Chepiga and Mila (2021a); Maceira  _et al._ (2022). However,
recent proposal on multi-component and multi-species Rydberg arraysSingh  _et
al._ (2022); Sheng  _et al._ (2022); Levi  _et al._ (2015); Chepiga (2023);
Covey  _et al._ (2023), add new independent parameters that can be
individually controlled in experiments. This opens a way to tune the conformal
critical point and the Ashkin-Teller asymmetry parameter $\lambda$ and in turn
to manipulate the appearance of the chiral transition at the boundary of the
period-4 phase. A priori, it should be possible to realize the Ashkin-Teller
critical point with $\lambda\gtrsim 0.98$ followed by a finite interval of
conformal transitions. Kibble-Zurek experiments should in principle be able to
check this scenario, but this will require to reach a much higher accuracy
than that currently available.

## Acknowledgments

The authors acknowledge Samuel Nyckees for useful discussions. The work has
been supported by the Swiss National Science Foundation (FM) grant 182179 and
by the Delft Technology Fellowship (NC). Numerical simulations have been
performed on the Dutch national e-infrastructure with the support of the SURF
Cooperative, the facilities of the Scientific IT and Application Support
Center of EPFL and at the DelftBlue HPC.

*

##  Appendix A Approaching a Transition from Different Angles in Parameter
Space

The behaviour of the order parameters across the transition should not depend
on the direction in parameter space along which the transition is approached.
An illustrative example is given by the transition at $\lambda=1,\delta=0.12$.
First, the point of the C-IC transition in $\beta$-space, labeled $\beta_{c}$,
is determined by performing simulations at constant $\lambda$ and $\delta$ on
the commensurate side and then fitting the diverging correlation length,
Figure (8b).

Figure 8: (a) Determining $\beta_{c}$, i.e. the value in $\beta-$space where
the C-IC transition occurs, by fitting the (inverse of the) correlation length
with a power law. (b) The extracted wave vector $q$ for the three different
cuts listed in Table 1. The inset shows an enlarged version of cuts $1$&$2$
close to the transition.

Once $\beta_{c}$ has been determined, the transition is then approached from
different angles in the $\beta-\delta$-plane. Table 1 shows the three
different cuts that were carried out in this particular example. The
corresponding plots of $q$ are shown in Figure (8a).

Table 1: Table of the points that were simulated to examine the behaviour around the transition at $\lambda=1$, $\delta=0.12$ and $\beta=1.001$. Each triplet in a row denotes a point that was simulated. As one can see from the bottom line in the table, each cut aims at the point of the transition, but it is approached from three different angles in the $\beta-\delta$-plane. $\lambda$ is always kept at $1$. Cut $1$ | Cut $2$ | Cut $3$
---|---|---
$\lambda$ | $\beta$ | $\delta$ | $\lambda$ | $\beta$ | $\delta$ | $\lambda$ | $\beta$ | $\delta$
|  |  |  |  |  | 1 | 0.651 | 0.47
|  |  |  |  |  | 1 | 0.701 | 0.42
1 | 0.976 | 0.32 | 1 | 0.976 | 0.37 | 1 | 0.751 | 0.37
1 | 0.981 | 0.28 | 1 | 0.981 | 0.32 | 1 | 0.801 | 0.32
1 | 0.986 | 0.24 | 1 | 0.986 | 0.27 | 1 | 0.851 | 0.27
1 | 0.991 | 0.2 | 1 | 0.991 | 0.22 | 1 | 0.901 | 0.22
1 | 0.996 | 0.16 | 1 | 0.996 | 0.17 | 1 | 0.951 | 0.17
1 | 1.001 | 0.12 | 1 | 1.001 | 0.12 | 1 | 1.001 | 0.12

## References

  * Giamarchi (2004) T. Giamarchi,  _Quantum physics in one dimension_, Internat. Ser. Mono. Phys. (Clarendon Press, Oxford, 2004).
  * Tsvelik (2003) A. M. Tsvelik,  _Quantum Field Theory in Condensed Matter Physics_, 2nd ed. (Cambridge University Press, 2003).
  * Huse and Fisher (1982) D. A. Huse and M. E. Fisher, Phys. Rev. Lett. 49, 793 (1982).
  * Selke and Yeomans (1982) W. Selke and J. M. Yeomans, Zeitschrift für Physik B Condensed Matter 46, 311 (1982).
  * Schulz (1983) H. Schulz, Physical Review B 28, 2746 (1983).
  * Haldane  _et al._ (1983) F. D. M. Haldane, P. Bak, and T. Bohr, Phys. Rev. B 28, 2743 (1983).
  * Huse and Fisher (1984) D. A. Huse and M. E. Fisher, Phys. Rev. B 29, 239 (1984).
  * Schreiner  _et al._ (1994) J. Schreiner, K. Jacobi, and W. Selke, Phys. Rev. B 49, 2706 (1994).
  * Pokrovsky and Talapov (1979) V. L. Pokrovsky and A. L. Talapov, Phys. Rev. Lett. 42, 65 (1979).
  * Kosterlitz and Thouless (1973) J. M. Kosterlitz and D. J. Thouless, Journal of Physics C: Solid State Physics 6, 1181 (1973).
  * Di Francesco  _et al._ (1997) P. Di Francesco, P. Mathieu, and D. Sénéchal,  _Conformal Field Theory_, Graduate Texts in Contemporary Physics (Springer, New York, 1997).
  * den Nijs (1988) M. den Nijs, Phase Transitions and Critical Phenomena 12, 219 (1988).
  * Ostlund (1981) S. Ostlund, Phys. Rev. B 24, 398 (1981).
  * Nelson and Halperin (1979) D. R. Nelson and B. Halperin, Physical Review B 19, 2457 (1979).
  * Chepiga and Mila (2021a) N. Chepiga and F. Mila, Nature Communications 12, 1 (2021a).
  * Nyckees and Mila (2022) S. Nyckees and F. Mila, Physical Review Research 4, 013093 (2022).
  * Bernien  _et al._ (2017) H. Bernien, S. Schwartz, A. Keesling, H. Levine, A. Omran, H. Pichler, S. Choi, A. S. Zibrov, M. Endres, M. Greiner, _et al._ , Nature 551, 579 (2017).
  * Keesling  _et al._ (2019) A. Keesling, A. Omran, H. Levine, H. Bernien, H. Pichler, S. Choi, R. Samajdar, S. Schwartz, P. Silvi, S. Sachdev, _et al._ , Nature 568, 207 (2019).
  * Rader and Läuchli (2019) M. Rader and A. M. Läuchli, “Floating phases in one-dimensional rydberg ising chains,” (2019), arXiv:1908.02068 [cond-mat.quant-gas] .
  * Whitsitt  _et al._ (2018a) S. Whitsitt, R. Samajdar, and S. Sachdev, Phys. Rev. B 98, 205118 (2018a).
  * Chepiga and Mila (2019a) N. Chepiga and F. Mila, Phys. Rev. Lett. 122, 017205 (2019a).
  * Chepiga and Mila (2019b) N. Chepiga and F. Mila, SciPost Phys. 6, 33 (2019b).
  * Giudici  _et al._ (2019) G. Giudici, A. Angelone, G. Magnifico, Z. Zeng, G. Giudice, T. Mendes-Santos, and M. Dalmonte, Phys. Rev. B 99, 094434 (2019).
  * Whitsitt  _et al._ (2018b) S. Whitsitt, R. Samajdar, and S. Sachdev, Phys. Rev. B 98, 205118 (2018b).
  * Chepiga and Mila (2021b) N. Chepiga and F. Mila, Phys. Rev. Res. 3, 023049 (2021b).
  * Maceira  _et al._ (2022) I. A. Maceira, N. Chepiga, and F. Mila, Phys. Rev. Res. 4, 043102 (2022).
  * Kohmoto  _et al._ (1981) M. Kohmoto, M. den Nijs, and L. P. Kadanoff, Phys. Rev. B 24, 5229 (1981).
  * O’Brien  _et al._ (2015) A. O’Brien, S. D. Bartlett, A. C. Doherty, and S. T. Flammia, Physical Review E 92, 042163 (2015).
  * Ashkin and Teller (1943) J. Ashkin and E. Teller, Physical Review 64, 178 (1943).
  * White (1992) S. R. White, Phys. Rev. Lett. 69, 2863 (1992).
  * Schollwöck (2005) U. Schollwöck, Rev. Mod. Phys. 77, 259 (2005).
  * Östlund and Rommer (1995) S. Östlund and S. Rommer, Phys. Rev. Lett. 75, 3537 (1995).
  * Schollwöck (2011) U. Schollwöck, Annals of Physics 326, 96 (2011).
  * Ornstein and Zernike (1914) L. Ornstein and F. Zernike, Koninklijke Nederlandse Akademie van Wetenschappen Proceedings Series B Physical Sciences 17, 793 (1914).
  * Singh  _et al._ (2022) K. Singh, S. Anand, A. Pocklington, J. T. Kemp, and H. Bernien, Phys. Rev. X 12, 011040 (2022).
  * Sheng  _et al._ (2022) C. Sheng, J. Hou, X. He, K. Wang, R. Guo, J. Zhuang, B. Mamat, P. Xu, M. Liu, J. Wang, and M. Zhan, Phys. Rev. Lett. 128, 083202 (2022).
  * Levi  _et al._ (2015) E. Levi, J. Minář, J. P. Garrahan, and I. Lesanovsky, New Journal of Physics 17, 123017 (2015).
  * Chepiga (2023) N. Chepiga, arXiv e-prints , arXiv:2308.12838 (2023), arXiv:2308.12838 .
  * Covey  _et al._ (2023) J. P. Covey, H. Weinfurter, and H. Bernien, npj Quantum Information 9, 90 (2023).


We use $\approx$ 7,400 lines of specification and proof to develop the  framework, which takes 8 PMs.
The  language and its rely-guarantee proof system consist of $\approx$ 2,400 LOSP, and  $\approx$ 15,000 LOSP. The two parts of specification and proof are completely reused in  and  respectively.
The adapter of  is $\approx$ 660 LOSP including new proof rules and their soundness as well as a concrete syntax. The adapter of  is $\approx$ 470 LOSP. The two  instances takes about 2 PMs.

We develop $\approx$ 17,600 LOSP for the Zephyr case study, 40 times more than the lines of the C code due to the in-kernel concurrency, where invariant proofs represent the largest part. The case study takes 12 PMs. The BPEL case study takes 2,200 LOSP and 2 PMs.

Specification and Proof Statistics

3|c|| Framework     3c| and  Adapters

Item 					      LOSP      PM     Item     LOSP     PM

Language and Semantics       300 	    6*8      extension     530     6*2

1-2 4-5
Computation 			      2,270 	         Adapter     130

1-2 4-5
Validity and Proof Rules     280 	         Adapter     470

Soundness                    4,200

Invariant/other lemmas       380

1-2 4-5
Total                        7,430 	        Total 				    1,130

3|c||Zephyr Memory Case     3c|BPEL Case

Item 					  	    LOSP      PM     Item     LOSP     PM

Specification 				    400 	    5*12     Syntax 				    120     5*2

1-2 4-5
Auxiliary Lemmas/Invariant     1,700 	    					      Semantics			    160

1-2 4-5
Proof of Allocation 		    10,600     					      Translation			    120

1-2 4-5
Proof of Free 				    4,950 	   					      Correctness Proof	    1,800

1-2 4-5
Total 						    17,650    					      Total 		    2,200

§.§ Further Related Work

Rely-guarantee Approach and Mechanization
The rely-guarantee approach has been mechanized in Isabelle/HOL (e.g. <cit.>) and Coq (e.g. <cit.>).
In <cit.>, an abstract algebra of atomic steps is developed, and rely/guarantee concurrency is an interpretation of the algebra.
To allow a meaningful comparison of rely-guarantee semantic models, two abstract models for rely-guarantee are developed and mechanized in <cit.>. The two works do not consider the concrete imperative languages for rely-guarantee. The works <cit.> mechanize the rely-guarantee approach for simple imperative languages. Later, a rely-guarantee proof system for  <cit.>, a generic and realistic imperative language by extending Simpl, is developed in Isabelle/HOL. These mechanizations focus on imperative languages for pure programs. Two of them <cit.> are mechanized in Isabelle/HOL and they have been integrated into .

Rely-guarantee Reasoning about Event-based Systems
Refinement of reactive systems <cit.> and the subsequent Event-B approach <cit.> propose a refinement-based formal method for system-level modeling and analysis.
Different from Event-B where the execution of events are atomic, we consider the interleaved semantics of events and relax the atomicity of them in .
In <cit.>, an Event-B model is created to mimic rely-guarantee style reasoning for concurrent programs, but not to provide a rely-guarantee framework for Event-B.
The rely-guarantee reasoning for event-based applications has been studied in <cit.>.
The definition of events is similar to . They extend a simple, sequential, imperative language by primitives for announcing and consuming events, announce(e) and consume(e(x)) where e is an event. Therefore, events are triggered by imperative programs in another event. This is very different from the reactive semantics in , which supports complex reaction structures to simulate real reactive systems. Moreover, the language to specify events in these works is a simple imperative language, whilst  has an open interface for the integration and reusability of different languages and frameworks.

Formal Verification of Memory Management
Memory models <cit.> provide the necessary abstraction to separate the behaviour of a program from the behaviour of the memory it reads and writes. There are several formalizations of memory models in the literature <cit.>, where some of them only create an abstract specification of the services for memory allocation and release <cit.>.
Formal verification of OS memory management has been studied in CertiKOS<cit.>, seL4 <cit.>, Verisoft <cit.>, and in the hypervisors from <cit.>, where only the works in <cit.> consider concurrency. Comparing to buddy memory allocation, the data structures and algorithms verified in <cit.> are relatively simpler, without block split/coalescence and multiple levels of free lists and bitmaps. <cit.> only considers virtual mapping but not allocation or deallocation of memory areas.
Algorithms and implementations of dynamic memory allocation have been formally specified and verified in an extensive number of works <cit.>. However, the buddy memory allocation is only studied in <cit.>, which does not consider concrete data structures (e.g. bitmaps) and concurrency. The Zephyr case study in this article presents the first formal specification and mechanized proof for a concurrent buddy memory allocation of a realistic operating system.

Formal Verification of BPEL
In recent years, how to increase the dependability of complex Web services composition has become a key problem. Thus numerous approaches have been proposed to formally specify and verify service compositions <cit.>.
Many works attempt to formally verify BPEL programs by manually modeling BPEL using verification tools (e.g. <cit.>) and by model transformation (e.g.<cit.>), however without proof of correctness of the modeling and transformation.
The rely-guarantee approach has been applied to BPEL in <cit.>. The authors proposed the rely-guarantee proof rules for each BPEL activity.
Compare to these works, this article presents the first verified translation from BPEL to , and thus conduct the formal verification of BPEL by reusing the  proof systems.

§ CONCLUSION AND FUTURE WORK

In this article, we propose an event-based rely-guarantee framework for concurrent reactive systems. This framework is open to the specification of event behaviours. It provides a rely-guarantee interface to integrate systems for specification and reasoning at that level that eases formal methods reusability. We have mechanized the integration of the  and  languages and their proof systems into  in the Isabelle/HOL theorem prover. We show the simplicity of events to represent concurrent reactive systems and the usefullness of  for realistic systems in the verification of the concurrent buddy memory allocation of Zephyr RTOS. We also show the expressiveness of reaction structures in  to model complex business processes in the BPEL case study.

Currently we are working on using  on the formal verification of noninterference properties on concurrent reactive systems. As future work, we plan to extend  to support step-wise refinement. More domain-specific reasoning frameworks, such as interrupts of multicore platforms and messaging systems for autonomous vehicles, are under development using  and its instances.

#1     #1#1#1     #1     #1     #1     #1#1          #1#1

[Abrial and HallerstedeAbrial and
authorpersonJean-Raymond Abrial and
personStefan Hallerstede. year2007.
Refinement, Decomposition, and Instantiation of
Discrete Models: Application to Event-B.
journalFundamenta Informaticae
volume77, number1-2 (year2007),

[Aceto, Ingólfsdóttir, Larsen, and
SrbaAceto et al2007]
authorpersonLuca Aceto, personAnna
Ingólfsdóttir, personKim Larsen, and
personJǐrí Srba. year2007.
booktitleReactive Systems - Modeling, Specification
and Verification.
publisherCambridge University Press.

authorpersonJames S. Albus.
The NIST Real-time Control System (RCS): An
Approach to Intelligent Systems Research.
journalJournal of Experimental & Theoretical
Artificial Intelligence volume9, number2-3
(year1997), pages157–174.

[Alkassar, Schirmer, and StarostinAlkassar
et al2008]
authorpersonEyad Alkassar, personNorbert
Schirmer, and personArtem Starostin.
Formal Pervasive Verification of a Paging
Mechanism. In booktitleProceedings of International
Conference on Tools and Algorithms for the Construction and Analysis of
Systems (TACAS). publisherSpringer Berlin Heidelberg,
addressBerlin, Heidelberg, pages109–123.

authorpersonJune Andronick.
Reasoning About Concurrency in High-Assurance,
High-Performance Software Systems. In booktitleProceedings
of International Conference on Automated Deduction (CADE),
editorpersonLeonardo de Moura (Ed.).
publisherSpringer International Publishing,
addressCham, pages1–7.

[Andronick, Lewis, and MorganAndronick
et al2015]
authorpersonJune Andronick, personCorey
Lewis, and personCarroll Morgan.
Controlled Owicki-Gries Concurrency: Reasoning
about the Preemptible eChronos Embedded Operating System. In
booktitleProceedings Workshop on Models for Formal Analysis
of Real Systems (MARS). pages10–24.

[Babin, Ait-Ameur, and PantelBabin
et al2017]
authorpersonG. Babin, personY.
Ait-Ameur, and personM. Pantel.
Web Service Compensation at Runtime: Formal
Modeling and Verification Using the Event-B Refinement and Proof Based Formal
journalIEEE Transactions on Services Computing
volume10, number1 (dateJanuary
year2017), pages107–120.

[Back and SereBack and Sere1991]
authorpersonRalph-Johan Back and
personKaisa Sere. year1991.
Stepwise Refinement of Action Systems.
journalStructured Programming
volume12 (year1991), pages17–30.

[Back and SereBack and Sere1996]
authorpersonRalf JR Back and personKaisa
Sere. year1996.
Superposition Refinement of Reactive Systems.
journalFormal Aspects of Computing
volume8, number3 (year1996),

authorpersonClemens Ballarin.
booktitleTutorial to Locales and Locale
Isabelle/HOL 2018 document.

[Blanchard, Kosmatov, Lemerre, and
LoulergueBlanchard et al2015]
authorpersonAllan Blanchard, personNikolai
Kosmatov, personMatthieu Lemerre, and
personFrédéeric Loulergue.
A Case Study on Formal Verification of the
Anaxagoros Hypervisor Paging System with Frama-C. In
booktitleProceedings of International Workshop on Formal
Methods for Industrial Critical Systems. publisherSpringer
International Publishing, pages15–30.

[Bolignano, Jensen, and SilesBolignano
et al2016]
authorpersonPauline Bolignano, personThomas
Jensen, and personVincent Siles.
Modeling and Abstraction of Memory Management in a
Hypervisor. In booktitleProceedings of International
Conference on Fundamental Approaches to Software Engineering (FASE).
publisherSpringer Berlin Heidelberg, pages214–230.

[Chen, Wu, Shao, Lockerman, and GuChen
et al2016]
authorpersonHao Chen, personXiongnan Wu,
personZhong Shao, personJoshua Lockerman, and
personRonghui Gu. year2016.
Toward Compositional Verification of Interruptible
OS Kernels and Device Drivers. In booktitle37th ACM
SIGPLAN Conference on Programming Language Design and Implementation
(PLDI). publisherACM, pages431–447.

[Dam, Guanciale, Khakpour, Nemati, and
SchwarzDam et al2013]
authorpersonMads Dam, personRoberto
Guanciale, personNarges Khakpour, personHamed
Nemati, and personOliver Schwarz.
Formal Verification of Information Flow Security
for a Simple Arm-based Separation Kernel. In
booktitleProceedings of the ACM SIGSAC Conference on
Computer & Communications Security (CCS). publisherACM,
addressNew York, NY, USA, pages223–234.

[Dingel, Garlan, Jha, and NotkinDingel
et al1998]
authorpersonJ. Dingel, personD. Garlan,
personS. Jha, and personD. Notkin.
Towards a Formal Treatment of Implicit Invocation
Using Rely/Guarantee Reasoning.
journalFormal Aspects of Computing
volume10, number3 (date01 Mar
year1998), pages193–213.

[Fang and SighireanuFang and
authorpersonBin Fang and personMihaela
Sighireanu. year2017a.
Hierarchical Shape Abstraction for Analysis of
Free List Memory Allocators. In booktitleProceedings of
International Symposium on Logic-Based Program Synthesis and
Transformation. publisherSpringer International Publishing,

[Fang and SighireanuFang and
authorpersonBin Fang and personMihaela
Sighireanu. year2017b.
A Refinement Hierarchy for Free List Memory
Allocators. In booktitleProceedings of ACM SIGPLAN
International Symposium on Memory Management. publisherACM,

[Fang, Sighireanu, Pu, Su, Abrial, Yang, and
QiaoFang et al2018]
authorpersonBin Fang, personMihaela
Sighireanu, personGeguang Pu, personWen Su,
personJean-Raymond Abrial, personMengfei Yang, and
personLei Qiao. year2018.
Formal Modelling of List based Dynamic Memory
journalScience China Information Sciences
volume61, number12 (date13 Nov
year2018), pages103 – 122.

[Fenkam, Gall, and JazayeriFenkam
et al2003a]
authorpersonPascal Fenkam, personHarald
Gall, and personMehdi Jazayeri.
Composing Specifications of Event Based
Applications. In booktitleInternational Conference on
Fundamental Approaches to Software Engineering (FASE).
publisherSpringer Berlin Heidelberg, addressBerlin,
Heidelberg, pages67–86.

[Fenkam, Gall, and JazayeriFenkam
et al2003b]
authorpersonPascal Fenkam, personHarald
Gall, and personMehdi Jazayeri.
Constructing Deadlock Free Event-Based
Applications: A Rely/Guarantee Approach. In
booktitleInternational Symposium of Formal Methods Europe
(FME). publisherSpringer Berlin Heidelberg,
addressBerlin, Heidelberg, pages636–657.

authorpersonThe Linux Foundation.
titleThe Zephyr Project.
Accessed: June 2019.

[Fu, Bultan, and SuFu et al2004]
authorpersonXiang Fu, personTevfik Bultan,
and personJianwen Su. year2004.
Analysis of Interacting BPEL Web Services. In
booktitleProceedings of the 13th International Conference on
World Wide Web (seriesWWW'04). publisherACM,
addressNew York, NY, USA, pages621–630.

[G. M. M. Campos and N. S. Rosa and L. F.
PiresG. M. M. Campos and N. S. Rosa and L. F. Pires2014]
authorpersonG. M. M. Campos and N. S. Rosa and L.
F. Pires. year2014.
A Survey of Formalization Approaches to Service
Composition. In booktitleProceedings of 2014 IEEE
International Conference on Services Computing. pages179–186.

[Gallardo, Merino, and SanánGallardo
et al2009]
authorpersonMaría del Mar Gallardo,
personPedro Merino, and personDavid Sanán.
Model Checking Dynamic Memory Allocation in
Operating Systems.
journalJournal of Automated Reasoning
volume42, number2 (dateApril
year2009), pages229–264.

[Gamma, Helm, Johnson, and VlissidesGamma
et al1995]
authorpersonErich Gamma, personRichard
Helm, personRalph Johnson, and personJohn
Vlissides. year1995.
booktitleDesign Patterns: Elements of Reusable
Object-oriented Software.
publisherAddison-Wesley Longman Publishing Co., Inc.,
addressBoston, MA, USA.

[Garlan, Jha, Notkin, and DingelGarlan
et al1998]
authorpersonD. Garlan, personS. Jha,
personD. Notkin, and personJ. Dingel.
Reasoning About Implicit Invocation. In
booktitleProceedings of the 6th ACM SIGSOFT International
Symposium on Foundations of Software Engineering (FSE).
publisherACM, addressNew York, NY, USA,

[Gu, Shao, Chen, Wu, Kim, Sjöberg, and
CostanzoGu et al2016]
authorpersonRonghui Gu, personZhong Shao,
personHao Chen, personXiongnan Wu,
personJieung Kim, personVilhelm Sjöberg, and
personDavid Costanzo. year2016.
CertiKOS: An Extensible Architecture for Building
Certified Concurrent OS Kernels. In booktitleProceedings
of 12th USENIX Conference on Operating Systems Design and Implementation
(seriesOSDI'16). publisherUSENIX Association,
addressBerkeley, CA, USA, pages653–669.

[Harel and PnueliHarel and Pnueli1985]
authorpersonD. Harel and personA.
Pnueli. year1985.
On the Development of Reactive Systems. In
booktitleLogics and Models of Concurrent Systems,
editorpersonKrzysztof R. Apt (Ed.).
publisherSpringer Berlin Heidelberg, addressBerlin,
Heidelberg, pages477–498.

authorpersonIan J. Hayes.
Generalised Rely-guarantee Concurrency: An
Algebraic Foundation.
journalFormal Aspects of Computing
volume28, number6 (date01 Nov
year2016), pages1057–1078.

[Hayes, Colvin, Meinicke, Winter, and
VelykisHayes et al2016]
authorpersonIan J. Hayes, personRobert J.
Colvin, personLarissa A. Meinicke, personKirsten
Winter, and personAndrius Velykis.
An Algebra of Synchronous Atomic Steps. In
booktitleProceedings of International Symposium on Formal
Methods (FM). publisherSpringer International Publishing,

[Hoang and AbrialHoang and Abrial2010]
authorpersonThai Son Hoang and
personJean-Raymond Abrial. year2010.
Event-B Decomposition for Parallel Programs. In
booktitleSecond International Conference of Abstract State
Machines, Alloy, B and Z (ABZ). publisherSpringer Berlin
Heidelberg, pages319–333.

authorpersonC. B. Jones.
Tentative Steps Toward a Development Method for
Interfering Programs.
journalACM Transactions on Programming Languages and
System volume5, number4 (dateOctober
year1983), pages596–619.

[Klein, Andronick, Elphinstone, Murray, Sewell,
Kolanski, and HeiserKlein et al2014]
authorpersonGerwin Klein, personJune
Andronick, personKevin Elphinstone, personToby
Murray, personThomas Sewell, personRafal Kolanski,
and personGernot Heiser. year2014.
Comprehensive Formal Verification of An OS
journalACM Transactions on Computer Systems
volume32, number1 (year2014),

[Klein, Elphinstone, Heiser, Andronick, Cock,
Derrin, Elkaduwe, Engelhardt, Kolanski, Norrish, et alKlein
et al2009]
authorpersonGerwin Klein, personKevin
Elphinstone, personGernot Heiser, personJune
Andronick, personDavid Cock, personPhilip Derrin,
personDhammika Elkaduwe, personKai Engelhardt,
personRafal Kolanski, personMichael Norrish,
et al year2009.
seL4: Formal Verification of an OS Kernel. In
booktitleProceedings of ACM SIGOPS 22nd Symposium on
Operating Systems Principles (seriesSOSP'09).
publisherACM Press, addressBig Sky, Montana, USA,

[Klein and TuchKlein and Tuch2004]
authorpersonGerwin Klein and personHarvey
Tuch. year2004.
Towards Verified Virtual Memory in L4. In
booktitleProceedings of TPHOLs Emerging Trends.
addressPark City, Utah, USA, pages16 pages.

authorpersonXavier Leroy.
Formal Verification of a Realistic Compiler.
journalCommunications of ACM volume52,
number7 (year2009), pages107–115.

[Leroy and BlazyLeroy and Blazy2008]
authorpersonXavier Leroy and
personSandrine Blazy. year2008.
Formal Verification of a C-like Memory Model and
Its Uses for Verifying Program Transformations.
journalJournal of Automated Reasoning
volume41, number1 (date01 July
year2008), pages1–31.

[Liang, Feng, and FuLiang
et al2012]
authorpersonHongjin Liang, personXinyu
Feng, and personMing Fu. year2012.
A Rely-guarantee-based Simulation for Verifying
Concurrent Program Transformations. In booktitle39th
Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages
(POPL). publisherACM Press, pages455–468.

[Mansky, Garbuzov, and ZdancewicMansky
et al2015]
authorpersonWilliam Mansky, personDmitri
Garbuzov, and personSteve Zdancewic.
An Axiomatic Specification for Sequential Memory
Models. In booktitleProceedings of International
Conference on Computer Aided Verification (CAV).
publisherSpringer International Publishing,

[Mantel, Sands, and SudbrockMantel
et al2011]
authorpersonHeiko Mantel, personDavid
Sands, and personHenning Sudbrock.
Assumptions and Guarantees for Compositional
Noninterference. In booktitle24th Computer Security
Foundations Symposium (CSF). publisherIEEE Press,

[Marti, Affeldt, and YonezawaMarti
et al2006]
authorpersonNicolas Marti, personReynald
Affeldt, and personAkinori Yonezawa.
Formal Verification of the Heap Manager of an
Operating System Using Separation Logic. In
booktitleProceedings of International Conference on Formal
Engineering Methods (ICFEM). publisherSpringer Berlin
Heidelberg, addressBerlin, Heidelberg,

[Moreira, Pereira, and de SousaMoreira
et al2013]
authorpersonNelma Moreira, personDavid
Pereira, and personSimao Melo de Sousa.
booktitleOn the Mechanisation of Rely-Guarantee in
typeTechnical Report.
institutionUniversidade do Porto.

[Murray, Matichuk, Brassil, Gammie, and
KleinMurray et al2012]
authorpersonToby Murray, personDaniel
Matichuk, personMatthew Brassil, personPeter Gammie,
and personGerwin Klein. year2012.
Noninterference for Operating System Kernels. In
booktitle2nd International Conference on Certified Programs
and Proofs (CPP). publisherSpringer, pages126–142.

[Murray, Sison, Pierzchalski, and
RizkallahMurray et al2016]
authorpersonToby Murray, personRobert
Sison, personEdward Pierzchalski, and
personChristine Rizkallah. year2016.
Compositional Verification and Refinement of
Concurrent Value-Dependent Noninterference. In
booktitle29th IEEE Computer Security Foundations Symposium
(CSF). publisherIEEE Press.

[National Security AgencyNational Security
National Security Agency year2012.
booktitleCommon Criteria for Information Technology
Security Evaluation (edition3.1 r4 ed.).
National Security Agency.

authorpersonLeonor Prensa Nieto.
The Rely-Guarantee Method in Isabelle/HOL. In
booktitle12th European Symposium on Programming (ESOP).
publisherSpringer Berlin Heidelberg, pages348–362.

authorpersonOASIS. year2007.
titleWeb Services Business Process Execution Language
Accessed: June 2019.

authorpersonChris Peltz.
Web Services Orchestration and Choreography.
journalComputer volume36,
number10 (dateOct. year2003),

authorpersonNSF Project.
titleThe Science of Deep Specification.

[Sanán, Zhao, Hou, Zhang, Tiu, and
LiuSanán et al2017]
authorpersonDavid Sanán, personYongwang
Zhao, personZhe Hou, personFuyuan Zhang,
personAlwen Tiu, and personYang Liu.
CSimpl: A Rely-Guarantee-Based Framework for
Verifying Concurrent Programs. In booktitle23rd
International Conference on Tools and Algorithms for the Construction and
Analysis of Systems (TACAS). publisherSpringer Berlin
Heidelberg, pages481–498.

[Saraswat, Jagadeesan, Michael, and von
PraunSaraswat et al2007]
authorpersonVijay A. Saraswat, personRadha
Jagadeesan, personMaged Michael, and
personChristoph von Praun. year2007.
A Theory of Memory Models. In
booktitleProceedings of the 12th ACM SIGPLAN Symposium on
Principles and Practice of Parallel Programming (PPoPP).
publisherACM, pages161–172.

authorpersonN. Schirmer.
titleVerification of Sequential Imperative Programs
in Isabelle/HOL.
thesistypePh.D. Dissertation.
schoolTechnischen Universitat Munchen.

[Sheng, Qiao, Vasilakos, Szabo, Bourne, and
XuSheng et al2014]
authorpersonQuan Z. Sheng, personXiaoqiang
Qiao, personAthanasios V. Vasilakos, personClaudia
Szabo, personScott Bourne, and personXiaofei Xu.
Web Services Composition: A Decade's Overview.
journalInformation Sciences
volume280 (year2014), pages218 – 238.

[Stachtiari and KatsarosStachtiari and
authorpersonEmmanouela Stachtiari and
personPanagiotis Katsaros. year2018.
Compositional Execution Semantics for Business
Process Verification.
journalJournal of Systems and Software
volume137 (year2018), pages217 – 238.

[Su, Abrial, Pu, and FangSu
et al2016]
authorpersonWen Su, personJean Raymond
Abrial, personGeguang Pu, and personBin Fang.
Formal Development of a Real-Time Operating System
Memory Manager. In booktitleProceedings of International
Conference on Engineering of Complex Computer Systems (ICECCS).

[Tews, Völp, and WeberTews
et al2009]
authorpersonHendrik Tews, personMarcus
Völp, and personTjark Weber.
Formal Memory Models for the Verification of
Low-Level Operating-System Code.
journalJournal of Automated Reasoning
volume42, number2 (date01 April
year2009), pages189–227.

[van Stadenvan Staden2015]
authorpersonStephan van Staden.
On Rely-Guarantee Reasoning. In
booktitleInternational Conference on Mathematics of Program
Construction. publisherSpringer International Publishing,

[Vaynberg and ShaoVaynberg and Shao2012]
authorpersonAlexander Vaynberg and
personZhong Shao. year2012.
Compositional Verification of a Baby Virtual
Memory Manager. In booktitleProceedings of 2nd
International Conference on Certified Programs and Proofs (CPP).
publisherSpringer-Verlag, addressBerlin, Heidelberg,

[Ševčík, Vafeiadis,
Zappa Nardelli, Jagannathan, and SewellŠevčík
et al2013]
authorpersonJaroslav Ševčík,
personViktor Vafeiadis, personFrancesco
Zappa Nardelli, personSuresh Jagannathan, and
personPeter Sewell. year2013.
CompCertTSO: A Verified Compiler for
Relaxed-Memory Concurrency.
journalJ. ACM volume60,
number3, Article articleno22 (dateJune
year2013), numpages50 pages.

[Xu, Fu, Feng, Zhang, Zhang, and LiXu
et al2016]
authorpersonFengwei Xu, personMing Fu,
personXinyu Feng, personXiaoran Zhang,
personHui Zhang, and personZhaohui Li.
A Practical Verification Framework for Preemptive
OS Kernels. In booktitle28th International Conference on
Computer Aided Verification (CAV). publisherSpringer,

[Xu, de Roever, and HeXu
et al1997]
authorpersonQiwen Xu, personWillem-Paul de
Roever, and personJifeng He. year1997.
The Rely-guarantee Method for Verifying Shared
Variable Concurrent Programs.
journalFormal Aspects of Computing
volume9, number2 (year1997),

[Yu, Hamid, and ShaoYu et al2003]
authorpersonDachuan Yu, personNadeem A.
Hamid, and personZhong Shao. year2003.
Building Certified Libraries for PCC: Dynamic
Storage Allocation. In booktitleProceedings of European
Symposium on Programming Languages and Systems (ESOP).
publisherSpringer Berlin Heidelberg, pages363–379.

[Zhao and SanánZhao and
authorpersonYongwang Zhao and personDavid
Sanán. year2019.
Rely-guarantee Reasoning about Concurrent Memory
Management in Zephyr RTOS. In booktitle31st International
Conference on Computer-Aided Verification (CAV).
publisherSpringer, pages515–533.

[Zhao, Sanán, Zhang, and LiuZhao
et al2016]
authorpersonYongwang Zhao, personDavid
Sanán, personFuyuan Zhang, and personYang
Liu. year2016.
Reasoning About Information Flow Security of
Separation Kernels with Channel-Based Communication. In
booktitle22nd International Conference on Tools and
Algorithms for the Construction and Analysis of Systems (TACAS).
publisherSpringer Berlin Heidelberg, pages791–810.

[Zhao, Sanán, Zhang, and LiuZhao
et al2019]
authorpersonYongwang Zhao, personDavid
Sanán, personFuyuan Zhang, and personYang
Liu. year2019.
A Parametric Rely-guarantee Reasoning Framework
for Concurrent Reactive Systems. In booktitleProceedings
of 23rd Internaltional Symposium on Formal Methods (FM).
publisherSpringer Berlin Heidelberg, pages161–178.

[Zhu, Xu, Ma, Qin, and QiuZhu
et al2012]
authorpersonHuibiao Zhu, personQiwen Xu,
personChris Ma, personShengchao Qin, and
personZongyan Qiu. year2012.
The Rely/Guarantee Approach to Verifying
Concurrent BPEL Programs. In booktitleSoftware Engineering
and Formal Methods, editorpersonGeorge
Eleftherakis, personMike Hinchey, and personMike
Holcombe (Eds.). publisherSpringer Berlin Heidelberg,
addressBerlin, Heidelberg, pages172–187.

[Zhu, Huang, and ZhouZhu
et al2017]
authorpersonYi Zhu, personZhiqiu Huang,
and personHang Zhou. year2017.
Modeling and Verification of Web Services
Composition based on Model Transformation.
journalSoftware: Practice and Experience
volume47, number5 (year2017),

§ C CODE OF K_MEM_POOL_FREE

static void free_block(struct k_mem_pool *p, int level, size_t *lsizes, int bn)

int i, key, lsz = lsizes[level];
void *block = block_ptr(p, lsz, bn);

key = irq_lock();

set_free_bit(p, level, bn);

if (level        partner_bits(p, level, bn) == 0xf)
for (i = 0; i < 4; i++)
int b = (bn      3) + i;

clear_free_bit(p, level, b);
if (b != bn        block_fits(p, block_ptr(p, lsz, b), lsz))
sys_dlist_remove(block_ptr(p, lsz, b));

free_block(p, level-1, lsizes, bn / 4); /* tail recursion! */

if (block_fits(p, block, lsz))
sys_dlist_append(   p->levels[level].free_list, block);

void k_mem_pool_free(struct k_mem_block *block)

int i, key, need_sched = 0;
struct k_mem_pool *p = get_pool(block->id.pool);
size_t lsizes[p->n_levels];

/* As in k_mem_pool_alloc(), we build a table of level sizes
* to avoid having to store it in precious RAM bytes.
* Overhead here is somewhat higher because free_block()
* doesn't inherently need to traverse all the larger
* sublevels.
lsizes[0] = _ALIGN4(p->max_sz);
for (i = 1; i <= block->id.level; i++)
lsizes[i] = _ALIGN4(lsizes[i-1] / 4);

free_block(get_pool(block->id.pool), block->id.level, lsizes, block->id.block);

/* Wake up anyone blocked on this pool and let them repeat
* their allocation attempts
key = irq_lock();

while (!sys_dlist_is_empty(   p->wait_q))
struct k_thread *th = (void *)sys_dlist_peek_head(   p->wait_q);

need_sched = 1;

if (need_sched        !_is_in_isr())

§ SPECIFICATION AND PROOF SKETCH OF K_MEM_POOL_FREE

The formal specification of k_mem_pool_free (in black color) and its rely-guarantee proof sketch (in blue color) are shown as follows.

Mempoolfreepre t   inv  allocatingnode t  None  freeingnode t  None

mem_pool_freeBlock b($\mathcal{T}$ t)

WHEN  pool b  mempools    level b  length levels mempoolinfo pool b   block b  length bits levels mempoolinfo pool blevel b   data b  blockptr mempoolinfo pool b          ALIGN4 maxsz mempoolinfo pool b div 4  level b block bTHEN

Mempoolfreepre t   g
(* g is the guard condition of the event *)

here we set the bit to FREEING so that other thread cannot mempoolfree the same block        it also requires that it can only free ALLOCATED block

t  AWAIT bits levels mempoolinfo pool b  level b  block b

ALLOCATED THEN

mempoolinfo  setbitfreeing mempoolinfo pool b level b block b

freeingnode  freeingnode t  Some b

mpfreeprecond2 t b   inv  allocatingnode t  None   g  freeingnode t  Some b

t  needresched  needreschedt  False

mpfreeprecond3 t b  mpfreeprecond2 t b  needresched t  False

t  lsizes  lsizest  ALIGN4 maxsz mempoolinfo pool b

mpfreeprecond4 t b      mpfreeprecond3 t b  lsizes t  ALIGN4 maxsz mempoolinfo pool b

FOR t  i  it  1  i t  level b  t  i  it  i t  1 DO    t  lsizes  lsizest  lsizes t  ALIGN4 lsizes t  i t  1 div 4

mpfreeprecond5 t b  mpfreeprecond3 t b       iilength lsizes t lsizes t  ii  ALIGN4 maxsz mempoolinfo pool b                                        div 4  ii  length lsizes t  level b

start freeblockpool level lsizes block

t  freeblockr  freeblockr t  True

mpfreeprecond6 t b  mpfreeprecond5 t b  freeblockr t  True

t  bn  bn t  block b

mpfreeprecond7 t b  mpfreeprecond6 t b  bn t  block b

t  lvl  lvl t  level b

mpfreeloopinv t b
WHILE freeblockr t DO
mpfreecnd1 t b   mpfreeloopinv t b      0
t   lsz  lsz t  lsizes t  lvl t
mpfreecnd2 t b   mpfreecnd1  t b    lsz t  lsizes t  lvl t
t   blk  blk t  blockptr mempoolinfo pool b lsz t bn t
mpfreecnd3 t b   mpfreecnd2  t b                        blk t  blockptr mempoolinfo pool b lsz t bn t
t   ATOM    {V1} V1  mpfreecnd3  t b   cur  Some t
mempoolinfo  setbitfree mempoolinfo pool b lvl t bn t    {V2} V2 = V1mempoolinfo                   setbitfree mempoolinfo V1 pool b lvl V1 t bn V1 t
freeingnode  freeingnode t  None    {V3} V3 = V2freeingnode  freeingnode V2t  None
IF lvl t  0  partnerbits mempoolinfo pool b lvl t bn t THEN

(V3  NULL  lvl t  partnerbits mempoolinfo pool b lvl t bn t)

mergeblockloopinv V3  t b       V let minf0  mempoolinfo V3pool b
lvl0  levels minf0  lvl V3 t          minf1  mempoolinfo Vpool b
lvl1  levels minf1  lvl V3 t in         bits lvl1  listupdatesn bits lvl0 bn V3 t div 4  4 i V t NOEXIST         freelist lvl1  removes map ii blockptr minf0 lsz V3 t                          bn V3 t div 4  4  ii 0i V t freelist lvl0

waitq minf0  waitq minf1  t t  t  lvarsnochange t V V3

p p  pool b  mempoolinfo V p  mempoolinfo V3 p         j j  lvl V3 t  levels minf0j  levels minf1j

VV3gvarsconfstable   i V t  4       = 4 - i V t ......

FOR i  it  0 i t  4 i  it  i t  1 DO

mergeblockloopinv V3  t b      0

{V4} V4  mergeblockloopinv V3  t b      0

bb  bb t  bn t div 4  4  i t

{V5} V5  V4bb  bb V tbn V4 t div 4  4  i V4 t

mempoolinfo  setbitnoexist mempoolinfo pool b lvl t bb t

{V6} V6  V5 mempoolinfo                       setbitnoexist (mempoolinfo V5) (pool b) (lvl V5 t) (bb V5 t)

blockpt  blockpt t  blockptr mempoolinfo pool b lsz t bb t

{V7} V7  V6blockpt  blockpt V6                    tblockptr mempoolinfo V6 pool b lsz V6 t bb V6 t

IF bn t  bb t  blockfits mempoolinfo pool b blockpt t lsz t THEN            mempoolinfo  mempoolinfo pool b                  removefreelist mempoolinfo pool b lvl t blockpt t          FI        ROF

mergeblockloopinv V3  t b     = 0

lvl  lvl t  lvl t  1        bn  bn t  bn t div 4        mempoolinfo  setbitfreeing mempoolinfo pool b lvl t bn t        freeingnode  freeingnode t  Some pool  pool b level  lvl t                       block  bn t
data  blockptr mempoolinfo pool b                          ALIGN4 maxsz mempoolinfo pool b div 4  lvl t
bn t       ELSE

{V3}   NULL  lvl t  partnerbits mempoolinfo pool b lvl t bn t

IF blockfits mempoolinfo pool b blk t lsz t THEN          mempoolinfo  mempoolinfo pool b              appendfreelist mempoolinfo pool b lvl t blk t         FI        freeblockr  freeblockr t  False      FI    END  (* END of ATOM *)   OD  (* END of WHILE  free_block_r  DO  *)

mpfreeprecond9 t b  Mempoolfreepre t   g

end of  freeblockpool level lsizes block

t  ATOMIC

{Va} Va  mpfreeprecond9  t b  cur  Some t

stm9loopinv Va t b      V inv V  cur V  cur Va  tick V  tick Va  VVagvarsconfstable        freeingnode V t  freeingnode Va t  allocatingnode V t  allocatingnode Va t       p levels mempoolinfo V p  levels mempoolinfo Va p       p p  pool b  mempoolinfo V p  mempoolinfo Va p       t t  t  lvarsnochange t V Va         length waitq mempoolinfo pool b

WHILE waitq mempoolinfo pool b   DO

stm9loopinv Va t b      0

th  th t  hd waitq mempoolinfo pool b

mempoolinfo  mempoolinfo pool b  mempoolinfo pool b

waitq  tl waitq mempoolinfo pool b

thdstate  thdstate th t  READY

needresched  needreschedt  True

stm9loopinv Va t b     = 0

IF needresched t THEN      reschedule   (* _reschedule_threads(key) *)    FI  END  (* END of ATOM *)END

Mempoolfreepost t   inv  allocatingnode t  None  freeingnode t  None