# Electric double layer of colloidal particles in salt-free concentrated
suspensions including non-uniform size effects and orientational ordering of
water dipoles

Jun-Sik Sin<EMAIL_ADDRESS>College of Physics, Kim Il Sung
University, Taesong District, Pyongyang, DPR Korea  Kwang-Il Kim  College of
Physics, Kim Il Sung University, Taesong District, Pyongyang, DPR Korea  Kuk-
Chol Ri  College of Physics, Kim Il Sung University, Taesong District,
Pyongyang, DPR Korea  Dok-Yong Ju  College of Physics, Kim Il Sung University,
Taesong District, Pyongyang, DPR Korea  Nam-Hyok Kim  College of Physics, Kim
Il Sung University, Taesong District, Pyongyang, DPR Korea  Chung-Sik Sin
College of Physics, Kim Il Sung University, Taesong District, Pyongyang, DPR
Korea

###### Abstract

The response of a suspension under a variety of static or alternating external
fields strongly depends on the equilibrium electric double layer that
surrounds the colloidal particles in the suspension. The theoretical models
for salt-free suspensions can be improved by incorporating non-uniform size
effects and orientational ordering of water dipoles neglected in previous
mean-field approaches, which are based on the Poisson-Boltzmann approach. Our
model including non-uniform size effects and orientational ordering of water
dipoles seems to have quite a promising effect because the model can predict
the phenomena like a heavy decrease in relative permittivity of the suspension
and counterion stratification near highly charged colloidal particle. In this
work we numerically obtain the electric potential, the counterions
concentration and the relative permittivity around a charged particle in a
concentrated salt-free suspension corrected by non-uniform size effects and
orientational ordering of water dipoles. The results show the worth of such
corrections for medium to high particle charges at every particle volume
fraction. We conclude that non-uniform size effects and orientational ordering
of water dipoles are necessary for the development of new theoretical models
to study non-equilibrium properties in concentrated colloidal suspensions.

Salt-free suspension; Electric double layer; Orientational ordering of water
dipoles; Non-uniform size effects; Poisson-Boltzmann equation.

##  I Introduction

A suspension of charged particles under static or alternative electric fields
is one of the most interesting topics of electrokinetics
Lyklema_monograph_1995 ; Hunter_monograph_1995 ; Masiliyah_monograph_2006 ;
OBrien_fluidmech_1990 ; Dukhin_langmuir_1999 . In particular, study of salt-
free suspensions has been continuously grown in recent years from experimental
and theoretical point of view because in salt-free suspensions, colloidal
crystals can be formed at relatively low particle volume fraction than in a
suspension with added external salt OBrien_fluidmech_1990 ;
Dukhin_langmuir_1999 ; Sood_monograph_1991 ; Medebach_chemphys_2003 . A salt-
free suspension is composed of charged colloidal particles and the added
counterions released by the particles in the liquid medium, where the
electroneutrality is preserved.

The unique behaviours of salt-free suspensions can be understood by using
physical quantities like electrophoretic mobility, electrical conductivity and
dielectric response, which are electrohydrodynamic properties of suspension in
electrolyte solution Carrique_physchemb_2006 ; Carrique_langmuir_2008 ;
Arroyo_langmuir_2008 ; Ruiz_physchemc_2007 ; Ruiz_physchemb_2008 . The
physical quantities can be obtained by solving electrohydrodynamic equations
with initial and boundary conditions. All of static or dynamic quantities are
closely related to the properties of the equilibrium electric double layer
surrounding the particles. If the salt-free suspension is dilute, for typical
cases, particle-particle electrohydrodynamic interactions can be negligible.
However, in the high regime of particle volume fraction, the response to
external fields is affected by the interactions which give rise to the
mathematical difficulty related with many-body interactions as well as the
numerical problems for solving the equations without any approximation.

To overcome this problem, the authors of Carrique_physchemb_2009 ;
Ruiz_physchemb_2009 ; Ruiz_colloidinterf_2010 ; Carrique_physchemb_2010
introduced a cell model approach, and the approach successfully was applied to
dealing with electrokinetic and rheological properties in concentrated
suspension. It was confirmed in Denton_physmatter  that up to moderately
strong electrostatic couplings, the cell model accurately predicts osmotic
pressures of deionised suspensions in agreement with Monte Carlo simulations
and renormalized-effective interaction approaches. In spite of the help of the
cell model, because the theoretical models are based on Poisson-Boltzmann(PB)
approach, the models maintain the shortcomings of Poisson-Boltzmann approach.

In Lopez_colloidinterf_2007 ; Lopez_colloidinterf_2008 ;
Aranda_colloidinterf_2009 ; Rascon_colloidinterf_2009 ; Lopez_physchemb_2010 ,
the authors investigated dilute colloidal suspensions by classical PB
equation, which neglects ionic correlation, ionic size effects and solvent
polarization. They confirmed the fact that considering the distance of closest
approach to the charged particle is important for explaining the overcharging
mechanism near the charged particle without explicit consideration of ionic
correlation.

Roa and coworkers Roa_pccp_2011_1 ; Roa_pccp_2011_2 ; Roa_pccp_2011_3 ;
Roa_colloidinterf_2012  considered the finite sizes of ions by extending
Borukhov’s approach Borukhov_jpolym_2004  to concentrated salt-free suspension
with the help of the cell model. The consideration of finite ion sizes yielded
reasonable counterions concentration profiles and electric potential profiles
and allowed one to understand reasonably electrophoretic mobility, electric
conductivity and dielectric response.

To well understand properties of electric double layer, different
computational approaches such as Monte Carlo and numerical solutions of
integral equations were introduced, but they are unable of making feasible
predictions out of equilibrium and involve complex calculations
Ibarra_pccp_2009 ; Gonzalez_physchem_1989 .

In the case of electrolytes, electric double layer theory has a lengthy
history compared to salt-free suspension, dating back to Helmholtz
Helmholtz_annphys_1879 . The original PB approach proposed by Gouy and
Chapmann does not consider the finite volumes of ions, and neglects ionic
correlations in electrolyte Gouy_jphys_1910 ; Chapman_philomag_1913 . In fact,
for typical situations including low to medium particle charges and monovalent
ions in electrolyte solution, this approach seems to be quite reasonable for
representation of the equilibrium problem. The limitations of PB approach
yield unphysical ionic concentration profiles near highly charged interfaces
and also inability to predict the overcharging phenomena.

To eliminate such a shortcoming of the PB approach, various modifications of
PB approach were pioneered and successfully applied to the practical problems.
In order to account for ionic size effect, Stern Stern_zelechem_2007  modified
the PB approach considering the finite size effect of ions by combining the
Helmholtz model Helmholtz_annphys_1879  with the Gouy-Chapmann mode
lChapman_philomag_1913 . Bikerman Bikerman_philosmag_1942  empirically
extended Boltzmann distribution by correcting ion concentration for the volume
excluded by ions. In the last two decades, researchers considered finite
volumes of ions and water molecules within lattice statistical mechanics
approach Borukhov_prl_1997 ; Borukhov_electrochim_2000 ; Iglic_physfran_1996 ;
Bohnic_electrochimica_2001 ; Bohnic_bioelechem_2002 ; Bohnic_bioelechem_2005 .
However, most of them are based on the assumption that different species of
ions in electrolytes have equal size. Recent studies Tresset_pre_2008 ;
Chu_biophys_2007 ; Biesheuvel_colloidinterf_2007 ; Li_pre_2011 ; Li_pre_2012 ;
Boschitsch_jcomchem_2012 ; Kornyshev_physchemb_2007 ; Popovic_pre_2013
indicate that difference in sizes of ions enables one to understand phenomena
like the asymmetric differential electric capacitance and the stratification
of counterions.

It is well known that near a charged surface in an electrolyte the relative
permittivity of the electrolyte solution varies according to the distance from
the surface Onsager_amchem_1936 ; Kirkwood_chemphys_1939 . Although the Booth
model Booth_chemphys_1951 ; Booth_chemphys_1955  is widely used in many
practices, it has the drawback that the model does not take into account the
sizes of both ions and water molecules in electrolyte solution. In
Iglic_bioelechem_2010 ; Gongadze_bioelechem_2012 ; Gongadze_elechem_2013 , the
authors developed water polarization model including size effects of ions and
water molecules. The permittivity model of electrolytes well represents the
fact that the permittivity of an electrolyte solution may be strongly
decreased by orientational ordering of water dipoles and depletion of water
molecules.

Recently, we Sin_electrochimica_2015  have incorporated not only the non-
uniform size effects of ions and water molecules in electrolyte but also the
orientational ordering of water dipoles into the Poisson-Boltzmann approach.
It is evident that in the case of salt-free suspension as well as
electrolytes, such effects will influence equilibrium and non-equilibrium
properties of electric double layer.

Summarizing, in this study, we will focus on the influence of orientational
ordering of water dipoles and non-uniform size effects on the electrostatic
properties of electric double layer of a charged particle in a concentrated
salt-free suspension. In other words, we extends the Poisson-Boltzmann
approach developed for aqueous electrolytes by us Sin_electrochimica_2015  to
the case of salt-free suspension. As in Aranda_colloidinterf_2009 ;
Rascon_colloidinterf_2009 ; Roa_pccp_2011_1 , our model also incorporates an
excluded region in contact with the particle of a hydrated radius size, which
yields more realistic representation of solid-liquid interface and also
predicts results in good agreement with experimental electrokinetic data.
Solving numerically new equations, we will analyze the equilibrium surface
potential, relative permittivity of the suspension and counterions
concentration profiles inside a cell upon changing particle volume fraction,
particle surface charge density and size of the counterions. In order to show
the importance of the orientational ordering of water dipoles, the results
will be compared with ones of Roa_pccp_2011_1  that takes into account only
finite ion size.

##  II Theory

###  II.1 The cell model

Figure 1: (Color online) Cell model including the distance of closest approach
of the counterions to the particle surface.

Different electrokinetic and rheological phenomena in salt-free concentrated
suspensions have been studied by a cell model. In the cell model, each
spherical particle of radius $a$ is surrounded by a concentric shell of the
liquid medium, having an outer radius $b$ such that the particle/cell volume
ratio in the cell is equal to the particle volume fraction throughout the
entire suspension, that is,

$\displaystyle\phi=\left(\frac{a}{b}\right)^{3}.$ (1)

In the cell model, it is assumed that the macroscopic properties of a
suspension can be obtained from appropriate averages of local properties in a
unique cell. We consider a spherical charged particle of radius $a$ and
surface charge density $\sigma$ immersed in a salt-free medium with the added
counterions of valence $z_{c}$. The spherical coordinate system
$\left(r,\theta,\phi\right)$ is used and its origin is at the center of the
particle. When any external field does not exist, a spherically symmetrical
charge distribution surrounds the particle.

###  II.2  Non-uniform size effects and orientational ordering of water
dipoles

The total free energy of the cell can be written in terms of the local
electrostatic potential $\psi\left({\bf r}\right)$, the counterions
concentration $n_{r}\left({\bf r}\right)$ and the number density of water
molecules
$n_{w}\left(r\right)=\left<\rho\left(\omega,r\right)\right>_{\omega}$.

$\displaystyle F=\int{d{\bf r}}\left(-\frac{\varepsilon_{0}\varepsilon
E^{2}}{2}+e_{0}z_{c}\psi
n_{c}+\left<\rho\left(\omega\right)\gamma{p_{0}}E\cos\omega\right>_{\omega}-\mu_{c}n_{c}-\left<\mu_{w}\left(\omega\right)\rho\left(\omega\right)\right>_{\omega}-Ts\right),$
(2)

where $\left<f\left(\omega\right)\right>_{\omega}=\int
f\left(\omega\right)2\pi\sin\omega d\omega$ in which $\omega$ is the angle
between the vector p and the vector -E. Here p is the dipole moment of water
molecules and E is the electric field strength. The first term is the self
energy of the electrostatic field, where $\varepsilon$ equals $n^{2}$, where
$n=1.33$ is the refractive index of water. The next term corresponds to the
electrostatic energy of the counterions in the electrostatic mean field, where
$e_{0}$ is the elementary charge. The third one represents the electrostatic
energy of water dipolesGongadze_bioelechem_2012 , where
$\gamma=\left(2+n^{2}\right)/2$, $p_{0}=\left|{\bf p}\right|$ and
$E=\left|{\bf E}\right|$. The next two terms couple the system to a bulk
reservoir, where $\mu_{c}$ is the chemical potentials of the counterions and
$\mu_{w}\left(\omega\right)$ is the chemical potential of water dipoles with
orientational angle $\omega$. $T$ is the temperature and $s$ is the entropy
density.

Consider a unit volume of the cell around the charged particle. The entropy
density is the logarithm of the number of translational and orientational
arrangements of non-interacting $n_{c}$ counterions and
$\rho\left(\omega_{i}\right)\Delta\Omega_{i}\left(i=1\cdots N\right)$ water
molecules, where $\Delta\Omega_{i}=2\pi sin\omega_{i}\Delta\omega$ is an
element of a solid angle and $\Delta\omega=\pi/N$. The counterion and water
molecule occupy volumes of $V_{c}$ and $V_{w}$, respectively. We assume that
the volumes are independent of the ionic concentrations. Within a lattice
statistics approach each particle in the suspension occupies more than one
cell of a lattice as in Popovic_pre_2013 ; Sin_electrochimica_2015 . Unlike in
Popovic_pre_2013 , orientational ordering of water dipoles as well as
translational arrangements of counterions is explicitly considered. We first
place $n_{c}$ counterions of the volume $V_{c}$. Accounting for orientational
ordering of water dipoles, we put in
$\rho\left(\omega_{i}\right)\left(i=0,1,...\right)$ water molecules of the
volume $V_{w}$ in the lattice. The number of arrangements $W$ is written as

$W=\frac{n_{s}\left(n_{s}-1\cdot
v_{v}\right)\cdots\left(n_{s}-\left(n_{c}-1\right)v_{c}\right)}{n_{c}!}\frac{\left(n_{s}-n_{c}v_{c}\right)\cdots
v_{w}}{\lim_{N\rightarrow\infty}\prod^{N}_{i=1}\left(\rho\left(\omega_{i}\right)\Delta\Omega_{i}\right)!},$
(3)

where $v_{c,w}=V_{c,w}/a^{3}$ are the numbers of cells that the counterion and
water molecule occupy, respectively. $n_{s}=1/a^{3}$ is the number of cells
per unit volume and $a$ denotes the linear dimension of one cell. Expanding
the logarithms of factorials using Stirlings formula, we obtain the expression
for the entropy density, $s=k_{B}\ln W$,

$\displaystyle\frac{s}{k_{B}}=\ln
W=n_{c}\ln{\frac{V_{c}}{a^{3}}}+\frac{1}{V_{c}}\ln{\frac{1}{V_{c}}}-n_{c}\ln{n_{c}}-\left(\frac{1}{V_{c}}-n_{c}\right)\ln{\left(\frac{1}{V_{c}}-n_{c}\right)}+\left(\frac{1-n_{c}V_{c}}{V_{w}}\right)\ln{\frac{V_{w}}{a^{3}}}$
$\displaystyle+\left(\frac{1-n_{c}V_{c}}{V_{w}}\right)\ln{\left(\frac{1-n_{c}V_{c}}{V_{w}}\right)}-\lim_{N\rightarrow\infty}\sum^{N}_{i=1}{\rho\left(\omega_{i}\right)\Delta\Omega_{i}}\ln{\left(\rho\left(\omega_{i}\right)\Delta\Omega_{i}\right)},$
(4)

where $k_{B}$ is the Boltzmann constant. The variation of the Lagrangian with
respect to $n_{c}$ yields an equation from which $n_{c}$ and
$\rho\left(\omega\right)$ in the suspension can be obtained. All lattice cells
are occupied by either counterions or water molecules, therefore

$\displaystyle n_{s}=n_{c}v_{c}+n_{w}v_{w}.$ (5)

Using the method of undetermined multipliers, the Lagrangian of the cell is

$\displaystyle L=F-\int\lambda\left({\bf
r}\right)\left(1-n_{c}V_{c}-n_{w}V_{w}\right)d{\bf r},$ (6)

where $\lambda$ is a local Lagrange parameter.

The Euler$-$Lagrange equations for the Lagrangian are obtained and solved with
respect to the functions $n_{c}$ and $\rho\left(\omega\right)$. The variation
of the Lagrangian with respect to $n_{c}$ yields an equation from which
$n_{c}$ and $\rho\left(\omega\right)$ in the suspension can be obtained.

$\displaystyle\frac{\delta L}{\delta
n_{c}}=e_{0}z_{c}\psi-\mu_{c}-k_{B}T\left(\ln\frac{V_{c}}{a^{3}}+\frac{V_{c}}{V_{w}}\ln{a^{3}}+\ln\frac{\left(1-n_{c}V_{c}\right)^{1-V_{c}/V_{w}}}{n_{c}V_{c}}\right)+\lambda
V_{c}=0.$ (7)

The first boundary condition is $\psi\left(r=b\right)=0$, that fixes the
origin of the electric potential at $r=b$. As shown in Roa_pccp_2011_1 , it
can be checked that the concentration of counterions, $n_{c}$, is the same
irrespective of the origin of the electric potential. Other boundary
conditions are $n_{c}\left(r=b\right)=n_{0}$ and
$\lambda\left(r=b\right)=\lambda_{0}$, where $n_{0}$ and $\lambda_{0}$ are
unknown coefficients that represent the ionic concentration and the Lagrange
parameter where the electric potential is zero, respectively. Using the
boundary conditions we get the chemical potential for counterions from Eq.(7):

$\displaystyle\mu_{c}=-k_{B}T\left(\ln\frac{V_{c}}{a^{3}}+\frac{V_{c}}{V_{w}}\ln{a^{3}}+\ln\frac{\left(1-n_{0}V_{c}\right)^{1-V_{c}/V_{w}}}{n_{0}V_{c}}\right)+\lambda_{0}V_{c}.$
(8)

Inserting Eq.(8) into Eq.(7), we obtain $n_{c}$ by exponentiation:

$\displaystyle\exp\left(-e_{0}z_{c}\psi/k_{B}T\right)\exp\left(V_{c}\left(\lambda-\lambda_{0}\right)/k_{B}T\right)=\frac{n_{c}\left(1-n_{0}V_{c}\right)^{1-V_{c}/V_{w}}}{n_{0}\left(1-n_{c}V_{c}\right)^{1-V_{c}/V_{w}}}.$
(9)

Like the derivation of Eq.(9), the expressions for $\rho\left(\omega\right)$
are simply obtained:

$\displaystyle\rho\left(\omega\right)=\rho_{0}\exp\left(-\frac{\gamma
p_{0}E\cos\omega}{k_{B}T}\right)\exp\left(V_{w}\left(\lambda-\lambda_{0}\right)/k_{B}T\right).$
(10)

In general, within our approach the counterions concentration and the number
density of water molecules are obtained implicitly not explicitly.

In the case when the counterions and water molecules have the same sizes, that
is, when $V_{w}=V_{c}$, we can recover the result of Gongadze_bioelechem_2012
in Eqs.(9,10). When we neglect orientational ordering of water dipoles, our
approach is identical to that of Popovic_pre_2013 .

The Euler$-$Lagrange equation for $\psi\left(r\right)$ yields the Poisson-
Boltzmann equation

$\displaystyle\frac{1}{r^{2}}\frac{d}{dr}\left(r^{2}\varepsilon_{0}\varepsilon_{r}\frac{d\psi}{dr}\right)=-e_{0}z_{c}n_{c},$
(11)

where

$\displaystyle\varepsilon_{r}\equiv n^{2}+\frac{\left|{\bf
P}\right|}{\varepsilon_{0}E}.$ (12)

Here, ${\bf P}$ is the polarization vector due to a total orientation of
point-like water dipoles. From the spherical symmetry of this problem, one can
see that the electric field strength is perpendicular to the surface of the
charged particle and have the same magnitude at all points equidistant from
the surface. Consequently, ${\bf P}$ is given as Gongadze_bioelechem_2012

$\displaystyle{\bf
P}\left(r\right)=c_{w}\left(r\right)\left(\frac{2+n^{2}}{3}\right)p_{0}\mathcal{L}\left(\gamma{p_{0}}E\beta\right)\hat{{\bf
e}},$ (13)

where a function $\mathcal{L}\left(u\right)=\coth\left(u\right)-1/u$ is the
Langevin function and $\hat{{\bf e}}={{\bf E}/E}$ .

Differentiation of Eqs.(9, 10, 5)with respect to the distance from the charged
surface provides linear algebraic equations in terms of
$d{n_{c}}/dr,d{n_{w}}/dr,dg/dx$, where
$g\equiv\left(\lambda-\lambda_{0}\right)/k_{B}T$:

$\displaystyle\frac{d{n_{w}}}{dr}=n_{w}\left[\mathcal{L}\left(\gamma{p_{0}}E\beta\right)\left(\gamma{p_{0}}\beta\right)\frac{dE}{dr}+V_{w}\frac{dg}{dr}\right],$
(14)
$\displaystyle\frac{d{n_{c}}}{dr}=\frac{n_{c}\left(1-n_{c}V_{c}\right)}{1-n_{c}V_{c}^{2}/V_{w}}\left(\frac{e_{0}z_{c}}{k_{B}T}\frac{d\psi}{dr}+V_{c}\frac{dg}{dr}\right),$
(15) $\displaystyle\frac{dn_{c}}{dr}V_{c}+\frac{dn_{w}}{dr}V_{w}=0$ (16)

Solving the system of Eqs.(14),(15), (16) for $d{n_{c}}/dr,d{n_{w}}/dr,dg/dr$
results in the following coupled differential equations:

$\displaystyle\frac{dn_{c}}{dr}=-\frac{n_{cc}n_{w}V_{c}V_{w}}{n_{w}V_{w}^{2}+n_{cc}V_{c}^{2}}\left[[\mathcal{L}\left(\gamma{p_{0}}E\beta\right)\left(\gamma{p_{0}}\beta\right)\frac{dE}{dr}+\frac{V_{w}}{V_{c}}\frac{e_{0}z_{c}}{k_{B}T}\frac{d\psi}{dr}\right]$
(17) $\displaystyle\frac{dn_{w}}{dr}=-\frac{V_{c}}{V_{w}}\frac{dn_{c}}{dr}$
(18)

, where
$n_{cc}=n_{c}\left[1-\frac{n_{c}V_{c}\left(V_{c}/V_{w}-1\right)}{1-n_{c}V_{c}}\right]^{-1}$.

The electrostatic potential, the counterions concentration and the number
density of water molecules are obtained by solving Eqs.(11), (17), (18),
respectively.

###  II.3  Excluded region in contact with the particle

As Lopez-Garcia et al.Lopez_physchemb_2010  and Roa et al.Roa_pccp_2011_1
did, we account for a distance of closest approach of the counterions to the
particle surface, resulting from their finite size. We consider counterions as
spheres of radius $R_{c}$ with a point charge at its center. Counterions can
not approach closer to the surface of the particle than their effective
hydration radius, $R_{c}$. Consequently, the ionic concentration will be zero
in the region between the spherical surface, $r=a$, and the spherical surface,
$r=a+R_{c}$. The electric potential $\psi\left(r\right)$ is determined by the
stepwise equation:

$\displaystyle{\frac{d^{2}\psi\left(r\right)}{dr^{2}}+\frac{2}{r}\frac{d\psi\left(r\right)}{dr}=0,a\leq
r\leq a+R_{c}}$ $\displaystyle{Eq.\left(11\right),a+R_{c}\leq r\leq b}.$ (19)

To completely specify the problem the electric potential should be forced to
be continuous at the surface $r=a+R_{C}$, and also its first derivative, which
is related to the continuity of the normal component of the electric
displacement at that surface. The boundary conditions needed for solving the
problem are

$\displaystyle\psi^{\prime}\left(r=a\right)=-\frac{\sigma}{\varepsilon\left(r=a\right)},$
$\displaystyle\psi\left(r=b\right)=0,\psi^{\prime}\left(r=b\right)=0,$
$\displaystyle\psi\left(r=\left(a+R_{c}\right)_{-}\right)=\psi\left(r=\left(a+R_{c}\right)_{+}\right),\psi^{\prime}\left(r=\left(a+R_{c}\right)_{-}\right)=\psi^{\prime}\left(r=\left(a+R_{c}\right)_{+}\right),$
(20)

,where subscript - refers to the region $a\leq r\leq a+R_{c}$, and subscript +
refers to the region $a+R_{c}\leq r\leq b$.

##  III Results and Discussion

Figure 2: (Color online) Electric potential distribution (a) and counterions
concentration (b) along the cell, considering or not orientational ordering of
water dipoles and/or the excluded region in contact with the particle. The
particle surface charge density, the particle volume fraction and the maximum
possible concentration of counterions due to the excluded volume effect are
$\sigma=$0.4C/$m^{2},\phi=0.5$ and $n_{c}^{max}=22$M, respectively. Figure 3:
(Color online) (a). Relative permittivity along the cell, considering
(circles, DPBL) or not (solid lines, DPB) the excluded region in contact with
the particle in the case when orientational ordering of water dipoles is taken
into account. (b). Relative permittivity along the cell for different ion
sizes, considering the excluded region in contact with the particle (DPBL).
Triangles, circles and solid lines stand for $n_{c}^{max}=$ 22M, 10M and 4M.
Other parameters are the same as in the FiG. 2.

Under the boundary conditions, we combine Eqs. (19, 20) and solve these
differential equations for $n_{c},n_{w},\psi$ by using the fourth order Runge-
Kutta method, which is combined with the shooting method. Calculations are
started at the outer surface of the cell. The counterions concentration
$n_{0}$ at the surface of the cell is varied to satisfy the boundary condition
Eq.(20) for every given surface charge density. For all the calculations, the
temperature $T$, the valence of the added counterions $z_{c}$ and the particle
radius $a$ have been taken equal to 298.15K , -1 and 100nm, respectively. As
in Gongadze_bioelechem_2012 , the water dipole moment $p_{0}$ should be
3.1D(Debye is $3.336\times 10^{-30}$C/m) so that far away from the charged
surface($r=b$) the relative permittivity of the suspension reaches the value
of pure water($\epsilon_{r}=78.5$). In calculations, we choose $n_{0w}=55$M
for the number density of water molecules in the bulk suspension. In molar
concentrations, the values used in the calculations, $n_{c}=$ 22, 10 and 4 M,
correspond approximately to counterion effective diameters of $2R_{c}=$0.425,
0.55 and 0.75nm, respectively.

FIG. 2 shows the electric potential distribution, FIG. 2(a), and the
counterions concentration profiles, FIG. 2(b), along the cell. Solid lines
represent the predictions of the equation considering only finite ion sizes
without a distance of closest approach to the particle surface (MPB). Dashed
lines stand for the results of the equation accounting for finite ion sizes
and a distance of closest approach to the particle surface (MPBL). Circles
correspond to the outcome of the equation taking into account finite ion sizes
and orientational ordering of water dipoles(DPB). Plus signs exhibit the
equation accounting for finite ion sizes, orientational ordering of water
dipoles and a distance of closest approach to the particle surface (DPBL). The
particle surface charge density have been chosen equal to 0.4C/$m^{2}$ and the
particle volume fraction is $\phi=0.5$(very concentrated suspension), which
implies a normalized cell size of $b/a=1.26$. In fact, the authors of
Roa_pccp_2011_1  also used the same size of parameters, but did not consider
orientational ordering of water dipoles.

FIG. 2(a) shows that for our cases, the electric potentials are higher than
ones of Roa_pccp_2011_1 . This is attributed to the fact that orientational
ordering of water dipoles requires an additional electric energy. In the case
when we take into account the distance of closest approach of the counterions
to the particle surface( DPBL model), there is an higher increase of the
surface potential as in Roa_pccp_2011_1 . Although in the case of DPBL model
the surface electric potential reaches 2V that appears unfeasible, in the case
of DPB model the potential is about 1V. It means that for the case of DPBL, in
the region of $a+R_{c}\leq r\leq b$ the electric potential difference is about
1V, that is below the decomposition potential of water. The rest of potential
difference is applied to the region of closest approach to the particle
surface. As a result, $\sigma$=0.4C/$m^{2}$ is the maximum possible surface
charge density for stable presence of suspension. This is consistent with the
fact that in Bohnic_bioelechem_2005 ; Roa_pccp_2011_1  calculations was
performed within the region of $\sigma\leq 0.4C/m^{2}$, which is called as
physiological range. This shows that our approach well represents practical
situations. We can observe in FIG. 2(b) that accounting for orientational
ordering of water dipoles causes non-monotonous counterions concentration
profiles, i.e. the position of the maximum counterions concentration is not
located at the position of the surface of the particle. This is due to the
statistical mechanical competition effect between orientational ordering of
water dipoles and counterion condensation near the particle surface
Gongadze_genphysiol_2013 ; Sin_electrochimica_2015 . For the counterions
concentration profiles, our approach mathematically predicts two peaks. The
higher one of them is equal to one of the case considering only finite ion
size Roa_pccp_2011_1 , $n_{c}^{max}$. The higher peak occurs at a larger
particle surface charge density than corresponding one of the lower peak. The
formation of the higher peak requires quite a large particle surface charge
density which corresponds to the unphysical value above the decomposition
potential of water.

FIG. 3 shows the permittivity of the suspension for considering (circles,
DPBL) or not (solid lines, DPB) the excluded region in contact with the
particle, FIG. 3(a), and for a particle volume fraction $\phi=0.5$ for
different ion sizes, FIG. 3(b), along the cell when orientational ordering of
water dipoles is taken into account. The parameters are the same as in FIG. 2.
FIG. 3(a) shows that the permittivity of the suspension near the particle
surface decreases towards the particle surface. This decrease of
$\epsilon_{r}$ is attributed to the increased orientational ordering of water
dipoles and increased depletion of water molecules due to the accumulated
counterions near the particle surface. The spatial region with decreased
permittivity extends to a larger distance when we take into account the
excluded region in contact with the particle. As shown in FIG. 3(b), it is
obvious that the larger the counterion size, the wider the spatial region with
permittivity lower than one of pure water. Eqs. (12, 13) explain that a small
number of water dipoles and increased orientational ordering results in
decreased permittivity of the suspension, as discussed in FIG. 3(a). FIG. 3(a)
and FIG. 3(b) well represent that close to the charge surface the orientation
of water molecules and depletion of water molecules result in spatial
variation of permittivity Outhwaite_molphys_1976 ; Butt_physcheminterf_2003 ;
Gongadze_bioelechem_2012 .

FIG. 4 shows the effective charge divided by the particle charge along the
cell for a particle volume fraction $\phi=0.5$, for different ion sizes and
for MPBL and DPBL. The parameters are the same as in Fig. 2. It is shown in
FIG. 4 that the effective charges for the method(DPBL) studied by considering
orientational ordering of water dipoles are larger than corresponding ones of
Roa_pccp_2011_1 (MPBL). In other words, orientational ordering of water
dipoles diminishes the screening of the suspension. This is due to the non-
monotonous counterions concentration profiles as shown in FIG. 2(a).

Figure 4: (Color online) Effective charge divided by the particle charge along
the cell for different ion sizes, considering or not orientational ordering of
water dipoles in the case when the excluded region in contact with the
particle is taken into account. For the case when orientational ordering of
water dipoles is not taken into account(MPBL), squares, dashed lines and solid
lines stand for $n_{c}^{max}=$4M, 10M and 22M, respectively. For the case when
orientational ordering of water dipoles is taken into account(MPBL), crosses,
circles and triangles correspond to $n_{c}^{max}=$4M, 10M and 22M,
respectively. Other parameters are the same as in Fig.3(b). Figure 5: (Color
online) (a). Surface electric potential for different values of particle
surface charge density for different ion sizes, considering or not
orientational ordering of water dipoles and/or the excluded region in contact
with the particle(MPB, MPBL, DPB, DPBL). (b). Surface potential against the
particle surface charge density for different particle volume fraction values.
Other parameters are the same as in Fig. 2. Figure 6: (Color online) Surface
number density of water molecules (a) and surface relative permittivity (b) as
functions of particle surface charge density for different ion sizes,
considering the excluded region in contact with the particle and orientaional
ordering of water dipoles. Circles, dashed lines and solid lines stand for
$n_{c}^{max}=$22M, 10M and 4M. Other parameters are the same as in Fig. 2.

FIG. 5 displays the equilibrium electric surface potential as a function of
particle surface charge density for different ion sizes and $\phi=0.5$ , FIG.
5(a), and for different particle volume fractions and $n_{c}^{max}=22$M, FIG.
5(b). It is shown in FIG. 5(a) that although in all cases the surface electric
potential increases with particle surface charge density, the shapes of the
profiles clearly differ from each other. In the cases when orientational
ordering of water dipoles is taken into account(DPB and DPBL), the surface
potential with particle surface charge density rapidly increases compared to
the case of no accounting for water dipoles(MPB and MPBL), respectively. As
shown in Roa_pccp_2011_1 , PB equation predicts that in the region of low
surface charge density, the surface potential sharply increases with the
surface charge density. This is in agreement with the predictions of our
theory as well as MPB. However, in the region of medium and high charge
density, the surface electric potential predicted by MPB increases more
rapidly than ones of PB as proved in Roa_pccp_2011_1 . In the cases of DPB and
DPBL, the behavior of the classical condensation effect is severely limited,
because in the high regime of the surface charge the additional counterions
are located in farther positions form the particle surface than ones predicted
by MPB and MPBL as shown in FIG. 2(b). Consequently, in the case when
orientational ordering of water dipoles is explicitly considered, the further
increase of the surface potential is attributed to the larger extent of
counterion condensation compared to the case of no accounting for
orientational ordering of water dipoles. It can be intuitively explained that
from the medium regime, the results of DPBL and DPB theories are significantly
deviated from corresponding ones of MPBL and MPB, respectively. In fact, a
high surface charge density yields a wide spatial region with low permittivity
compared to the case of the low surface charge density. Combining the above
fact with the boundary condition
$E=\frac{\sigma}{\epsilon_{r}\left(r=a\right)}$ and the definition of electric
field strength ${\bf E}=-\frac{d\psi}{dr}$, we can easily verify that the
results of DPBL and DPB theories are higher than ones of MPBL and MPB,
respectively. FIG. 5(b) shows that in the case of orientational ordering of
water dipoles is taken into account(DPBL), the surface electric potential
increases with the particle volume fraction as in the case of MPBL. When the
particle concentration rises, the space for the counterions inside the cell
gets small and, consequently the screening of the particle charge is enhanced,
thus reducing the value of the surface potential. This fact will have
significant consequences on the electrokinetic properties of colloidal
particles in concentrated salt-free suspensions, as shown in
Aranda_colloidinterf_2009 ; Rascon_colloidinterf_2009  for dilute suspensions
in electrolyte solutions.

FIG. 6(a) and FIG. 6(b) show the number density of water molecules and the
relative electric permittivity of the suspension at the particle surface
according to the particle surface charge density for different ion sizes,
respectively. FIG. 6(a) exhibits that accounting for simultaneously
orientational ordering of water dipoles and finite size effects yields a non-
monotonous behavior of the number density of water molecules at the particle
surface. It should be noted that the smaller counterion size involves the
shallower valley of the number density of water molecules at the particle
surface. Then we note that all the number densities of water molecules are
nearly equal in the high regime of surface charge density. According to
Eqs.(12, 13), the number density of water molecules is proportional to the
relative permittivity at any position. On the other hand, the electric
permittivity decreases with magnitude of the electric field strength at any
position. Even though in the case of larger number density of water molecules,
electric field strength gets slightly smaller, the sequence of magnitude of
the electric permittivities for all cases studied is in agreement with one of
magnitude of corresponding number densities of water molecules as shown in
Fig. 6(b).

##  IV Conclusions

In this work we have studied the influence of non-uniform size effects and
orientational ordering of water dipoles on the description of the equilibrium
electric double layer of a spherical colloidal particle in a concentrated
salt-free suspension.

We have used a cell model approach to deal with particle-particle interaction,
and extended Poisson-Boltzmann equations to account for such non-uniform size
effects and orientational ordering of water dipoles. The theoretical procedure
has followed that used by the authors Sin_electrochimica_2015  but with the
additional inclusion of a region of closest approach for counterions to the
particle surface. Unlike in Roa_pccp_2011_1 , our PB approach can consider
different sizes of different species of counterions as well as the difference
in sizes of counterions and water molecules. We also have calculated the
counterions concentration, equilibrium electric potential and relative
permittivity for concentrated suspensions. The results have shown that
orientational ordering of water dipoles is quite important for medium to high
particle charges at every particle volume fraction, and even more if the
distance of closest approach of the counterions to the particle surface is
taken into account.

This equilibrium model presented in this study will be used as the base of
non-equilibrium models for the response of a suspension to external electric
fields. Experimental results concerning the static or dynamic electrophoretic
mobilities, electrical conductivity and dielectric response, should be
compared with the predictions of non-equilibrium models. Although the
stratification of counterions associated with the difference in size of the
counterions has not been accessed in the present study, consideration of the
difference in size of the counterions is very important for realistic salt-
free suspensions which contain different species of counterions. Recently, the
authors of Li_pre_2011 ; Li_pre_2012  studied the competition of multiple
counterions of different valences and different sizes in binding to the
surface of a spherical colloidal particle by both a mean-field theory and
Monte Carlo simulations. The both methods predicted the stratification of
counterions around the charged surface and found that the ionic valence-to-
volume ratios, instead of ionic valences alone, are the key factors that
determine the binding of counterions to the charged surface. Because the
authors of Li_pre_2011 ; Li_pre_2012  did not consider decreased permittivity
of suspension near the charge particle, it will be interesting to study the
phenomena by using our method. Additionally, Monte Carlo approach accounting
for both non-uniform size effects and orientational ordering of water dipoles
is necessary for studying deeply the phenomena. As a final conclusion, we
emphasize that we can apply this model to prediction of non-equilibrium
properties in realistic salt-free concentrated suspensions. The task will be
performed by the authors in the near future.

## References

  * (1) J. Lyklema, Fundamentals of interface and colloid science: vol. II, Solid-liquid interfaces (Academic Press,London, 1995).
  * (2) R. J. Hunter, Foundations of colloid science (Oxford University Press, London, 1995).
  * (3) J. H. Masliyah and S. Bhattacharjee, Electrokinetic and colloid transport phenomena (Wiley-Interscience, New Jersey, 2006).
  * (4) R. W. OBrien, J. Fluid Mech. 212, 81 (1990).
  * (5) A. S. Dukhin, H. Ohshima, V. N. Shilov, and P. J. Goetz, Langmuir 15, 3445 (1999).
  * (6) A. K. Sood, Solid State Physics (Academic Press, 1991), vol. 45, p. 1.
  * (7) M. Medebach and T. Palberg, J. Chem. Phys. 119, 3360 (2003).
  * (8) F. Carrique, E. Ruiz-Reina, F. J. Arroyo, and A. V. Delgado, J. Phys. Chem. B 110, 18313 (2006).
  * (9) F. Carrique, E. Ruiz-Reina, F. J. Arroyo, M. L. Jimenez and A. V. Delgado, Langmuir 24, 2395(2008).
  * (10) F. Carrique, E. Ruiz-Reina, F. J. Arroyo, M. L. Jimenez and A. V. Delgado, Langmuir 24, 11544 (2008).
  * (11) E. Ruiz-Reina and F. Carrique, J. Phys. Chem. C 111, 141 (2007).
  * (12) E. Ruiz-Reina and F. Carrique, J. Phys. Chem. B 112, 11960 (2008).
  * (13) F. Carrique and E. Ruiz-Reina, J. Phys. Chem. B 113, 8613 (2009).
  * (14) F. Carrique and E. Ruiz-Reina, J. Phys. Chem. B 113, 10261 (2009).
  * (15) E. Ruiz-Reina and F. Carrique, J. Colloid Interface Sci. 345, 538 (2010).
  * (16) F. Carrique, E. Ruiz-Reina, F. J. Arroyo, and A. V. Delgado, J. Phys. Chem. B 114, 6134 (2010).
  * (17) A. R. Denton, J. Phys.: Condens. Matter 22, 364108 (2010).
  * (18) J. J. Lopez-Garcia, M. J. Aranda-Rascon, and J. Horno, J. Colloid Interface Sci. 316, 196 (2007).
  * (19) J. J. Lopez-Garcia, M. J. Aranda-Rascon, and J. Horno, J. Colloid Interface Sci. 323, 146 (2008).
  * (20) M. J. Aranda-Rascon, C. Grosse, J. J. Lopez-Garcia, and J. Horno, J. Colloid Interface Sci. 335, 250 (2009).
  * (21) M. J. Aranda-Rascon, C. Grosse, J. J. Lopez-Garcia, and J. Horno, J. Colloid Interface Sci. 336, 857 (2009).
  * (22) J. J. Lopez-Garcia, M. J. Aranda-Rascon, C. Grosse, and J. Horno, J. Phys. Chem. B 114, 7548 (2010).
  * (23) R. Roa, F. Carrique, and E. Ruiz-Reina, Phys. Chem. Chem. Phys. 13, 3960 (2011).
  * (24) R. Roa, F. Carrique, and E. Ruiz-Reina, Phys. Chem. Chem. Phys. 13, 9644 (2011).
  * (25) R. Roa, F. Carrique, and E. Ruiz-Reina, Phys. Chem. Chem. Phys. 13, 19437 (2011).
  * (26) R. Roa, F. Carrique, and E. Ruiz-Reina, J. Colloid Interface Sci. 387, 153 (2012).
  * (27) I. Borukhov, J. Polym. Sci. B Polym. Phys. 42, 3598 (2004).
  * (28) J. Ibarra-Armenta, A. Martin-Molina, and M. Quesada Perez, Phys. Chem. Chem. Phys. 11, 309 (2009).
  * (29) E. Gonzalez-Tovar and M. Lozada-Cassou, J. Phys. Chem. 93, 3761 (1989).
  * (30) M. G. Gouy, J. Phys.(France) 9, 457 (1910).
  * (31) D. L. Chapman, Philos. Mag. 25, 475 (1913).
  * (32) H. Helmholtz, Ann. Phys. 7, 337 (1879).
  * (33) O. Stern, Z. Elektrochem. 30, 508 (1924).
  * (34) J. J. Bikerman, Philos. Mag. 33, 508 (1942).
  * (35) I. Borukhov, D. Andelman, and H. Orland, Phys. Rev. Lett. 79, 435 (1997).
  * (36) I. Borukhov, D. Andelman, and H. Orland, Electrochim. Acta 46, 221 (2000).
  * (37) V. Kralj-Iglič and A. Iglič, J. Phys. France, 6, 477 (1996).
  * (38) K. Bohnic, V. Kralj-Iglič, and A. Iglič, Electrochim. Acta 46, 3033 (2001).
  * (39) K. Bohnic, A. Iglič, T. Slivnik, and V. Kralj-Iglič, Bioelectrochemistry 57, 73 (2002).
  * (40) K. Bohnic, J. Gimsa, V. Kralj-Iglič, T. Slivnik, and A. Iglič, Bioelectrochemistry 67, 91 (2005).
  * (41) G. Tresset, Phys. Rev. E. 78, 061506 (2008).
  * (42) V. B. Chu, Y. Bai, J. Lipfert, D. Herschlag, and S. Doniach. J., Biophys. J. 93, 3202 (2007).
  * (43) P. M. Biesheuvel and K. van Soestbergen, J. Colloid Interface Sci. 316, 490 (2007).
  * (44) S. Zhou, Z. Wang, and B. Li, Phys. Rev. E. 84:021901 (2011).
  * (45) J. Wen, S. Zhou, S. Xu, and B. Li, Phys. Rev. E. 85, 041406 (2012).
  * (46) A. H. Boschitsch and P.V. Danilov, J. Comput. Chem. 33, 1152 (2012).
  * (47) A. A. Kornyshev, J. Phys. Chem. B 111, 5545 (2007).
  * (48) M. Popovic and A. Siber, Phys. Rev. E. 88, 022302:1-5 (2013).
  * (49) L. Onsager, J. Am. Chem. Soc. 58, 1486 (1936).
  * (50) J. G. Kirkwood, J. Chem. Phys. 7, 911 (1939).
  * (51) F. Booth, J. Chem. Phys. 19, 391 (1951).
  * (52) F. Booth, J. Chem. Phys. 23, 453 (1955).
  * (53) A. Iglič, E. Gongadze, and K. Bohnic, Bioelectrochemistry 79, 223 (2010).
  * (54) E. Gongadze and A. Iglič, Bioelectrochemistry 87, 199 (2012).
  * (55) E. Gongadze, A. Velikonja, T. Slivnik, V. Kralj-Iglič, and A. Iglič, Electrochim. Acta 109, 656 (2013).
  * (56) J.-S. Sin, S.-J. Im, and K.-I. Kim, Electrochim. Acta 153, 531 (2015).
  * (57) E. Gongadze and A. Iglič, Gen. Physiol. Biophys. 32, 143 (2013).
  * (58) H. J. Butt, K. Graf, M. Kappl, Physics and chemistry of interfaces. 1st ed. (Wiley-VCH Verlag, Weinhelm, 2003).
  * (59) C. W. Outhwaite , Mol. Phys. 31, 1345 (1976).


Let $\varphi\in\text{LTL($\\{{\textsf{F}},{\textsf{G}},\land\\}$)}$ be flat,
and let $A,A^{\prime}\subseteq\mathit{AP}$. It is the case that
$\varphi[A][A^{\prime}]\in\\{\varphi[A],{\mathit{false}}\\}$.

###### Proof:

If $\varphi[A]={\mathit{false}}$, then
$\varphi[A][A^{\prime}]={\mathit{false}}$. Otherwise, by definition,
$\varphi[A][A^{\prime}]$ is either $\varphi[A]$ or ${\mathit{false}}$. ∎

See 5

###### Proof:

Let $i\in[1..n-1]$. By definition of $\mathcal{A}_{\varphi}$, there exist
$\psi_{i}\in\mathfrak{U}(r_{i-1})$ and $\psi_{i+1}\in\mathfrak{U}(r_{i})$ such
that $r_{i}=\psi_{i}[A_{i}]\neq{\mathit{false}}$ and
$r_{i+1}=\psi_{i+1}[A_{i+1}]\neq{\mathit{false}}$. There are two cases.

_Case $\psi_{i+1}=r_{i}$_. We have

$r_{i+1}=\psi_{i+1}[A_{i+1}]=r_{i}[A_{i+1}]=\psi_{i}[A_{i}][A_{i+1}].$

As $r_{i+1}\neq{\mathit{false}}$, it is the case that
$\psi_{i}[A_{i}][A_{i+1}]=\psi_{i}[A_{i}]=r_{i}$ by Proposition 27. Therefore,
$r_{i}=r_{i+1}$, which contradicts the fact that the path is simple.

_Case $\psi_{i+1}\neq r_{i}$_. We have
$|r_{i+1}|_{\textsf{F}}=|\psi_{i+1}[A_{i+1}]|_{\textsf{F}}\leq|\psi_{i+1}|_{\textsf{F}}$
by Item 2 of Proposition 4. Moreover, we have
$|\psi_{i+1}|_{\textsf{F}}<|r_{i}|_{\textsf{F}}$ by Item 1 of Proposition 4,
since $\psi_{i+1}\in\mathfrak{U}(r_{i})\setminus\\{r_{i}\\}$. ∎

See 1

###### Proof:

We proceed by induction on $|\varphi|_{\textsf{F}}$.

If $|\varphi|_{\textsf{F}}=0$, then $\varphi$ is of the form
$\psi\land{\textsf{G}}\psi^{\prime}\land\bigwedge_{i\in
I}{\textsf{G}}{\textsf{F}}\psi_{i}^{\prime\prime}$. Let
$\varphi^{\prime}\coloneqq\varphi[w(0)]$. Note that
$\mathfrak{U}(\varphi)=\\{\varphi\\}$. We have

$\displaystyle w\models\varphi$ $\displaystyle\iff\ $
$\displaystyle\mathrm{prop}(\psi\land\psi^{\prime})\subseteq w(0)\land
w[1..]\models({\textsf{G}}\psi^{\prime}\land\bigwedge_{i\in
I}{\textsf{G}}{\textsf{F}}\psi_{i}^{\prime\prime})$ $\displaystyle\iff\ $
$\displaystyle\varphi[w(0)]\neq{\mathit{false}}\land
w[1..]\models\varphi[w(0)]$ $\displaystyle\iff\ $
$\displaystyle\varphi\xrightarrow{}^{w(0)}\varphi^{\prime}\land
w[1..]\models\varphi^{\prime}.$

Now, assume that $\varphi=\theta\land{\textsf{F}}\psi$ where $\theta$ and
$\psi$ are flat.

$\Rightarrow$) Let $w\models\varphi$. We have $w\models\theta$ and
$w\models{\textsf{F}}\psi$. By induction hypothesis, there exists
$\theta^{\prime}$ such that $\theta\xrightarrow{}^{w(0)}\theta^{\prime}$ and
$w[1..]\models\theta^{\prime}$. By definition of $\mathfrak{U}(\cdot)$, we
have
$\theta\land{\textsf{F}}\psi\xrightarrow{}^{w(0)}\theta^{\prime}\land{\textsf{F}}\psi$.
So, if $w[1..]\models{\textsf{F}}\psi$, then we are done by taking
$\varphi^{\prime}\coloneqq\theta^{\prime}\land{\textsf{F}}\psi$. Otherwise, we
must have $w\models\psi$. By induction hypothesis, there exists
$\psi^{\prime}$ such that $\psi\xrightarrow{}^{w(0)}\psi^{\prime}$ and
$w[1..]\models\psi^{\prime}$. Since
$\mathfrak{U}(\psi)\subseteq\mathfrak{U}({\textsf{F}}\psi)$, we have
${\textsf{F}}\psi\xrightarrow{}^{w(0)}\psi^{\prime}$, and hence
$\theta\land{\textsf{F}}\psi\xrightarrow{}^{w(0)}\theta^{\prime}\land\psi^{\prime}$.
So, we are done by taking
$\varphi^{\prime}\coloneqq\theta^{\prime}\land\psi^{\prime}$.

$\Leftarrow$) Let $\varphi^{\prime}$ satisfy
$\varphi\xrightarrow{}^{w(0)}\varphi^{\prime}$ and
$w[1..]\models\varphi^{\prime}$. By definition of ${\xrightarrow{}}$, there
exist $\theta^{\prime},\psi^{\prime}$ such that
$\theta\xrightarrow{}^{w(0)}\theta^{\prime}$,
${\textsf{F}}\psi\xrightarrow{}^{w(0)}\psi^{\prime}$ and
$\varphi^{\prime}=\theta^{\prime}\land\psi^{\prime}$. Thus,
$w[1..]\models\theta^{\prime}$ and $w[1..]\models\psi^{\prime}$. By induction
hypothesis, we have $w\models\theta$. It remains to show that
$w\models{\textsf{F}}\psi$.

If $\psi^{\prime}\neq{\textsf{F}}\psi$, then
$|\psi^{\prime}|_{\textsf{F}}<|{\textsf{F}}\psi|_{\textsf{F}}$ by Proposition
4, and hence $w\models{\textsf{F}}\psi$ by induction hypothesis. Otherwise, we
have $\psi^{\prime}={\textsf{F}}\psi$ and so $w[1..]\models{\textsf{F}}\psi$,
and in particular $w\models{\textsf{F}}\psi$. ∎

###### Proof:

We proceed by induction on $|\varphi|_{\textsf{F}}$. If
$|\varphi|_{\textsf{F}}=0$, then the claim trivially holds. Let
$\varphi=\theta\land{\textsf{F}}\psi$ where $\theta$ and $\psi$ are flat.

$\Leftarrow)$ Since $\varphi\xrightarrow{}^{w(0)\cdots
w(i-1)}\varphi^{\prime}$ and $w[i..]\models\varphi^{\prime}$, repeated
applications of Item 1 yields $w\models\varphi$.

$\Rightarrow$) Let $w\models\varphi$. It is the case that $w\models\theta$ and
$w\models{\textsf{F}}\psi$. Let $j\in\mathbb{N}$ be such that
$w[j..]\models\psi$. By Item 1, there exists $\psi^{\prime}$ such that
$\psi\xrightarrow{}^{w(j)}\psi^{\prime}$ and $w[j+1..]\models\psi^{\prime}$.
By definition of ${\xrightarrow{}}$, there exists
$\psi^{\prime\prime}\in\mathfrak{U}(\psi)$ such that
$\psi^{\prime}=\psi^{\prime\prime}[w(j)]$. As
$\mathfrak{U}(\psi)\subseteq\mathfrak{U}({\textsf{F}}\psi)$, we have
$\psi^{\prime\prime}\in\mathfrak{U}({\textsf{F}}\psi)$, and so
${\textsf{F}}\psi\xrightarrow{}^{w(j)}\psi^{\prime}$. Moreover, we have
${\textsf{F}}\psi\xrightarrow{}^{w(0)\cdots w(j-1)}{\textsf{F}}\psi$. Thus,
${\textsf{F}}\psi\xrightarrow{}^{w(0)\cdots w(j)}\psi^{\prime}$.

By repeated applications of Item 1, there exists $\theta^{\prime}$ such that
$\theta\xrightarrow{}^{w(0)\cdots w(j)}\theta^{\prime}$ and
$w[j+1..]\models\theta^{\prime}$. Hence,

$(\theta\land{\textsf{F}}\psi)\xrightarrow{}^{w(0)\cdots
w(j)}(\theta^{\prime}\land\psi^{\prime})\text{ and
}w[j+1..]\models\theta\land\psi^{\prime}.$

By Proposition 4, we have
$|\theta|_{\textsf{F}}\geq|\theta^{\prime}|_{\textsf{F}}$ and
$|{\textsf{F}}\psi|_{\textsf{F}}>|\psi^{\prime}|_{\textsf{F}}$. Thus,
$|\theta\land{\textsf{F}}\psi|_{\textsf{F}}>|\theta^{\prime}\land\psi^{\prime}|_{\textsf{F}}$.
So, by induction hypothesis, there exist $k\geq j+1$ and $\varphi^{\prime}$
such that $(\theta^{\prime}\land\psi^{\prime})\xrightarrow{}^{w(j+1)\cdots
w(k-1)}\varphi^{\prime}$, $|\varphi^{\prime}|_{\textsf{F}}=0$ and
$w[k..]\models\varphi^{\prime}$. We are done since

$\varphi=(\theta\land{\textsf{F}}\psi)\xrightarrow{}^{w(0)\cdots
w(j)}(\theta^{\prime}\land\psi^{\prime})\xrightarrow{}^{w(j+1)\cdots
w(k-1)}\varphi^{\prime}.$

See 8

###### Proof:

  1. 1.

We assume that $X_{q,r}\neq\emptyset$, as we are otherwise trivially done. Let
us first show that $X_{q,r}$ is closed under intersection. Let $A,B\in
X_{q,r}$. By definition of ${\xrightarrow{}}$, there must exist
$\theta\in\mathfrak{U}(q)$ such that $r=\theta[A]=\theta[B]$. Moreover,
$\theta$ is of the form

$\theta=\psi\land{\textsf{G}}\psi^{\prime}\land\bigwedge_{i\in
I}{\textsf{G}}{\textsf{F}}\psi_{i}^{\prime\prime}\land\bigwedge_{j\in
J}{\textsf{F}}\varphi_{j},$

and it is the case that $\mathrm{prop}(\psi\land\psi^{\prime})\subseteq A$ and
$\mathrm{prop}(\psi\land\psi^{\prime})\subseteq B$. This means that
$\mathrm{prop}(\psi\land\psi^{\prime})\subseteq A\cap B$, and hence that
$r=\theta[A\cap B]$, which implies $q\xrightarrow{}^{A\cap B}r$.

Since $X_{q,r}$ is closed under intersection, it has a minimal element $A$,
which is in fact $A\coloneqq\mathrm{prop}(\psi\land\psi^{\prime})$ and can
thus be obtained in polynomial time from $\theta$. We have
$X_{q,r}={\uparrow\\!{A}}$, as for any $A^{\prime}\supseteq A$, we have
$\mathrm{prop}(\psi\land\psi^{\prime})=A\subseteq A^{\prime}$, and so
$q\xrightarrow{}^{A^{\prime}}\theta[A^{\prime}]=r$.

  2. 2.

Since $X_{q,r}\neq\emptyset$, there exist $\theta\in\mathfrak{U}(q)$ and
$A\subseteq\mathit{AP}$ such that $r=\theta[A]$. Thus, $r$ is of the form
${\textsf{G}}\psi^{\prime}\land\bigwedge_{i\in
I}{\textsf{G}}{\textsf{F}}\psi_{i}^{\prime\prime}\land\bigwedge_{j\in
J}{\textsf{F}}\varphi_{j}$. Note that $r\in\mathfrak{U}(r)$ and $r[B]=r$ where
$B\coloneqq\mathrm{prop}(\psi^{\prime})$. Thus, $r\xrightarrow{}^{B}r$, and so
$B\in X_{r,r}$.

  3. 3.

Since $X_{q,q}\neq\emptyset$, $q$ is of the form
$q={\textsf{G}}\psi^{\prime}\land\bigwedge_{i\in
I}{\textsf{G}}{\textsf{F}}\psi_{i}^{\prime\prime}\land\bigwedge_{j\in
J}{\textsf{F}}\varphi_{j}$. Let $\theta\in\mathfrak{U}(q)$. The latter is of
the form

$\displaystyle\theta$
$\displaystyle=\psi_{\mathfrak{U}}\land{\textsf{G}}(\psi^{\prime}\land\psi_{\mathfrak{U}}^{\prime})\land\bigwedge_{i\in
I_{\mathfrak{U}}}{\textsf{G}}{\textsf{F}}\psi_{i}^{\prime\prime}\land\bigwedge_{j\in
J_{\mathfrak{U}}}{\textsf{F}}\varphi_{j}.$

Testing $\mathrm{prop}(\psi^{\prime})\subseteq A$ is less restrictive than
$\mathrm{prop}(\psi_{\mathfrak{U}}\land\psi^{\prime}\land\psi_{\mathfrak{U}}^{\prime})\subseteq
A$. So, if $\theta[A]\neq{\mathit{false}}$, then $q[A]\neq{\mathit{false}}$.
As $q\in\mathfrak{U}(q)$, this means that $q\xrightarrow{}^{A}r$ implies
$q\xrightarrow{}^{A}q$. ∎

##  Appendix C Missing proofs of Section IV

See 2

###### Proof:

Let us give the details missing from the main text.

  1. 1.

We show that $\bm{x}\models_{\mathit{M}}{\textsf{F}}\neg Z$ iff $\bm{x}\not\in
Z$ or there exists a mode $\bm{m}\in\mathit{M}$ such that $\bm{m}\neq\bm{0}$.

$\Rightarrow)$ For the sake of contradiction, suppose that $\bm{x}\in Z$ and
that there is no $\bm{m}\in M$ with $\bm{m}\neq\bm{0}$. Clearly, we can never
reach a point other than $\bm{x}$.

$\Leftarrow)$ If $\bm{x}\not\in Z$, then clearly
$\bm{x}\models_{\mathit{M}}{\textsf{F}}\neg Z$. Otherwise, we have $\bm{m}\in
Z$ with $\bm{m}\neq\bm{0}$. Since we assume $Z$ to be a bounded zone, it must
hold that by simply scheduling $\bm{m}$ forever, we eventually leave $Z$.

  2. 2.

We show that $\bm{x}\models_{\mathit{M}}{\textsf{G}}\neg Z$ iff $\bm{x}\not\in
Z$ and there exists a mode $\bm{m}\in\mathit{M}$ such that for all
$\alpha\in\mathbb{R}_{>0}$ it is the case that $\bm{x}+\alpha\bm{m}\not\in Z$.

$\Leftarrow)$ It is easy to see that the execution obtained by scheduling
$\bm{m}$ for an infinite duration satisfies the formula since
$\bm{x}+\alpha\bm{m}\not\in Z$ for all $\alpha\in\mathbb{R}_{>0}$.

$\Rightarrow)$ Clearly, it must hold that $\bm{x}\not\in Z$. Let the modes of
$\mathit{M}$ be $\\{\bm{m}_{1},\dots,\bm{m}_{n}\\}$. To prove the other half,
assume for contradiction that for all $i\in[1..n]$, it holds that
$\bm{x}+\alpha_{i}\bm{m}_{i}\in Z$ for some $\alpha_{i}\in\mathbb{R}_{>0}$.
Let us demonstrate that for any non-Zeno infinite schedule $\rho$, it is the
case that $\mathrm{exec}(\rho,\bm{x})\not\models{\textsf{G}}\neg Z$. We do so
by showing the existence of $\tau\in\mathbb{R}_{\geq 0}$ and $\bm{z}\in Z$
such that $\bm{x}\xrightarrow{}^{\rho[..\tau]}\bm{z}$.

Let $\bm{m}^{\prime}_{i}\coloneqq\alpha_{i}\bm{m}_{i}$, and let us consider
the MMS $\mathit{M}^{\prime}\coloneqq\\{\alpha_{i}\bm{m}_{i}:i\in[1..n]\\}$.
Clearly, schedules of $\mathit{M}$ and $\mathit{M}^{\prime}$ can be related: A
schedule $\pi$ of $\mathit{M}$ amounts to the schedule $\pi^{\prime}$ of
$\mathit{M}^{\prime}$ where we replace we replace each occurrence
$(\beta,\bm{m}_{i})$ with $(\beta/\alpha_{i},\bm{m}^{\prime}_{i})$. Thus, for
every $\bm{y},\bm{y}^{\prime}$, we have
$\bm{y}\xrightarrow{}^{\pi}\bm{y}^{\prime}$ iff
$\bm{y}\xrightarrow{}^{\pi^{\prime}}\bm{y}^{\prime}$.

Let us consider a schedule $\pi$ of $\mathit{M}^{\prime}$, and let
$\rho=\pi[..1]$. It is the case that $\bm{x}\xrightarrow{}^{\rho}\bm{z}$ with

$\bm{z}=\bm{x}+\sum_{i=1}^{n}\lambda_{i}\bm{m}^{\prime}_{i},$

for some $\lambda_{1},\dots,\lambda_{n}$ such that
$\sum_{i=1}^{n}\lambda_{i}=1$. Thus, $\bm{z}$ is a convex combination of the
points $\bm{x}+\bm{m}_{i}^{\prime}$ for any $i\in[1..n]$. But note that
$\bm{x}+\bm{m}_{i}^{\prime}=\bm{x}+\alpha_{i}\bm{m}_{i}$ by definition of
$\mathit{M}^{\prime}$, and $\bm{x}+\alpha_{i}\bm{m}_{i}\in Z$ by definition of
$\alpha_{i}$. So, $\bm{z}$ is a convex combination of points from $Z$, and is
thus included in $Z$, as it is convex.

  3. 3.

The proof for ${\textsf{G}}{\textsf{F}}\neg Z$ is as in Item 1, except that it
remains to note that once an execution has left $Z$ by scheduling $\bm{m}$, if
it keeps scheduling $\bm{m}$, then it will not re-enter $Z$.

  4. 4.

The proof for ${\textsf{F}}{\textsf{G}}\neg Z$ is as in Item 3. ∎

See 3

###### Proof:

_Fragment $\text{LTL}_{\text{B}}$($\\{{\textsf{F}}\\}$)_. We reduce from
linear programming feasibility. This problem asks whether a given zone
$Z\subseteq\mathbb{R}^{d}$, described by a system of inequalities
$\mathbf{A}\bm{x}\leq\bm{b}$, has a non-negative solution. The problem is
P-complete even if zone $Z$ is bounded [23, Prob. A.4.1]. Let
$\mathit{M}\coloneqq\\{\bm{e}_{i}:i\in[1..d]\\}$. It is readily seen that
$Z\neq\emptyset$ iff $\bm{0}\models_{\mathit{M}}{\textsf{F}}Z$.

_Fragment $\text{LTL}_{\text{B}}$($\\{{\textsf{G}}\\}$)_. We reduce from the
monotone circuit-value problem (CVP) [23, Prob. A.1.3]. Let
$C(x_{1},\ldots,x_{n})$ be a boolean circuit with gates from
$\\{\land,\lor\\}$, and let $w_{1},\ldots,\allowbreak
w_{n}\allowbreak\in\allowbreak\\{0,1\\}$. We construct a $d$-dimensional MMS
$\mathit{M}$, $\bm{x}\in\mathbb{R}^{d}$ and a bounded zone
$Z\subseteq\mathbb{R}^{d}$ such that $C(w)=1$ iff
$\bm{x}\models_{\mathit{M}}{\textsf{G}}Z$.

Each gate $g$ is associated to a dimension $g$. We add two dimensions
$\\{\heartsuit,\overline{\heartsuit}\\}$. Let
$\bm{x}\coloneqq\bm{e}_{\heartsuit}+\sum_{i=1}^{n}w_{i}\cdot\bm{e}_{x_{i}}$.
Let $Z$ be the zone defined by $c\in[0,1]$ for every dimension $c$.

We denote as $g_{\text{out}}$ the output gate of $C$. We associate a mode
$\bm{m}_{g}$, to each gate $g=u\land v$, defined by
$\bm{m}_{g}\coloneqq-\bm{e}_{u}-\bm{e}_{v}+\bm{e}_{g}$. We associate the modes
$\bm{m}_{g}$ and $\bm{m}_{g}^{\prime}$ to each gate $g=u\lor v$, defined by
$\bm{m}_{g}\coloneqq-\bm{e}_{u}+\bm{e}_{g}$ and
$\bm{m}_{g}\coloneqq-\bm{e}_{v}+\bm{e}_{g}$. We add two modes:
$\bm{m}_{\heartsuit}\coloneqq-\bm{e}_{g_{\text{out}}}-\bm{e}_{\heartsuit}+\bm{e}_{\overline{\heartsuit}}$
and
$\bm{m}_{\overline{\heartsuit}}\coloneqq\bm{e}_{g_{\text{out}}}+\bm{e}_{\heartsuit}-\bm{e}_{\overline{\heartsuit}}$.

Let $g_{1},\ldots,g_{m}$ be a topological ordering of the gates of $C$. Let
$C_{j}$ be the subcircuit obtained by setting $g_{j}$ as the output gate. A
routine induction shows that $C_{j}(w)=1$ iff there exists $\bm{y}$ such that
$\bm{x}\xrightarrow{}^{*}_{Z}\bm{y}$ and $\bm{y}(g_{j})>0$. The claim implies
that $C(w)=1$ iff $\bm{x}\models_{\mathit{M}}{\textsf{G}}Z$. Indeed, any non-
Zeno infinite schedule must use $\bm{m}_{\heartsuit}$. Moreover, upon reaching
some $\bm{y}$ such that $\bm{y}(g_{\text{out}})=\alpha>0$, it is possible to
alternate between $\alpha\bm{m}_{\heartsuit}$ and
$\alpha\bm{m}_{\overline{\heartsuit}}$ indefinitely. ∎

##  Appendix D Missing proofs of Section IV-B

Proposition 10 follows inductively from this lemma:

###### Lemma 8

Let $\rho(\alpha,\bm{m})\rho^{\prime}(\beta,\bm{m})\rho^{\prime\prime}$ be a
schedule. This holds:

  * •

If
$\bm{x}\xrightarrow{}^{\rho(\alpha,\bm{m})\rho^{\prime}(\beta,\bm{m})\rho^{\prime\prime}}_{Z}\bm{y}$,
then
$\bm{x}\xrightarrow{}^{\rho\,(\alpha,\bm{m})\,\frac{\alpha}{\alpha+\beta}[\rho^{\prime}\rho^{\prime\prime}]}_{Z}{}$,

  * •

If
$\bm{x}\xrightarrow{}^{\rho^{\prime\prime}(\beta,\bm{m})\rho^{\prime}(\alpha,\bm{m})\rho}_{Z}\bm{y}$,
then
${}\xrightarrow{}^{\frac{\alpha}{\alpha+\beta}[\rho^{\prime\prime}\rho^{\prime}]\,(\alpha,\bm{m})\,\rho}_{Z}\bm{y}$.

###### Proof:

We only prove the first item. The second follows symmetrically. We have
$\bm{x}\xrightarrow{}^{\rho}_{Z}\bm{u}$ for some $\bm{u}$. By convexity, there
exist $\bm{v},\bm{v}^{\prime},\bm{w}$ such that:

$\bm{u}\xrightarrow{}^{\frac{\alpha}{\alpha+\beta}[(\alpha,\bm{m})\rho^{\prime}(\beta,\bm{m})]}_{Z}\bm{v}\xrightarrow{}^{\frac{\alpha}{\alpha+\beta}\rho^{\prime\prime}}_{Z}\bm{w}$

and

$\bm{u}\xrightarrow{}^{(\alpha,\bm{m})\frac{\alpha}{\alpha+\beta}\rho^{\prime}}_{Z}\bm{v}^{\prime}.$

Let us show that $\bm{v}=\bm{v}^{\prime}$:

$\displaystyle\bm{v}$
$\displaystyle=\bm{u}+\frac{\alpha}{\alpha+\beta}\left(\alpha\bm{m}+\bm{\Delta}_{\rho^{\prime}}+\beta\bm{m}\right)$
$\displaystyle=\bm{u}+\frac{\alpha}{\alpha+\beta}\left((\alpha+\beta)\bm{m}+\bm{\Delta}_{\rho^{\prime}}\right)$
$\displaystyle=\bm{u}+\alpha\bm{m}+\frac{\alpha}{\alpha+\beta}\bm{\Delta}_{\rho^{\prime}}$
$\displaystyle=\bm{v}^{\prime}.$

From this, we get
$\bm{x}\xrightarrow{}^{\rho}_{Z}\bm{u}\xrightarrow{}^{(\alpha,\bm{m})\frac{\alpha}{\alpha+\beta}\rho^{\prime}}_{Z}\bm{v}\xrightarrow{}^{\frac{\alpha}{\alpha+\beta}\rho^{\prime\prime}}_{Z}\bm{w}$.
∎

See 2

###### Proof:

We only prove the first item. The second follows symmetrically. By convexity,
there exist $\bm{y}^{\prime}$ and $\bm{w}$ such that

$\bm{x}\xrightarrow{}^{\rho(\frac{\alpha}{2},\bm{m})\frac{1}{2}\rho^{\prime}}_{Z}\bm{y^{\prime}}\text{
and
}\bm{x}\xrightarrow{}^{\rho(\alpha,\bm{m})\frac{1}{2}\rho^{\prime}}_{Z}\bm{w}.$

Moreover, we have
$\bm{y^{\prime}}\xrightarrow{}^{(\frac{\alpha}{2},\bm{m})}\bm{w}$. Since
$\bm{y}^{\prime},\bm{w}\in Z$, by convexity, we conclude that

$\bm{x}\xrightarrow{}^{\rho(\frac{\alpha}{2},\bm{m})\frac{1}{2}\rho^{\prime}}_{Z}\bm{y^{\prime}}\xrightarrow{}^{(\frac{\alpha}{2},\bm{m})}_{Z}\bm{w}.$

See 11

###### Proof:

By Lemma 2, we can pick

$\pi^{\prime}\coloneqq\prod_{i=1}^{|\pi|}\left(\frac{1}{2^{i}}\cdot\pi(i)\right),\
\pi^{\prime\prime}\coloneqq\prod_{i=1}^{|\pi|}\left(\frac{1}{2^{(|\pi|-i+1)}}\cdot\pi(i)\right),$

and $\beta\coloneqq 2^{|\pi|}\cdot\lceil\mathrm{time}({\pi})\rceil$. ∎

See 12

###### Proof:

Let
$\pi\coloneqq(\alpha_{1},\bm{m}_{1})(\alpha_{2},\bm{m}_{2})\cdots(\alpha_{k},\bm{m}_{k})$.
Let $\bm{x}^{0}_{0}\coloneqq\bm{x}$, $\bm{x}^{k}_{\beta k-1}\coloneqq\bm{y}$
and $\bm{x}^{k}_{j}\coloneqq\bm{x}^{0}_{j+1}$. Let

$\displaystyle\bm{x}^{i}_{j}$
$\displaystyle\coloneqq\bm{x}^{0}_{0}+j\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta
k}+\sum_{h=1}^{i}\frac{\alpha_{h}\bm{m}_{h}}{\beta k}$
$\displaystyle=\bm{x}^{i}_{0}+\sum_{h=i+1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta
k}+(j-1)\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta
k}+\sum_{h=1}^{i}\frac{\alpha_{h}\bm{m}_{h}}{\beta k}$
$\displaystyle=\bm{x}^{i}_{0}+\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta
k}+(j-1)\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta k}$
$\displaystyle=\bm{x}^{i}_{0}+j\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta
k}.$

Let $\mathbf{A}\bm{\ell}\leq\bm{b}$ be the system of inequalities that
represents zone $Z$. By assumption, the following holds for all $i\in[1..k]$:

$\mathbf{A}\left(\bm{x}^{0}_{0}+\frac{\alpha_{i}\bm{m}_{i}}{\beta}\right)\leq\bm{b}\text{
and }\mathbf{A}\left(\bm{x}^{k}_{\beta
k-1}-\frac{\alpha_{i}\bm{m}_{i}}{\beta}\right)\leq\bm{b}.$

The following holds:

$\bm{x}^{0}_{0}\xrightarrow{}^{\frac{1}{\beta
k}\pi(1)}_{Z}\bm{x}^{1}_{0}\xrightarrow{}^{\frac{1}{\beta
k}\pi(2)}_{Z}\bm{x}^{2}_{0}\xrightarrow{}^{\frac{1}{\beta
k}\pi(3)}_{Z}\cdots\xrightarrow{}^{\frac{1}{\beta
k}\pi(k)}_{Z}\bm{x}^{k}_{0},$

since

$\displaystyle\mathbf{A}\bm{x}^{i}_{0}$
$\displaystyle=\mathbf{A}\bm{x}^{0}_{0}+\sum_{j=1}^{i}\mathbf{A}\frac{\alpha_{j}\bm{m}_{j}}{\beta
k}$
$\displaystyle=\frac{k-i}{k}\mathbf{A}\bm{x}^{0}_{0}+\frac{i}{k}\mathbf{A}\bm{x}^{0}_{0}+\frac{1}{k}\sum_{j=1}^{i}\mathbf{A}\frac{\alpha_{j}\bm{m}_{j}}{\beta}$
$\displaystyle=\frac{k-i}{k}\mathbf{A}\bm{x}^{0}_{0}+\frac{1}{k}\sum_{j=1}^{i}\mathbf{A}\left(\bm{x}^{0}_{0}+\frac{\alpha_{j}\bm{m}_{j}}{\beta}\right)$
$\displaystyle\leq\frac{k-i}{k}\bm{b}+\frac{1}{k}\bm{b}$
$\displaystyle=\bm{b}.$

Similarly, the following holds:

$\displaystyle\bm{x}^{0}_{\beta k-1}\xrightarrow{}^{\frac{1}{\beta
k}\pi(1)}_{Z}\bm{x}^{1}_{\beta k-1}$
$\displaystyle\xrightarrow{}^{\frac{1}{\beta k}\pi(2)}_{Z}\bm{x}^{2}_{\beta
k-1}\cdots\xrightarrow{}^{\frac{1}{\beta k}\pi(k)}_{Z}\bm{x}^{k}_{\beta k-1}.$

It remains to show that, for all $i\in[1..k]$, $j\in[1..(\beta k-1)]$, we have
$\bm{x}^{i}_{j}=(1-\lambda)\bm{x}^{i}_{0}+\lambda\bm{x}^{i}_{\beta k-1}$ where
$\lambda=\frac{j}{\beta k-1}$.

We have:

$\displaystyle\bm{x}^{i}_{j}$
$\displaystyle=\bm{x}^{i}_{0}+j\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta
k}$ $\displaystyle=\bm{x}^{i}_{0}+\frac{\beta k-1}{\beta k-1}\cdot
j\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta k}$
$\displaystyle=\bm{x}^{i}_{0}+\lambda(\beta
k-1)\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta k}$
$\displaystyle=(1-\lambda)\bm{x}^{i}_{0}+\lambda\left(\bm{x}^{i}_{0}+(\beta
k-1)\sum_{h=1}^{k}\frac{\alpha_{h}\bm{m}_{h}}{\beta k}\right)$
$\displaystyle=(1-\lambda)\bm{x}^{i}_{0}+\lambda\bm{x}^{i}_{\beta k-1}.$

Since $\lambda\in[0,1]$, each $\bm{x}^{i}_{j}$ belongs to $Z$ by convexity. ∎

##  Appendix E Missing proofs of Section IV-C

See 15

###### Proof:

Let us prove the case where $\pi=\alpha m$ for some $\alpha\in\mathbb{R}_{>0}$
and mode $\bm{m}\in\mathit{M}$. The general case follows by induction. Note
that $\bm{x}^{\prime}=\bm{x}+\alpha\bm{m}$ and $\bm{x^{\prime}}\in Z$. Let
$\bm{z}^{\prime}\coloneqq\bm{z}+\beta\alpha\bm{m}$. We clearly have
$\bm{z}\xrightarrow{}^{\beta\pi}\bm{z}^{\prime}$. It remains to show that
$\bm{z}\xrightarrow{}^{\beta\pi}_{Z}\bm{z}^{\prime}$. By convexity of $Z$, it
suffices to show that $\bm{z}^{\prime}$ is on the line passing through
$\bm{x}^{\prime}\in Z$ and $\bm{y}\in Z$:

$\displaystyle\bm{z}^{\prime}$
$\displaystyle=(\beta\bm{x}+(1-\beta)\bm{y})+\beta\alpha\bm{m}$
$\displaystyle=\beta(\bm{x}+\alpha\bm{m})+(1-\beta)\bm{y}$
$\displaystyle=\beta\bm{x}^{\prime}+(1-\beta)\bm{y}.$ ∎

Within the proof of Proposition 16, we have claimed that
$f(\bm{x},\bm{y})\geq\lambda$. Let us prove this.

###### Proof:

We first make two additional claims. Given $\bm{x}\in X^{\prime}$ and
$\bm{y}\in Y^{\prime}$ such that
$\bm{z}\xrightarrow{}^{\pi}\bm{x}\xrightarrow{}^{\pi^{\prime}}\bm{y}$, it is
the case that:

  1. 1.

$f^{\prime}(\bm{x},\bm{y})\geq\lambda$, and

  2. 2.

$f^{\prime}(\bm{x},\bm{y})\leq\bm{v}_{3}^{T}(\bm{y}-\bm{x})$.

To prove Claim 1, note that we have

$\displaystyle f^{\prime}(\bm{x},\bm{y})$ $\displaystyle=\ $
$\displaystyle-(\bm{v}_{1}^{T}\mathbf{A}_{1}(\bm{x}-\bm{z})+\bm{v}_{2}^{T}\mathbf{A}_{2}(\bm{y}-\bm{z}))+{}$
$\displaystyle\hskip
20.0pt\bm{v}_{2}^{T}\mathbf{A}_{2}(\bm{y}-\bm{x})+\bm{v}_{3}^{T}(\bm{y}-\bm{x})$
$\displaystyle=\ $
$\displaystyle-(\bm{v}_{1}^{T}\mathbf{A}_{1}(\bm{x}-\bm{z})+\bm{v}_{2}^{T}\mathbf{A}_{2}(\bm{y}-\bm{z}))+{}\quad$
$\displaystyle\hskip
20.0pt(\bm{v}_{2}^{T}\mathbf{A}_{2}\mathbf{M}+\bm{v}_{3}^{T}\mathbf{M})\bm{\pi^{\prime}}$
$\displaystyle\geq\ $
$\displaystyle-(\bm{v}_{1}^{T}\mathbf{A}_{1}(\bm{x}-\bm{z})+\bm{v}_{2}^{T}\mathbf{A}_{2}(\bm{y}-\bm{z}))$
(by (2)) $\displaystyle\geq\ $
$\displaystyle-(\bm{v}_{1}^{T}(\bm{b}_{1}-\mathbf{A}_{1}\bm{z})+\bm{v}_{2}^{T}(\bm{b}_{2}-\mathbf{A}_{2}\bm{z}))$
(by $\bm{x}\in X^{\prime},\bm{y}\in Y^{\prime}$) $\displaystyle=\ $
$\displaystyle\lambda.$

Next, to prove Claim 2, we have

$\displaystyle f^{\prime}(\bm{x},\bm{y})$ $\displaystyle=\ $
$\displaystyle-(\bm{v}_{1}^{T}\mathbf{A}_{1}(\bm{x}-\bm{z})+\bm{v}_{2}^{T}\mathbf{A}_{2}(\bm{y}-\bm{z}))+{}$
$\displaystyle\hskip
20.0pt\bm{v}_{2}^{T}\mathbf{A}_{2}(\bm{y}-\bm{x})+\bm{v}_{3}^{T}(\bm{y}-\bm{x})$
$\displaystyle=\ $
$\displaystyle-\left(\bm{v}_{1}^{T}\mathbf{A}_{1}(\bm{x}-\bm{z})+\bm{v}_{2}^{T}\mathbf{A}_{2}(\bm{x}-\bm{z})\right)+\bm{v}_{3}^{T}(\bm{y}-\bm{x})$
$\displaystyle=\ $
$\displaystyle-(\bm{v}_{1}^{T}\mathbf{A}_{1}\mathbf{M}+\bm{v}_{2}^{T}\mathbf{A}_{2}\mathbf{M})\bm{\pi}+\bm{v}_{3}^{T}(\bm{y}-\bm{x})$
$\displaystyle\leq\ $ $\displaystyle\bm{v}_{3}^{T}(\bm{y}-\bm{x})$
$\displaystyle\text{(by~{}\eqref{eq:farkas:1})}.$

Finally, by using Claims 2 and 1, we can prove the original claim:
$f(\bm{x},\bm{y})=\bm{v}_{3}^{T}(\bm{y}-\bm{x})\geq
f^{\prime}(\bm{x},\bm{y})\geq\lambda$. ∎

See 18

###### Proof:

By unrolling the definition of $\bm{x}_{n}$ and $\bm{y}_{n}$, we have

$\displaystyle\bm{x}_{n}$ (17) $\displaystyle=\ $
$\displaystyle\bm{x}_{0}+\sum_{i=0}^{n-1}\left(\lambda^{i}\left(\bm{\Delta}_{\pi\pi^{\prime}}+\frac{\bm{\Delta}_{\rho}-\epsilon\bm{\Delta}_{\pi\pi^{\prime}}}{1+\epsilon}\right)+(1-\lambda^{i})\bm{\Delta}_{\rho^{\prime}\rho^{\prime\prime}}\right)$
$\displaystyle=\ $
$\displaystyle\bm{x}_{0}+\sum_{i=0}^{n-1}\left(\lambda^{i}\left(\bm{\Delta}_{\pi\pi^{\prime}}+\frac{\bm{\Delta}_{\rho}-\epsilon\bm{\Delta}_{\pi\pi^{\prime}}}{1+\epsilon}\right)+(1-\lambda^{i})\cdot\bm{0}\right)$
$\displaystyle=\ $
$\displaystyle\bm{x}_{0}+\sum_{i=0}^{n-1}\lambda^{i}\left(\bm{\Delta}_{\pi\pi^{\prime}}+\frac{\bm{\Delta}_{\rho}-\epsilon\bm{\Delta}_{\pi\pi^{\prime}}}{1+\epsilon}\right)$
$\displaystyle=\ $
$\displaystyle\bm{x}_{0}+\frac{\lambda^{n}-1}{\lambda-1}\left(\bm{\Delta}_{\pi\pi^{\prime}}+\frac{\bm{\Delta}_{\rho}-\epsilon\bm{\Delta}_{\pi\pi^{\prime}}}{1+\epsilon}\right)$
(18) $\displaystyle=\ $
$\displaystyle\bm{x}_{0}+\frac{\lambda^{n}-1}{-1/(1+\epsilon)}\left(\bm{\Delta}_{\pi\pi^{\prime}}+\frac{\bm{\Delta}_{\rho}-\epsilon\bm{\Delta}_{\pi\pi^{\prime}}}{1+\epsilon}\right)$
$\displaystyle=\ $
$\displaystyle\bm{x}_{0}-(\lambda^{n}-1)(1+\epsilon)\left(\bm{\Delta}_{\pi\pi^{\prime}}+\frac{\bm{\Delta}_{\rho}-\epsilon\bm{\Delta}_{\pi\pi^{\prime}}}{1+\epsilon}\right)$
$\displaystyle=\ $
$\displaystyle\bm{x}_{0}+(1-\lambda^{n})((1+\epsilon)\bm{\Delta}_{\pi\pi^{\prime}}+\bm{\Delta}_{\rho}-\epsilon\bm{\Delta}_{\pi\pi^{\prime}})$
$\displaystyle=\ $
$\displaystyle\bm{x}_{0}+(1-\lambda^{n})\bm{\Delta}_{\pi\pi^{\prime}\rho}$
$\displaystyle=\ $
$\displaystyle\lambda^{n}\bm{x}_{0}+(1-\lambda^{n})(\bm{x_{0}}+\bm{\Delta}_{\pi\pi^{\prime}\rho})$
$\displaystyle=\ $
$\displaystyle\lambda^{n}\bm{x_{0}}+(1-\lambda^{n})\bm{x}_{f},$

where (18) follows from $\sum_{i=0}^{n-1}x^{n-1}=(x^{n}-1)/(x-1)$.
Furthermore, we have

$\displaystyle\bm{y}_{n}$
$\displaystyle=\bm{x}_{n}+\lambda^{n}\bm{\Delta}_{\pi}+(1-\lambda^{n})\bm{\Delta}_{\rho^{\prime}}$
$\displaystyle=\lambda^{n}\bm{x}_{0}+(1-\lambda^{n})\bm{x}_{f}+\lambda^{n}\bm{\Delta}_{\pi}+(1-\lambda^{n})\bm{\Delta}_{\rho^{\prime}}$
(19)
$\displaystyle=\lambda^{n}(\bm{x}_{0}+\bm{\Delta}_{\pi})+(1-\lambda^{n})(\bm{x}_{f}+\bm{\Delta}_{\rho^{\prime}})$
$\displaystyle=\lambda^{n}\bm{y}_{0}+(1-\lambda^{n})\bm{y}_{f},$

where (19) follows from the fact that
$\bm{x}_{n}=\lambda^{n}\bm{x}_{0}+(1-\lambda^{n})\bm{x}_{f}$ for all
$n\in\mathbb{N}$, as proven above. ∎

##  Appendix F Missing proofs of Section IV-D

See 21

###### Proof:

We define $\mathbf{M}$ as the matrix such that each column is a mode from
$\mathit{M}$. Observe that the following set of constraints $\mathcal{S}$ is
equivalent to
$\exists\pi,\bm{z}^{\prime}:\bm{z}\xrightarrow{}^{\bm{\pi}}\bm{z^{\prime}}\land\mathbf{A}\bm{z^{\prime}}\leq\mathbf{A}\bm{z}\land\lVert\bm{\pi}\rVert\geq
1$:

$\displaystyle\exists\bm{u}\geq\bm{0}:\begin{bmatrix}\mathbf{A}\mathbf{M}\\\
\bm{-1}^{T}\end{bmatrix}\bm{u}\leq\begin{bmatrix}\bm{0}\\\ -1\end{bmatrix}.$

For the sake of contradiction, suppose that $\bm{z}\models{\textsf{G}}Z$ and
that $\mathcal{S}$ has no solution. By Farkas’ lemma, the following system
$\mathcal{S}^{\prime}$ has a solution:

$\displaystyle\exists\bm{v}_{1}\geq\bm{0},v_{2}\geq 0:$
$\displaystyle\begin{bmatrix}\mathbf{M}^{T}\mathbf{A}^{T}&\bm{-1}\end{bmatrix}\begin{bmatrix}\bm{v}_{1}\\\
v_{2}\end{bmatrix}\geq\bm{0},\,\begin{bmatrix}\bm{0}^{T}-1\end{bmatrix}\begin{bmatrix}\bm{v}_{1}\\\
v_{2}\end{bmatrix}<0.$

The latter can be rewritten equivalently as follows:

$\displaystyle\exists\bm{v}_{1}\geq\bm{0},v_{2}\geq
0:\mathbf{M}^{T}\mathbf{A}^{T}\bm{v}_{1}-\bm{1}v_{2}\geq\bm{0},\,-v_{2}<0$
$\displaystyle\iff\ $ $\displaystyle\exists\bm{v}_{1}\geq\bm{0},v_{2}\geq
0:\bm{v}_{1}^{T}\mathbf{A}\mathbf{M}\geq\bm{1}^{T}v_{2},\,v_{2}>0$
$\displaystyle\iff\ $ $\displaystyle\exists\bm{v}_{1}\geq\bm{0},v_{2}\geq
0:\bm{v}_{1}^{T}\mathbf{A}\mathbf{M}\geq\bm{1}^{T}v_{2}>\bm{0}^{T}.$

Since $\bm{z}\models{\textsf{G}}Z$, there exists a non-Zeno infinite schedule
$\pi$ such that $\bm{z}\xrightarrow{}^{\pi}_{Z}{}$. Let $n\in\mathbb{N}$,
$\pi_{n}\coloneqq\pi[..n]$ and
$\bm{z}_{n}\coloneqq\bm{z}+\bm{\Delta}_{\pi_{n}}$. We have $\bm{z}_{n}\in Z$
and hence $\mathbf{A}\bm{z}_{n}\leq\bm{b}$. Thus,

$\displaystyle v_{2}\bm{1}^{T}\bm{\pi_{n}}$
$\displaystyle\leq\bm{v}_{1}^{T}\mathbf{A}\mathbf{M}\bm{\pi_{n}}$
$\displaystyle=\bm{v}_{1}^{T}\mathbf{A}(\bm{z}_{n}-\bm{z})$
$\displaystyle\leq\bm{v}_{1}^{T}(\bm{b}-\mathbf{A}\bm{z}).$ (20)

Since $\pi$ is non-Zeno, we further have
$\lim_{n\to\infty}v_{2}\bm{1}^{T}\bm{\pi_{n}}=\infty$, which contradicts (20).
∎

See 22

###### Proof:

We consider the case case where $\rho=\alpha\bm{m}$. The general case follows
inductively. Since $\bm{z}\xrightarrow{}^{\rho}_{Z}$, we have
$\mathbf{A}\bm{z}+\mathbf{A}\alpha\bm{m}\leq\bm{b}$. Thus,
$\mathbf{A}\bm{z}^{\prime}+\mathbf{A}\alpha\bm{m}\leq\mathbf{A}\bm{z}+\mathbf{A}\alpha\bm{m}\leq\bm{b}$.
∎

##  Appendix G Missing proofs of Section IV-E

###### Proof:

$\Rightarrow)$ Let $\pi$ be a non-Zeno infinite schedule that satisfies
$\mathrm{exec}(\pi,\bm{x})\models\varphi$. We construct a non-Zeno infinite
schedule $\pi^{\prime}$ such that
$\mathrm{exec}(\pi^{\prime},(\bm{x},\ldots,\bm{x}))\models\varphi^{\prime}$.
By definition of $\varphi$, for each $i\in[1..n]$, there exist
$\tau_{i,0}<\tau_{i,1}<\cdots\in\mathbb{R}_{\geq 0}$ and
$\bm{x}_{i,0},\bm{x}_{i,1},\ldots\in\mathbb{R}^{d}$ such that $\tau_{i,0}=0$,
$\bm{x}_{i,0}=\bm{x}$ and

$\displaystyle\bm{x}_{i,j}\xrightarrow{}^{\pi[\tau_{i,j}..\tau_{i,j+1}]}_{Z_{0}}\bm{x}_{i,j+1}\in
Z_{i}$ $\displaystyle\text{ for all }j\in\mathbb{N}.$

Without loss of generality, we may assume that
$\tau_{i,j}\leq\tau_{1,j}\leq\tau_{i,j+1}$ for all $i\in[1..n]$ and
$j\in\mathbb{N}$. Indeed, the values can be chosen this way since each zone
$Z_{i}$ is visited infinitely often.

Let $\pi_{i}$ denote the schedule obtained from $\pi$ by replacing each mode
$\bm{m}\in\mathit{M}$ with $\bm{m}_{i}\in\mathit{M}^{\prime}$. Let
$\pi^{\prime}\coloneqq u_{0}v_{0}u_{1}v_{1}\cdots$ be the infinite schedule,
where

$\displaystyle u_{j}$ $\displaystyle\coloneqq\ $
$\displaystyle\pi_{1}[\tau_{1,j}..\tau_{1,j+1}]$
$\displaystyle\pi_{2}[\tau_{1,j}..\tau_{2,j+1}]$
$\displaystyle\cdots\pi_{n}[\tau_{1,j}..\tau_{n,j+1}],$ $\displaystyle v_{j}$
$\displaystyle\coloneqq\ $ $\displaystyle\pi_{1}[\tau_{1,j+1}..\tau_{1,j+1}]$
$\displaystyle\pi_{2}[\tau_{2,j+1}..\tau_{1,j+1}]$
$\displaystyle\cdots\pi_{n}[\tau_{n,j+1}..\tau_{1,j+1}].$

By definition, we have

$\displaystyle(\bm{x},\ldots,\bm{x})$
$\displaystyle\xrightarrow{}^{u_{0}}_{Z}(\bm{x}_{1,1},\ldots,\bm{x}_{n,1})$
$\displaystyle\in X$
$\displaystyle\xrightarrow{}^{v_{0}}_{Z}(\bm{x}_{1,1},\ldots,\bm{x}_{1,1})$
$\displaystyle\in Y$
$\displaystyle\xrightarrow{}^{u_{1}}_{Z}(\bm{x}_{1,2},\ldots,\bm{x}_{n,2})$
$\displaystyle\in X$
$\displaystyle\xrightarrow{}^{v_{1}}_{Z}(\bm{x}_{1,2},\ldots,\bm{x}_{1,2})$
$\displaystyle\in Y$ $\displaystyle\xrightarrow{}^{u_{2}}_{Z}\cdots.$

Thus, it follows that
$(\bm{x},\ldots,\bm{x})\models_{\mathit{M}^{\prime}}\varphi^{\prime}$.

$\Leftarrow)$ Let $\pi^{\prime}$ be a non-Zeno infinite schedule that
satisfies
$\mathrm{exec}(\pi^{\prime},(\bm{x},\ldots,\bm{x}))\models\varphi^{\prime}$.
There exist
$0=\tau_{0}<\gamma_{1}<\tau_{1}<\gamma_{2}<\tau_{2}<\cdots\in\mathbb{R}_{\geq
0}$ and $\bm{x}_{1},\bm{y}_{1},\bm{x}_{2},\bm{y}_{2},\ldots\in\mathbb{R}^{nd}$
such that

$\displaystyle(\bm{x},\ldots,\bm{x})$
$\displaystyle\xrightarrow{}^{\pi^{\prime}[\tau_{0}..\gamma_{1}]}_{Z}\bm{x}_{1}$
$\displaystyle\in X$
$\displaystyle\xrightarrow{}^{\pi^{\prime}[\gamma_{1}..\tau_{1}]}_{Z}\bm{y}_{1}$
$\displaystyle\in Y$
$\displaystyle\xrightarrow{}^{\pi^{\prime}[\tau_{1}..\gamma_{2}]}_{Z}\bm{x}_{2}$
$\displaystyle\in X$
$\displaystyle\xrightarrow{}^{\pi^{\prime}[\gamma_{2}..\tau_{2}]}_{Z}\bm{y}_{2}$
$\displaystyle\in Y$
$\displaystyle\xrightarrow{}^{\pi^{\prime}[\tau_{2}..\gamma_{3}]}_{Z}\cdots$

For every $i\in[1..n]$, let $\pi^{\prime}_{i}$ denote the schedule obtained
from $\pi^{\prime}$ by keeping only the modes from
$\\{\bm{m}_{i}:\bm{m}\in\mathit{M}\\}$, and changing each occurrence of
$\bm{m}_{i}$ to $\bm{m}$. Let

$\displaystyle\pi$ $\displaystyle\coloneqq\ $
$\displaystyle\pi_{1}[\tau_{0}..\gamma_{1}]\ \pi_{1}[\gamma_{1}..\tau_{1}]$
$\displaystyle\pi_{2}[\tau_{1}..\gamma_{2}]\ \pi_{2}[\gamma_{2}..\tau_{2}]$
$\displaystyle\cdots$ $\displaystyle\pi_{n}[\tau_{n-1}..\gamma_{n}]\
\pi_{n}[\gamma_{n}..\tau_{n}]$ $\displaystyle\pi_{1}[\tau_{n}..\gamma_{n+1}]\
\pi_{1}[\gamma_{n+1}..\tau_{n+1}]$ $\displaystyle\cdots$

Recall that $\bm{y}_{j}[i]=\bm{y}_{j}[i^{\prime}]$ for all
$i,i^{\prime}\in[1..n]$. So, by definition, we have

$\displaystyle\bm{x}$
$\displaystyle\xrightarrow{}^{\pi_{1}[\tau_{0}..\gamma_{1}]}_{Z_{0}}\ $
$\displaystyle\bm{x}_{1}[1]\ $
$\displaystyle\xrightarrow{}^{\pi_{1}[\gamma_{1}..\tau_{1}]}_{Z_{0}}\ $
$\displaystyle\bm{y}_{1}[1]\ $ $\displaystyle=\bm{y}_{1}[2]$
$\displaystyle\xrightarrow{}^{\pi_{2}[\tau_{1}..\gamma_{2}]}_{Z_{0}}\ $
$\displaystyle\bm{x}_{2}[2]\ $
$\displaystyle\xrightarrow{}^{\pi_{2}[\gamma_{2}..\tau_{2}]}_{Z_{0}}\ $
$\displaystyle\bm{y}_{2}[2]\ $ $\displaystyle=\bm{y}_{2}[3]$
$\displaystyle\cdots$ $\displaystyle\cdots$
$\displaystyle\xrightarrow{}^{\pi_{n}[\tau_{n-1}..\gamma_{n}]}_{Z_{0}}\ $
$\displaystyle\bm{x}_{n}[n]\ $
$\displaystyle\xrightarrow{}^{\pi_{n}[\gamma_{n}..\tau_{n}]}_{Z_{0}}\ $
$\displaystyle\bm{y}_{n}[n]\ $ $\displaystyle=\bm{y}_{n}[1]$
$\displaystyle\xrightarrow{}^{\pi_{1}[\tau_{n}..\gamma_{n+1}]}_{Z_{0}}\ $
$\displaystyle\bm{x}_{n+1}[1]\ $
$\displaystyle\xrightarrow{}^{\pi_{1}[\gamma_{n+1}..\tau_{n+1}]}_{Z_{0}}\ $
$\displaystyle\bm{y}_{n+1}[1]\ $ $\displaystyle=\bm{y}_{n+1}[2]$
$\displaystyle\cdots$ $\displaystyle\cdots$

Recall that $\bm{x}_{j}[i]\in Z_{i}$ for all $i\in[1..n]$ and
$j\in\mathbb{N}$. Thus, each zone $Z_{i}$ is visited infinitely often, and so
$\mathrm{exec}(\pi,\bm{x})\models\varphi$. ∎

##  Appendix H Missing proofs of Section V

###### Proof:

Let us show that $\bm{0}\models_{\mathit{M}}\varphi$ iff there is a solution
$V$ to the SUBSET-SUM instance $(S,t)$. Recall that
$\bm{0}\models_{\mathit{M}}\varphi$ holds iff $\mathit{M}$ has a non-Zeno
infinite schedule $\pi$ such that $\mathrm{exec}(\pi,\bm{0})\models\varphi$.

$\Leftarrow)$ Let $V\subseteq S$ be such that $\sum_{v\in V}v=t$. We define a
schedule $\pi$ that satisfies $\varphi$. Let
$\pi\coloneqq\pi_{1}\pi_{2}\cdots\pi_{n}\,\bm{y}_{1}^{\omega}$, where

$\pi_{i}\coloneqq\begin{cases}\bm{y}_{i}\,\overline{\bm{y}}_{i}&\text{if
}s_{i}\in V,\\\
\bm{n}_{i}\,\overline{\bm{n}}_{i}&\text{otherwise}.\end{cases}$

$\Rightarrow)$ Let $\pi$ be such that
$\sigma\coloneqq\mathrm{exec}(\pi,\bm{0})\models\varphi$. By definition of
$\varphi$, there exist
$\tau_{T},\tau_{Y_{1}},\tau_{N_{1}},\ldots,\tau_{Y_{n}},\tau_{N_{n}}\in\mathbb{R}_{\geq
0}$ such that $\sigma(\tau_{T})\in T$, $\sigma(\tau_{Y_{i}})\in Y_{i}$ and
$\sigma(\tau_{N_{i}})\in N_{i}$ for all $i\in[1..n]$. Let all of these be
minimal.

Let $\sigma^{\prime}\coloneqq\sigma[0..\tau_{T}]$. Since $\pi$ is a schedule
for $\sigma$, there exists a schedule $\pi^{\prime}$ such that
$\sigma^{\prime}=\mathrm{exec}(\pi^{\prime},\bm{0})$. We will show that:

$\displaystyle\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime}),\mathrm{time}_{\bm{n}_{i}}(\pi^{\prime})\in\\{0,1\\}\text{
for all }i\in[1..n].$ (*)

From (* ‣ H), we can finish the proof. Indeed, by definition of $\pi^{\prime}$
and of the modes, we have

$\sigma(\tau_{T})(c^{*})=\sum_{i=1}^{n}\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime})\cdot
s_{i}.$

Additionally, $\sigma(\tau_{T})(c^{*})=t$ holds by definition of zone $T$.
Since each $\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime})\in\\{0,1\\}$, we obtain a
solution
$V\coloneqq\\{s_{i}\colon\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime})=1\\}$ to the
SUBSET-SUM instance.

It remains to show (* ‣ H). We first make the following claims for every
$i\in[1..n]$:

  1. (1)

$\tau_{Y_{i}}\leq\tau_{T}$ and $\tau_{N_{i}}\leq\tau_{T}$.

  2. (2)

$\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime})+\mathrm{time}_{\bm{n}_{i}}(\pi^{\prime})=1$
and

  3. $\mathrm{time}_{\overline{\bm{y}}_{i}}(\pi^{\prime})+\mathrm{time}_{\overline{\bm{n}}_{i}}(\pi^{\prime})=1$.

Let us prove these two claims.

  1. (1)

We only show that $\tau_{Y_{i}}\leq\tau_{T}$, as $\tau_{N_{i}}\leq\tau_{T}$ is
symmetric. We proceed by proving that for any $\bm{x}\in T\setminus Y_{i}$, it
is the case that $\bm{x}\not\models_{\mathit{M}}{\textsf{F}}Y_{i}$. By
definition of $T$ and $Y_{i}$, we have $\bm{x}(c_{i,1})\in[-0.5,0.5)$,
$\bm{x}(c_{i,2})=2$ and $\bm{x}(c_{i,3})=\bm{x}(c_{i,4})=1$. Note that the
only modes affecting $\\{c_{i,1},\ldots,c_{i,4}\\}$ are
$\\{\bm{y}_{i},\bm{n}_{i},\overline{\bm{y}}_{i},\overline{\bm{n}}_{i}\\}$. The
only modes affecting $c_{i,1}$ positively, and that could thus lead it to
$0.5$, are $\bm{y}_{i}$ and $\overline{\bm{n}}_{i}$. However, both affect
$c_{i,2}$ positively, and no mode decreases $c_{i,2}$. Hence, using either
mode from $\bm{x}$ can never lead to a point in $Y_{i}$. Thus,
$\bm{x}\not\models_{\mathit{M}}{\textsf{F}}Y_{i}$.

  2. (2)

By $\sigma(\tau_{T})\in T$, we have $\sigma(\tau_{T})(c_{i,2})=2$. Since
$\bm{y}_{i}(c_{i,2})=\bm{n}_{i}(c_{i,2})=\overline{\bm{y}}_{i}(c_{i,2})=\overline{\bm{n}}_{i}(c_{i,2})=1$,
and since no mode decreases $c_{i,2}$, it is the case that
$\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime})+\mathrm{time}_{\bm{n}_{i}}(\pi^{\prime})+\mathrm{time}_{\overline{\bm{y}}_{i}}(\pi^{\prime})+\mathrm{time}_{\overline{\bm{n}}_{i}}(\pi^{\prime})=2$.
Since $T$ requires $c_{i,3}=1$, and no mode decreases $c_{i,3}$, we have
$\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime})+\mathrm{time}_{\bm{n}_{i}}(\pi^{\prime})=1$.
Similarly, as $T$ requires $c_{i,4}=1$, we have
$\mathrm{time}_{\overline{\bm{y}}_{i}}(\pi^{\prime})+\mathrm{time}_{\overline{\bm{n}}_{i}}(\pi^{\prime})=1$.

It remains to use the above claims to prove (* ‣ H). Note that
$\tau_{Y_{i}}\neq\tau_{N_{i}}$ as the constraints of $Y_{i}$ and $N_{i}$
conflict on $c_{i,1}$. Let us assume that $\tau_{Y_{i}}<\tau_{N_{i}}$ (the
other case is symmetric). Let $\psi$ and $\psi^{\prime}$ be schedules such
that $\mathrm{exec}(\psi,\bm{0})=\sigma[0..\tau_{Y_{i}}]$ and
$\mathrm{exec}(\psi^{\prime},\sigma(\tau_{Y_{i}}))=\sigma[\tau_{Y_{i}}..\tau_{N_{i}}]$.

By definition of $Y_{i}$ and $N_{i}$, we have
$\sigma(\tau_{Y_{i}})(c_{i,3})=1$ and $\sigma(\tau_{N_{i}})(c_{i,3})=1$. Since
no mode decreases $c_{i,3}$, modes $\bm{y}_{i}$ and $\bm{n}_{i}$ are not used
in $\psi^{\prime}$. Further, note that $\sigma(\tau_{Y_{i}})(c_{i,1})=0.5$ and
$\sigma(\tau_{N_{i}})(c_{i,1})=-0.5$. Therefore, it must be the case that

$0.5-\mathrm{time}_{\overline{\bm{y}}_{i}}(\psi^{\prime})+\mathrm{time}_{\overline{\bm{n}}_{i}}(\psi^{\prime})=-0.5.$

Thus,
$\mathrm{time}_{\overline{\bm{y}}_{i}}(\psi^{\prime})-\mathrm{time}_{\overline{\bm{n}}_{i}}(\psi^{\prime})=1$.
As $\psi^{\prime}$ arises from $\pi^{\prime}$, Claim 2 yields

$\mathrm{time}_{\overline{\bm{y}}_{i}}(\psi^{\prime})+\mathrm{time}_{\overline{\bm{n}}_{i}}(\psi^{\prime})\leq
1.$

So, we have $\mathrm{time}_{\overline{\bm{y}}_{i}}(\psi^{\prime})=1$ and
$\mathrm{time}_{\overline{\bm{n}}_{i}}(\psi^{\prime})=0$. From Claim 2, we
further derive
$\mathrm{time}_{\overline{\bm{y}}_{i}}(\psi)=\mathrm{time}_{\overline{\bm{n}}_{i}}(\psi)=0$.

By definition of $Y_{i}$, we have $\sigma(\tau_{Y_{i}})(c_{i,1})=0.5$. Since
$\bm{y}_{i}$ and $\bm{n}_{i}$ are the only modes possibly used in $\psi$ to
change $c_{i,1}$, we have
$\frac{1}{2}\cdot\mathrm{time}_{\bm{y}_{i}}(\psi)-\frac{1}{2}\cdot\mathrm{time}_{\bm{n}_{i}}(\psi)=0.5$.
By Claim (2),

$\mathrm{time}_{\bm{y}_{i}}(\psi^{\prime})+\mathrm{time}_{\bm{n}_{i}}(\psi^{\prime})\leq
1.$

So, we have $\mathrm{time}_{\bm{y}_{i}}(\psi)=1$ and
$\mathrm{time}_{\bm{n}_{i}}(\psi)=0$, which, by Claim (2), yields
$\mathrm{time}_{\bm{y}_{i}}(\pi^{\prime})=1$ and
$\mathrm{time}_{\bm{n}_{i}}(\pi^{\prime})=0$. ∎

##  Appendix I Missing proofs of Section VI

In Section VI, we implicitly assume that Petri nets with inhibitor arcs have
no transition that consumes from, and produces in, the same place. We can make
this assumption without loss of generality. Roughly, it is possible to split a
transition $t$ that consumes and produces in the same place into two
transitions $t_{\text{pre}}$ and $t_{\text{post}}$, while being equivalent
with respect to reachability. We let $t_{\text{pre}}$ consume from the place
and realize the effect of $t$ on all other places, and let $t_{\text{post}}$
produce in the place. We can ensure that when $t_{\text{pre}}$, then
immediately afterwards $t_{\text{post}}$ is fired by adding a new place
$p_{t}$, adding an arc from $t_{\text{pre}}$ to $p_{t}$ and an arc from
$p_{t}$ to $t_{\text{post}}$, and adding an inhibitor arc from $p_{t}$ to all
other transitions, thus preventing any transition other than $t_{\text{post}}$
from being fired until $t_{\text{post}}$ was fired to consume the token from
$p_{t}$.

Now, let us prove the statements from Section VI.

See 4

###### Proof:

Let $\bm{x}_{A},\bm{x}_{A}^{\prime}\in A$ and $\pi$ be as described.

Let $\pi=(\alpha,\bm{m})\pi^{\prime}$. By definition of $A$, we must have
$\bm{m}=\bm{a}_{t}$ for some $t\in T$. Since $\bm{x}_{A}(t_{A})=1$, we have
$\alpha\in(0,1]$. If $\alpha<1$, then zone $A_{t}^{\prime}\setminus A$ is
reached, and the only mode that can be used is $\bm{a}_{t}$. Thus, we can
assume w.l.o.g. that $\alpha=1$. Let
$\bm{x}_{B}\coloneqq\bm{x}_{A}+\bm{a}_{t}$. We have

$\bm{x}_{A}\xrightarrow{}^{\bm{a}_{t}}_{A_{t}^{\prime}}\bm{x}_{B}\text{ and
}\bm{x}_{B}\in B_{t}.$

Let $\pi^{\prime}=(\alpha^{\prime},\bm{m}^{\prime})\pi^{\prime\prime}$. By
definition of $B_{t}$, we have $\bm{m}^{\prime}=\bm{b}_{t}$ or
$\bm{m}^{\prime}=\bm{a}_{s}$ for some $s\neq t$. Since no zone allows for
$t_{B}>0$ and $s_{B}>0$, we must have $\bm{m}^{\prime}=\bm{b}_{t}$. Since
$\bm{x}_{B}(t_{B})=1$, we have $\alpha^{\prime}\in(0,1]$. If
$\alpha^{\prime}<1$, then zone $B_{t}^{\prime}\setminus B_{t}$ is reached,
and, again, the only mode that can be used is $\bm{b}_{t}$. So, we can assume
w.l.o.g. that $\alpha^{\prime}=1$. Let
$\bm{x}_{C}\coloneqq\bm{x}_{B}+\bm{b}_{t}$. We have

$\bm{x}_{B}\xrightarrow{}^{\bm{b}_{t}}_{B_{t}^{\prime}}\bm{x}_{C}\text{ and
}\bm{x}_{C}\in C_{t}.$

Let
$\pi^{\prime\prime}=(\alpha^{\prime\prime},\bm{m}^{\prime\prime})\pi^{\prime\prime\prime}$.
By definition of $C_{t}$, we have $\bm{m}^{\prime\prime}=\bm{c}_{t}$ or
$\bm{m}^{\prime\prime}=\bm{a}_{s}$ for some $s\neq t$. Since no zone allows
for $t_{C}>0$ and $s_{B}>0$, we must have $\bm{m}^{\prime\prime}=\bm{c}_{t}$.
Since $\bm{x}_{C}(t_{C})=1$, we have $\alpha^{\prime\prime}\in(0,1]$. If
$\alpha^{\prime\prime}<1$, then zone $C_{t}^{\prime}\setminus C_{t}$ is
reached, and, again, the only mode that can be used is $\bm{c}_{t}$. So, we
can assume w.l.o.g. that $\alpha^{\prime\prime}=1$. Let
$\bm{y}\coloneqq\bm{x}_{C}+\bm{c}_{t}$. We have

$\bm{x}_{C}\xrightarrow{}^{\bm{c}_{t}}_{C_{t}^{\prime}}\bm{y}\text{ and
}\bm{y}\in A.$

Since execution $\mathrm{exec}(\pi,\bm{x}_{A})$ does not contain intermediate
points in $A$, we have $\bm{y}=\bm{x}_{A}^{\prime}$ and hence
$\pi^{\prime\prime\prime}$ is empty. Consequently,
$\pi\equiv\bm{a}_{t}\bm{b}_{t}\bm{c}_{t}$. ∎

See 25

###### Proof:

We show the proposition with $\mathit{M}$ and $\mathit{AP}$ described above.
Let $\bm{x}$ be the point such that $\bm{x}(t_{A})\coloneqq 1$ for all $t\in
T$, $\bm{x}(\bm{p})\coloneqq\bm{x}_{\text{src}}$, and $\bm{x}(j)\coloneqq 0$
for any other $j$. Let $\bm{x}^{\prime}$ be defined in the same way, but with
$\bm{x}_{\text{tgt}}$ rather than $\bm{x}_{\text{src}}$.

Item 2 follows from the fact that zones from $\mathit{AP}$ are non-negative,
and each mode of $\mathit{M}$ decreases some dimension. It remains to show
that $\bm{x}_{\text{src}}\xrightarrow{}^{+}\bm{x}_{\text{tgt}}$ in
$\mathcal{N}$ iff $\bm{x}\xrightarrow{}^{+}_{\mathit{AP}}\bm{x}^{\prime}$ in
$\mathit{M}$.

$\Rightarrow$) Let
$\bm{x}_{\text{src}}\xrightarrow{}^{\pi}\bm{x}_{\text{tgt}}$ in $\mathcal{N}$,
where $\pi=t_{1}\cdots t_{k}$. Let
$\pi^{\prime}\coloneqq\bm{a}_{t_{1}}\bm{b}_{t_{1}}\bm{c}_{t_{1}}\cdots\bm{a}_{t_{k}}\bm{b}_{t_{k}}\bm{c}_{t_{k}}$.
We have $\bm{x}\xrightarrow{}^{\pi^{\prime}}_{\mathit{AP}}\bm{x}^{\prime}$ in
$\mathit{M}$.

$\Leftarrow$) Let $\bm{x}\xrightarrow{}^{\pi}_{\mathit{AP}}\bm{x}^{\prime}$ in
$\mathit{M}$ where $\pi$ is nonempty. As $\bm{x},\bm{x}^{\prime}\in A$,
repeated applications of Lemma 4 yield $t_{1},\ldots,t_{k}\in T$ and points
$\bm{y}_{A,1}$, $\bm{y}_{B,1}$, $\bm{y}_{C,1}$, $\ldots$, $\bm{y}_{A,k}$,
$\bm{y}_{B,k}$, $\bm{y}_{C,k}$, $\bm{y}_{A,k+1}$ such that
$\pi\equiv\bm{a}_{t_{1}}\bm{b}_{t_{1}}\bm{c}_{t_{1}}\cdots\bm{a}_{t_{k}}\bm{b}_{t_{k}}\bm{c}_{t_{k}}$,
and for all $i\in[1..k]$:

  1. 1.

$\bm{y}_{A,i}\in A$, $\bm{y}_{B,i}\in B_{t_{i}}$ and $\bm{y}_{C,i}\in
C_{t_{i}}$,

  2. 2.

$\bm{y}_{A,1}=\bm{x}$ and $\bm{y}_{A,k+1}=\bm{x}^{\prime}$, and

  3. 3.

$\bm{y}_{A,i}\xrightarrow{}^{\bm{a}_{t_{i}}}_{A_{t_{i}}^{\prime}}\bm{y}_{B,i}\xrightarrow{}^{\bm{b}_{t_{i}}}_{B_{t_{i}}^{\prime}}\bm{y}_{C,i}\xrightarrow{}^{\bm{c}_{t_{i}}}_{C_{t_{i}}^{\prime}}\bm{y}_{A,i+1}$
in $\mathit{M}$.

By definition of the modes and zones, Item 3 yields

$\displaystyle\bm{y}_{A,i}(\bm{p})\xrightarrow{}^{t_{i}}\bm{y}_{A,i+1}(\bm{p})\text{
in }\mathcal{N}$ $\displaystyle\text{for all }i\in[1..k].$

Thus, $\bm{x}_{\text{src}}=\bm{y}_{A,1}(\bm{p})\xrightarrow{}^{t_{1}\cdots
t_{k}}\bm{y}_{A,k+1}(\bm{p})=\bm{x}_{\text{tgt}}$ in $\mathcal{N}$. ∎

See 5

###### Proof:

The two following equivalences hold for LTL formulas interpreted over infinite
words:

  1. 1.

$(\psi\lor\psi^{\prime})\mathrel{\textsf{U}}\varphi\equiv(\psi\mathrel{\textsf{U}}\psi^{\prime})\mathrel{\textsf{U}}((\psi^{\prime}\mathrel{\textsf{U}}\psi)\mathrel{\textsf{U}}\varphi)$,

  2. 2.

$\varphi\mathrel{\textsf{U}}(\psi\lor\psi^{\prime})\equiv(\varphi\mathrel{\textsf{U}}\psi)\lor(\varphi\mathrel{\textsf{U}}\psi^{\prime})$.

By Propositions 1 and 2, these equivalences also hold for negation-free LTL
formulas interpreted over executions.

We proceed by induction on $n$. If $n=1$, then the claim is trivial. Assume
$n\geq 2$. Let $\psi^{\prime}\coloneqq\psi_{2}\lor\cdots\lor\psi_{n}$. We
have:

$\displaystyle(\psi_{1}\lor\psi_{2}\lor\cdots\lor\psi_{n})\mathrel{\textsf{U}}\varphi$
$\displaystyle\equiv\ $
$\displaystyle(\psi_{1}\lor\psi^{\prime})\mathrel{\textsf{U}}\varphi$
$\displaystyle\equiv\ $
$\displaystyle(\psi_{1}\mathrel{\textsf{U}}\psi^{\prime})\mathrel{\textsf{U}}((\psi^{\prime}\mathrel{\textsf{U}}\psi_{1})\mathrel{\textsf{U}}\varphi)$
(21) $\displaystyle\equiv\ $
$\displaystyle(\psi_{1}\mathrel{\textsf{U}}\psi^{\prime})\mathrel{\textsf{U}}(\theta\mathrel{\textsf{U}}\varphi)\quad$
(22) $\displaystyle\equiv\ $
$\displaystyle[(\psi_{1}\mathrel{\textsf{U}}\psi_{2})\lor\cdots\lor(\psi_{1}\mathrel{\textsf{U}}\psi_{n})]\mathrel{\textsf{U}}(\theta\mathrel{\textsf{U}}\varphi)$
(23) $\displaystyle\equiv\ $ $\displaystyle\theta^{\prime},$ (24)

where (21) and (23) follow from Items 1 and 2, and where (22) and (24) yield
$\theta,\theta^{\prime}\in\text{$\text{LTL}_{\text{B}}$($\\{\mathrel{\textsf{U}}\\}$)}$
by induction hypothesis. ∎

See 7

###### Proof:

Let $\mathcal{N}$ be a Petri net with inhibitor arcs and let
$\bm{x}_{\text{src}},\bm{x}_{\text{tgt}}$. Let $\mathit{M}$, $\bm{x}$,
$\bm{x}^{\prime}$ and $\mathit{AP}$ be given by Proposition 24. We modify
$\mathit{M}$ and $\mathit{AP}$ as follows. We add dimension $\heartsuit$ to
indicate that $\bm{x}^{\prime}$ was reached and extend the execution to an
infinite one.

Each mode $\bm{m}\in\mathit{M}$ is extended with $\bm{m}(\heartsuit)\coloneqq
0$. Each zone of $\mathit{AP}$ is extended with the constraint $\heartsuit=0$.
We add modes $\\{\bm{a}_{\heartsuit},\overline{\bm{a}_{\heartsuit}}\\}$ and
zone $A_{\heartsuit}$ defined by:

$\begin{array}[]{lp{2pt}rrr}\hline\cr\hline\cr
j&&\bm{a}_{\heartsuit}(j)&\overline{\bm{a}_{\heartsuit}}(j)\\\
\hline\cr\heartsuit&&1&-1\\\ \text{else}&&0&0\\\
\hline\cr\hline\cr\end{array}\hskip
28.45274pt\begin{array}[]{lp{2pt}lll}\hline\cr\hline\cr&&A_{\heartsuit}\\\
\hline\cr\heartsuit&&\in[0,1]\\\ \textbf{rest}&&=\bm{x}^{\prime}\\\
\hline\cr\hline\cr\end{array}$

Let $\mathit{M}^{\prime}$ and $\mathit{AP}^{\prime}$ be the resulting MMS and
set of zones. Let
$\varphi\coloneqq{\textsf{G}}(\bigvee_{Z\in\mathit{AP}^{\prime}}Z)$. Let
$\bm{y}\coloneqq(0,\bm{x})$. By Proposition 24, it suffices to show that
$\bm{x}\xrightarrow{}^{*}_{\mathit{AP}}\bm{x}^{\prime}$ in $\mathit{M}$ iff
$\bm{y}\models_{\mathit{M}^{\prime}}\varphi$.

$\Rightarrow$) Let $\pi$ be a finite schedule such that
$\bm{x}\xrightarrow{}^{\pi}_{\mathit{AP}}\bm{x}^{\prime}$ in $\mathit{M}$. Let
$\pi^{\prime}\coloneqq\pi\,\bm{a}_{\heartsuit}\,\overline{\bm{a}}_{\heartsuit}\,\bm{a}_{\heartsuit}\,\overline{\bm{a}}_{\heartsuit}\,\cdots$.
We have $\bm{y}\xrightarrow{}^{\pi^{\prime}}_{\mathit{AP}^{\prime}}$ in
$\mathit{M}^{\prime}$, and hence
$\mathrm{exec}(\pi^{\prime},\bm{y})\models_{\mathit{M}^{\prime}}\varphi$,
since $\pi^{\prime}$ is non-Zeno.

$\Leftarrow$) Let $\pi$ be an infinite non-Zeno schedule of
$\mathit{M}^{\prime}$ such that $\mathrm{exec}(\pi,\bm{y})\models\varphi$. Let
$\sigma\coloneqq\mathrm{exec}(\pi,\bm{y})$. By Proposition 24, we have
$\bm{y}\not\xrightarrow{}^{\pi}_{\mathit{AP}^{\prime}\setminus\\{A_{\heartsuit}\\}}$.

So, there exists $\tau\in\mathbb{R}_{\geq 0}$ such that $\sigma(\tau)\in
A_{\heartsuit}$. By definition of $\mathit{M}^{\prime}$, there is a minimal
$\tau^{\prime}\leq\tau$ with $\sigma(\tau^{\prime})=(0,\bm{x}^{\prime})$. Let
$\pi^{\prime}$ be a finite schedule such that
$\mathrm{exec}(\pi^{\prime},\bm{y})=\sigma[0..\tau^{\prime}]$. We have
$\bm{y}\xrightarrow{}^{\pi^{\prime}}_{\mathit{AP}^{\prime}\setminus\\{A_{\heartsuit}\\}}(0,\bm{x}^{\prime})$
in $\mathit{M}^{\prime}$. Hence,
$\bm{x}\xrightarrow{}^{*}_{\mathit{AP}}\bm{x}^{\prime}$ in $\mathit{M}$. ∎