obtained partial order $G_{A|B}^{o}$ is series-parallel from Theorem 6.4 one
will have weak convergence to $\mu_{G_{A|B}}$. This result will allow us in
Corollary 8.7 to compute the Rényi and von Neumann entanglement entropy.

Recall first, that a measure $\mu^{(D)}$ _converges weakly_ to a measure $\mu$
if for any continuous function $f:\mathbb{R}\to\mathbb{R}$ we have:

$\forall\varepsilon>0,\quad\lim_{D\to\infty}\mathbb{P}\left(\left|\int
f(t)\mathrm{d}\mu^{(D)}(t)-\int
f(t)\mathrm{d}\mu(t)\right|\leq\varepsilon\right)=1.$

######  Theorem 8.4.

Let boundary region $A\subseteq E_{\partial}$ in the graph $G$. The empirical
measure $\mu_{A}^{(D)}$ associated to the approximated normalised state
$\sigma_{A}$ converges weakly to $\mu_{G_{A|B}}$. More precisely for all
continuous function $f:\mathbb{R}\to\mathbb{R}$ we have:

$\forall\varepsilon>0,\quad\lim_{D\to\infty}\mathbb{P}\left(\left|\int
f(t)\mathrm{d}\mu^{(D)}_{A}(t)-\int
f(t)\mathrm{d}\mu_{G_{A|B}}(t)\right|\leq\varepsilon\right)=1.$

###### Proof.

As was shown in Theorem 5.14 the moment converges to a unique measure
$\mu_{G_{A|B}}$. In the particular case of an ordered series-parallel graph
$G_{A|B}^{o}$ we have an explicit graph dependent measure $\mu_{G_{A|B}^{o}}$.
Recall from Theorem 5.14 that:

$\frac{1}{D^{F(G_{A|B})}}\mathbb{E}\Big{[}\operatorname{Tr}\left(\sigma_{A}^{n}\right)\Big{]}\xrightarrow[D\to\infty]{}m_{n}=\int
t^{n}\mathrm{d}\mu_{G_{A|B}}(t).$

From standard probability theory results the convergence in probability
implies weak convergence (see [Bil12, Theorem 25.2]. For that one needs only
to show the decreasing scaling of the variance as $D\to\infty$. By using
[Has17, Lemma 14] that:

$\operatorname{Var}\left(\frac{1}{D^{F(G_{A|B})}}\operatorname{Tr}(\sigma_{A}^{n})\right)=O\left(\frac{1}{D}\right),\quad(D\to\infty),$

hence the weak convergence of $\mu_{A}^{(D)}$ to $\mu_{G_{A|B}}$, in
particular if the graph is series-parallel we have $\mu_{G_{A|B}^{o}}$. ∎

######  Lemma 8.5.

Let boundary region $A\subseteq E_{\partial}$ and let $m_{n}^{(D)}$ the moment
associated to the empirical measure $\mu_{A}^{(D)}$ one have:

$\mathbb{P}\Big{(}\Big{|}\mathbb{E}\log\Big{(}m_{n}^{(D)}\Big{)}-\log\Big{(}\mathbb{E}m_{n}^{(D)}\Big{)}\Big{|}>\varepsilon\Big{)}\xrightarrow[D\to\infty]{}1\quad\text{where}\quad
m_{n}^{(D)}:=\frac{1}{D^{F(G_{A|B})}}\mathbb{E}\Big{[}\operatorname{Tr}\left(\sigma_{A}^{n}\right)\Big{]}.$

###### Proof.

By Proposition 8.3 and Jensen’s inequality that
$\mathbb{E}\log\Big{(}m_{n}^{(D)}\Big{)}\leq\log\Big{(}\mathbb{E}m_{n}^{(D)}\Big{)}$.
All what remains to show that
$\mathbb{E}\log\Big{(}m_{n}^{(D)}\Big{)}\geq\log\Big{(}\mathbb{E}m_{n}^{(D)}\Big{)}$
holds with high probability. Fix $\varepsilon>0$. From Proposition 8.3 we know
that

$m_{n}^{(D)}\geq\mathbb{E}m_{n}^{(D)}-\delta\quad\text{with}\quad
0<\delta\leq\frac{\varepsilon}{\varepsilon+1}\mathbb{E}m_{n}^{(D)},$

holds with probability
$1-\exp{\Big{(}-c_{2n|E|}D^{\frac{1}{2n|E|}}\delta^{\frac{1}{n|E|}}\Big{)}}$.
It is easy to check that the following inequalities hold:

$\displaystyle\log\left(m_{n}^{(D)}\right)\geq\log\left(\mathbb{E}m_{n}^{(D)}-\delta\right)$
$\displaystyle=\log\left(\mathbb{E}m_{n}^{(D)}\right)+\log\left(1-\frac{\delta}{\mathbb{E}m_{n}^{(D)}}\right)$
$\displaystyle\geq\log\left(\mathbb{E}m_{n}^{(D)}\right)-\frac{\delta}{\mathbb{E}m_{n}^{(D)}-\delta}\geq\log\left(\mathbb{E}m_{n}^{(D)}\right)-\varepsilon.$

Therefore we have that
$\mathbb{E}\log\left(m_{n}^{(D)}\right)\geq\log\left(\mathbb{E}m_{n}^{(D)}\right)-\varepsilon$
occurs with probability at least

$1-\exp{\Big{(}-c_{2n|E|}D^{\frac{1}{2n|E|}}\delta_{\max}^{\frac{1}{n|E|}}\Big{)}}\quad\text{where}\quad\delta_{\max}=\frac{\varepsilon}{\varepsilon+1}\mathbb{E}m_{n}^{(D)}.$

As $D\to\infty$, $\mathbb{E}m_{n}^{(D)}$ converges, hence
$\delta_{\max}=O(1)$, showing that the probability estimate above converges to
1 and finishing the proof. ∎

We recall for completeness the following proposition from [CN11] which will
play a key role for the proof of our main result.

######  Proposition 8.6.

[CN11, Proposition 4.4] Let $f$ be a continuous function on $\mathbb{R}$ with
polynomial growth and $\nu_{n}$ a sequence of probability measures which
converges in moments to a compactly supported measure $\nu$. Then $\int
f\mathrm{d}\nu_{n}\to\int f\mathrm{d}\nu$.

######  Corollary 8.7.

Let boundary region $A\subseteq E_{\partial}$ in $G$, and let
$\tilde{\rho}_{A}$ the approximated reduced normalised state. Then the
averaged Rényi and von Neumann entropy converges weakly as $D\to\infty$ are
given by:

$\displaystyle F(G_{A|B})\log D-\mathbb{E}S_{n}(\tilde{\rho}_{A})$
$\displaystyle\xrightarrow[D\to\infty]{}\frac{1}{n-1}\log\left(\int
t^{n}\,\mathrm{d}\mu_{G_{A|B}}\right),$ $\displaystyle F(G_{A|B})\log
D-\mathbb{E}S(\tilde{\rho}_{A})$ $\displaystyle\xrightarrow[D\to\infty]{}\int
t\,\log t\,\mathrm{d}\mu_{G_{A|B}}.$

where $F(G_{A|B}):=\operatorname{maxflow}(G_{A|B})$ .

###### Proof.

The poof of this corollary is a direct consequence of different obtained
concentration results from the previous subsection and the weak convergence of
$\mu^{(D)}_{A}$ to $\mu_{G_{A|B}}$.

First, we shall start with the Rényi entropy, for that let consider:

$\displaystyle F(G_{A|B})\log
D-\mathbb{E}S_{n}(\tilde{\rho}_{A})=\frac{1}{1-n}\mathbb{E}\log\left(m_{n,A}^{(D)}\right),\quad\text{where}\quad
m_{n}^{(D)}:=\frac{1}{D^{F(G_{A|B})}}\mathbb{E}\Big{[}\operatorname{Tr}\left(\left(\sigma_{A}\right)^{n}\right)\Big{]},$

and recall that $\sigma_{A}:=D^{F(G_{A|B})}\tilde{\rho}_{A}^{S}$ restricted on
the support of $\tilde{\rho}_{A}:=D^{-|E_{\partial}|}\rho_{A}$. By using Lemma
8.5 and in the limit $D\to\infty$ we have:

$F(G_{A|B})\log
D-\mathbb{E}S_{n}(\tilde{\rho}_{A})\xrightarrow[D\to\infty]{}\frac{1}{n-1}\log\left(\int
t^{n}\,\mathrm{d}\mu_{G_{A|B}}\right).$

For the von Neumann entropy let consider
$\\{\lambda_{i}\\}\in\mathrm{spec}(\sigma_{A})$ and
$\\{\tilde{\lambda}_{i}\\}\in\mathrm{spec}(\tilde{\rho}_{A})$, it is direct
that:

$\mathbb{E}S(\tilde{\rho}_{A})=-\mathbb{E}\sum_{i}\tilde{\lambda}_{i}\log(\tilde{\lambda}_{i})=F(G_{A|B})\log(D)-\frac{1}{D^{F(G_{A|B})}}\mathbb{E}\sum_{i}\lambda_{i}\log(\lambda_{i}).$

Define the function $f:\mathbb{R}\to\mathbb{R}$ as $f(t):=t\log t$, by
combining Proposition 8.6 and Theorem 8.4 we have the following weak
convergence as $D\to\infty$

$F(G_{A|B})\log
D-\mathbb{E}S(\hat{\rho}_{A})=\frac{1}{D^{F(G_{A|B})}}\,\mathbb{E}\left(\sum_{i}\,f(\lambda_{i})\right)\xrightarrow[D\to\infty]{}\int\,f(t)\,\mathrm{d}\mu_{G_{A|B}},$

where the measure $\mu_{G_{A|B}}$ is defined on a compact support, ending the
proof of the corollary. In the particular case if the obtained poset structure
$G_{A|B}^{o}$ is series parallel the obtained graph dependent measure is
explicitly given $\mu_{G_{A|B}}=\mu_{G_{A|B}^{o}}$ by Theorem 6.4. ∎

##  9\. Conclusion

From a given graph general graph with boundary region and bulk region, the
main goal of this work is to compute the entanglement entropy, the Rényi and
the von Neumann entropy, of a given sub-boundary region $A$ of the graph. By
analysing as $D\to\infty$ the moments of a state associated to the region $A$,
with the help of the (maximal) flow approach we computed the leading terms
contribution to the moment. By analysing and removing all the augmenting paths
starting from $\operatorname{id}$ and ending in $\gamma$ of the network
$G_{A|B}$ constructed by connecting the region $A$ to the total cycle $\gamma$
and $\operatorname{id}$ to the region $B$ one obtains a cluster graph
$G_{A|B}^{c}$ by identifying all the remaining edges connected permutations.
The flow approach induces a natural ordering poset structure represented by
the induced poset order $G_{A|B}^{o}$. The maximal flow approach allows us to
deduce the moment convergence to the moment of a unique graph-dependent
measure $\mu_{G_{A|B}}$. This result allows us to deduce the higher order
correction terms of the Rényi and von Neumann entropy given by a graph-
dependent measure $\mu_{G_{A|B}}$. Moreover, we have shown if the obtained
partial order $G_{A|B}^{o}$ is series-parallel, and with the hep of free
probability theory we can explicitly give the associated graph-dependent
measure $\mu_{G_{A|B}}=\mu_{G_{A|B}^{o}}$ that will contribute to the higher
order correction terms of each of the Rényi and von Neumann entanglement
entropy.

In this work, we did not assume any assumption on the minimal cuts, in the
maximal flow approach by duality one can obtain different minimal cuts which
may intersect in different edges. Moreover, the higher-order correction terms
in the entanglement entropy can describe the quantum corrections beyond the
area law behaviour of the expected Ryu-Takayanagi entanglement entropy in the
context of ADS/CFT. It was previously argued in the literature that if one
wants to consider higher-order correction terms in the random tensor network
setting one needs to go beyond the maximally entangled state and consider
general link states representing the bulk matter field. In this work the
obtained higher-order quantum fluctuation of entanglement entropy with only
maximally entangled states that we interpret as fluctuations of spacetime
itself without any need of bulk fields represented by a generic link state.

Acknowledgments. We would like to thank Cécilia Lancien for sharing with us
preliminary notes on very similar questions. The authors were supported by the
ANR projects ESQuisses, grant number ANR-20-CE47-0014-01, and STARS, grant
number ANR-20-CE40-0008, as well as by the PHC program _Star_ (Applications of
random matrix theory and abstract harmonic analysis to quantum information
theory). K.F. acknowledges support from a NanoX project grant.

## References

  * [AGZ10] G.W. Anderson, A. Guionnet, and O. Zeitouni.  An Introduction to Random Matrices.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2010.
  * [AKC22] Harriet Apel, Tamara Kohler, and Toby Cubitt.  Holographic duality between local hamiltonians from random tensor networks.  Journal of High Energy Physics, 2022(3):1–43, 2022.
  * [Arm07] Drew Armstrong.  Generalized noncrossing partitions and combinatorics of coxeter groups, 2007.
  * [BBCC11] Teodor Banica, Serban Teodor Belinschi, Mireille Capitaine, and Benoit Collins.  Free Bessel laws.  Canadian Journal of Mathematics, 63(1):3–37, 2011.
  * [BDGR97] Denis Bechet, Philippe De Groote, and Christian Retoré.  A complete axiomatisation for the inclusion of series-parallel partial orders.  In International Conference on Rewriting Techniques and Applications, pages 230–240. Springer, 1997.
  * [Bil12] P. Billingsley.  Probability and Measure.  Wiley Series in Probability and Statistics. Wiley, 2012.
  * [Bil13] Patrick Billingsley.  Convergence of probability measures.  John Wiley & Sons, 2013.
  * [BPSW19] Ning Bao, Geoffrey Penington, Jonathan Sorce, and Aron C Wall.  Beyond toy models: distilling tensor networks in full ads/cft.  Journal of High Energy Physics, 2019(11):1–63, 2019.
  * [BS10] Zhidong Bai and Jack W Silverstein.  Spectral analysis of large dimensional random matrices, volume 20.  Springer, 2010.
  * [CCW22] Bowen Chen, Bartłomiej Czech, and Zi-Zhi Wang.  Quantum information in holographic duality.  Reports on Progress in Physics, 85(4):046001, 2022.
  * [CGGPG13] Benoît Collins, Carlos E González-Guillén, and David Pérez-García.  Matrix product states, random matrix theory and the principle of maximum entropy.  Communications in Mathematical Physics, 320:663–677, 2013.
  * [CLP+22] Newton Cheng, Cécilia Lancien, Geoff Penington, Michael Walter, and Freek Witteveen.  Random tensor networks with nontrivial links, 2022.
  * [CLP+24] Newton Cheng, Cécilia Lancien, Geoff Penington, Michael Walter, and Freek Witteveen.  Random tensor networks with non-trivial links.  Annales Henri Poincaré, 25(4):2107–2212, 2024.
  * [CN11] Benoît Collins and Ion Nechita.  Gaussianization and eigenvalue statistics for random quantum channels (III).  The Annals of Applied Probability, pages 1136–1179, 2011.
  * [CN16] Benoit Collins and Ion Nechita.  Random matrix techniques in quantum information theory.  Journal of Mathematical Physics, 57(1), 2016.
  * [CNŻ10] Benoît Collins, Ion Nechita, and Karol Życzkowski.  Random graph states, maximal flow and fuss–catalan distributions.  Journal of Physics A: Mathematical and Theoretical, 43(27):275303, 2010.
  * [CNŻ13] Benoît Collins, Ion Nechita, and Karol Życzkowski.  Area law for random graph states.  Journal of Physics A: Mathematical and Theoretical, 46(30):305302, 2013.
  * [CPGSV21] J Ignacio Cirac, David Perez-Garcia, Norbert Schuch, and Frank Verstraete.  Matrix product states and projected entangled pair states: Concepts, symmetries, theorems.  Reviews of Modern Physics, 93(4):045003, 2021.
  * [DQW21] Xi Dong, Xiao-Liang Qi, and Michael Walter.  Holographic entanglement negativity and replica symmetry breaking.  Journal of High Energy Physics, 2021(6):1–41, 2021.
  * [FH17] Michael Freedman and Matthew Headrick.  Bit threads and holographic entanglement.  Communications in Mathematical Physics, 352:407–438, 2017.
  * [FK94] SK Foong and S Kanno.  Proof of page’s conjecture on the average entropy of a subsystem.  Physical review letters, 72(8):1148, 1994.
  * [GGJN18] Carlos E González-Guillén, Marius Junge, and Ion Nechita.  On the spectral gap of random quantum channels.  arXiv preprint arXiv:1811.08847, 2018.
  * [Har13] Aram W. Harrow.  The church of the symmetric subspace, 2013.
  * [Has17] Matthew B Hastings.  The asymptotics of quantum max-flow min-cut.  Communications in Mathematical Physics, 351:387–418, 2017.
  * [HNQ+16] Patrick Hayden, Sepehr Nezami, Xiao-Liang Qi, Nathaniel Thomas, Michael Walter, and Zhao Yang.  Holographic duality from random tensor networks.  Journal of High Energy Physics, 2016(11):1–56, 2016.
  * [KFNR22] Jonah Kudler-Flam, Vladimir Narovlansky, and Shinsei Ryu.  Negativity spectra in random tensor networks and holography.  Journal of High Energy Physics, 2022(2):1–74, 2022.
  * [KVKV11] Bernhard H Korte, Jens Vygen, B Korte, and J Vygen.  Combinatorial optimization, volume 1.  Springer, 2011.
  * [Lan] Cécilia Lancien.  Personal communication.
  * [LC21] Ryan Levy and Bryan K Clark.  Entanglement entropy transitions with random tensor networks.  arXiv preprint arXiv:2108.02225, 2021.
  * [LM13] Aitor Lewkowycz and Juan Maldacena.  Generalized gravitational entropy.  Journal of High Energy Physics, 2013(8):1–29, 2013.
  * [LPG22] Cécilia Lancien and David Pérez-García.  Correlation length in random mps and peps.  In Annales Henri Poincaré, volume 23, pages 141–222. Springer, 2022.
  * [LPWV20] Javier Lopez-Piqueres, Brayden Ware, and Romain Vasseur.  Mean-field entanglement transitions in random tree tensor networks.  Physical Review B, 102(6):064202, 2020.
  * [LVFL21] Yaodong Li, Romain Vasseur, Matthew Fisher, and Andreas WW Ludwig.  Statistical mechanics model for clifford random tensor networks and monitored quantum circuits.  arXiv preprint arXiv:2110.02988, 2021.
  * [Mal99] Juan Maldacena.  The large-n limit of superconformal field theories and supergravity.  International journal of theoretical physics, 38(4):1113–1133, 1999\.
  * [MS17] James A Mingo and Roland Speicher.  Free probability and random matrices, volume 35.  Springer, 2017.
  * [MVS21] Raimel Medina, Romain Vasseur, and Maksym Serbyn.  Entanglement transitions from restricted boltzmann machines.  Physical Review B, 104(10):104205, 2021.
  * [MWW20] Donald Marolf, Shannon Wang, and Zhencheng Wang.  Probing phase transitions of holographic entanglement entropy with fixed area states.  Journal of High Energy Physics, 2020(12):1–41, 2020.
  * [Nec07] Ion Nechita.  Asymptotics of random density matrices.  Annales Henri Poincaré, 8(8):1521–1538, 2007.
  * [NRSR21] Adam Nahum, Sthitadhi Roy, Brian Skinner, and Jonathan Ruhman.  Measurement and entanglement phase transitions in all-to-all quantum circuits, on quantum trees, and in landau-ginsburg theory.  PRX Quantum, 2(1):010352, 2021.
  * [NS06] Alexandru Nica and Roland Speicher.  Lectures on the combinatorics of free probability, volume 13.  Cambridge University Press, 2006.
  * [Pag93] Don N Page.  Average entropy of a subsystem.  Physical review letters, 71(9):1291, 1993.
  * [PSSY22] Geoff Penington, Stephen H Shenker, Douglas Stanford, and Zhenbin Yang.  Replica wormholes and the black hole interior.  Journal of High Energy Physics, 2022(3):1–87, 2022.
  * [QSY22] Xiao-Liang Qi, Zhou Shangnan, and Zhenbin Yang.  Holevo information and ensemble theory of gravity.  Journal of High Energy Physics, 2022(2):1–24, 2022.
  * [QY18] Xiao-Liang Qi and Zhao Yang.  Space-time random tensor networks and holographic duality.  arXiv preprint arXiv:1801.05289, 2018.
  * [QYY17] Xiao-Liang Qi, Zhao Yang, and Yi-Zhuang You.  Holographic coherent states from random tensor networks.  Journal of High Energy Physics, 2017(8):1–29, 2017.
  * [RT06] Shinsei Ryu and Tadashi Takayanagi.  Holographic derivation of entanglement entropy from the anti–de sitter space/conformal field theory correspondence.  Physical review letters, 96(18):181602, 2006.
  * [SR95] Jorge Sánchez-Ruiz.  Simple proof of page’s conjecture on the average entropy of a subsystem.  Physical Review E, 52(5):5653, 1995.
  * [SŻ04] Hans-Jürgen Sommers and Karol Życzkowski.  Statistical properties of random density matrices.  Journal of Physics A: Mathematical and General, 37(35):8457, 2004\.
  * [VPYL19] Romain Vasseur, Andrew C Potter, Yi-Zhuang You, and Andreas WW Ludwig.  Entanglement transitions from holographic random tensor networks.  Physical Review B, 100(13):134203, 2019.
  * [Wig93] Eugene P Wigner.  Characteristic vectors of bordered matrices with infinite dimensions i.  The Collected Works of Eugene Paul Wigner: Part A: The Scientific Papers, pages 524–540, 1993.
  * [YHQ16] Zhao Yang, Patrick Hayden, and Xiao-Liang Qi.  Bidirectional holographic codes and sub-ads locality.  Journal of High Energy Physics, 2016(1):1–24, 2016.
  * [YLFC22] Zhi-Cheng Yang, Yaodong Li, Matthew PA Fisher, and Xiao Chen.  Entanglement phase transitions in random stabilizer tensor networks.  Physical Review B, 105(10):104306, 2022.
  * [YYQ18] Yi-Zhuang You, Zhao Yang, and Xiao-Liang Qi.  Machine learning spatial geometry from entanglement features.  Physical Review B, 97(4):045153, 2018.
  * [ŻPNC11] Karol Życzkowski, Karol A Penson, Ion Nechita, and Benoit Collins.  Generating random density matrices.  Journal of Mathematical Physics, 52(6):062201, 2011.
  * [ŻS01] Karol Życzkowski and Hans-Jürgen Sommers.  Induced measures in the space of mixed quantum states.  Journal of Physics A: Mathematical and General, 34(35):7111, 2001\.
  * [ŻS03] Karol Życzkowski and Hans-Jürgen Sommers.  Hilbert-schmidt volume of the set of mixed quantum states.  Journal of Physics A: Mathematical and General, 36(39):10115, 2003\.

##  Appendix A Basics of the combinatorial approach to free probability theory

In this section, we will recall and give the necessary material on
_combinatorics_ and _free probability_ needed to understand the rest of this
section. All the material that we shall introduce is standard and can be found
in [NS06, MS17].

Let $\pi:=\\{V_{1},\cdots,V_{n}\\}$333Do not confuse with $\pi_{i}$ introduced
in Section 5 representing the different paths. be a partition of a finite
totally ordered set $S$ such that $\bigsqcup_{i\in[n]}V_{i}=S$. We call
$\\{V_{i}\\}$ the _blocks_ of $\pi$. We denote by $p\sim_{\pi}q$ if $p$ and
$q$ belongs to the same block of $\pi$. A partition $\pi$ of a set $S$ is
called _crossing_ if there exists $p_{1}<q_{1}<p_{2}<q_{2}$ in $S$ such that
$p_{1}\sim_{\pi}p_{2}\nsim_{\pi}q_{1}\sim q_{2}$. We called a _non-crossing_
partition if $\pi$ is not crossing. We note by $\operatorname{NC}(S)$ the non-
crossing partition set of $S$. In particular if $S=\\{1,\cdots n\\}$, we
denote the non-crossing partition by $\operatorname{NC}(n)$. The set of non-
crossing partition plays a crucial in different areas from combinatorics
[Arm07] to random matrices and free probability theory which will be our main
focus. Moreover one should mention a crucial result [NS06]: _there exists a
one-to-one correspondence of the non-crossing partition set and the set of
permutations $\alpha$ in a geodesic between $\gamma$ and $\operatorname{id}$
i.e $|\alpha|+|\alpha^{-1}\gamma|=|\gamma|$._ Another important fact, the
cardinality $|\operatorname{NC}(n)|=\mathrm{Cat}_{n}$ where:

$\mathrm{Cat}_{n}:=\frac{1}{n+1}\binom{2n}{n},$ (19)

are the _Catalan numbers_. For more combinatorial details and properties of
the Catalan numbers and the non-crossing partitions see [NS06]. Assume
$(\alpha_{1},\cdots,\alpha_{k})$ $k$ tuples of permutations in
$\mathcal{S}_{n}$ such that

$|\alpha_{1}|+\sum_{i\in[k-1]}|\alpha_{i}^{-1}\alpha_{i+1}|+|\alpha_{k}^{-1}\gamma|=|\gamma|.$
(20)

are geodesics between $\operatorname{id}$ and $\gamma$. The cardinality of the
set of the $k$ tuple permutations satisfying the geodesic equation (20) known
as the _Fuss-Catalan_ numbers given by:

$\mathrm{FC}_{n,k}:=\frac{1}{nk+1}\binom{n+nk}{n},$

generalizing the Catalan numbers for $k=1$.

Now we are ready to introduce the _free probability theory_ tools that will be
used in this work. Moreover, one should mention the intrinsic link between
free probability theory and combinatorics where we will give some examples to
illustrate it. The combinatorics will allow us in the rest of this section to
understand our main result.

We recall that a _non-commutative probability space_ is a pair
$(\mathcal{A},\omega)$ of a unital $C^{*}$-algebra $\mathcal{A}$ with a state
_state_ $\omega:\mathcal{A}\to\mathbb{C}$ such that
$\omega(1_{\mathcal{A}})=1$. One says that the elements $a\in\mathcal{A}$
define a _noncommutative variable_. In the non-commutative probability space,
one can associate the distribution law $\mu_{a}$ to $a\in\mathcal{A}$ which is
defined as $\mu_{a}=\omega(a)$.

Before we give some concrete examples of some non-commutative probability
spaces, we shall recall the notion of _freeness_ that plays a crucial role in
the non-commutative probability world. The notion of freeness generalizes the
“classical” independence when the algebra $\mathcal{A}$ is commutative. We say
that for a given $n$ non-commutative random variables
$\\{a_{i}\\}\in\mathcal{A}$ are _free independent_ if for any polynomials
$\\{p_{i}\\}$ the following holds:

$\omega(a_{1}a_{2}\cdots a_{n})=0$ (21)

whenever $\omega(p_{k}(a_{i_{k}}))=0$ for $k\in[n]$ and two no adjacent
indices $i_{k}$ and $i_{k+1}$. One can check that with the definition of free
independence one has for given two free independent variables $a_{1}$ and
$a_{2}$:

$\omega((a_{1}-\omega(a_{1}))(a_{2}-\omega(a_{2}))=\omega(a_{1}a_{2})-\omega(a_{1})\omega(a_{2})=0,$
(22)

hence, generalizing the notion of standard independence in the commutative
setting where $\mathbb{E}(a_{1}a_{2})=\mathbb{E}(a_{1})\mathbb{E}(a_{2})$ for
two commutative random variables $a_{1},a_{2}$ in a commutative probability
space.

######  Definition A.1.

Let $(\mathcal{A}_{N},\omega_{N})$ with $N\in\mathbb{N}$ and
$(\mathcal{A},\omega)$ non-commutative probability spaces. We say that
$a_{N}\in\mathcal{A}_{N}$ converges weakly to $a\in\mathcal{A}$ as
$N\to\infty$ if the following holds:

$\lim_{N\to\infty}\omega_{N}((a_{N})^{n})=\omega(a^{n})\quad\forall
n\in\mathbb{N},$ (23)

where $\omega(a^{n})=\int x^{n}\mathrm{d}\mu_{a}(x)$ are the moments of $a$.

To illustrate concrete non-commutative probability spaces, we give some
classical examples. The first example we shall deal with is “classical”
probability space corresponding to commutative algebra. For that let
$(\Omega,\Sigma,\mu)$ where $\Omega$ a set, $\Sigma$ a $\sigma-$algebra, and
$\mu$ probability measure. Define $\mathcal{A}:=L^{\infty-}(\Omega,\mu)$
where:

$L^{\infty-}(\Omega,\mu):=\bigcap_{1\leq k<\infty}L^{k}(\Omega,\mu),$

and the state $\omega$ as:

$\omega(a):=\int_{\Omega}a(x)\mathrm{d}\mu(x),\quad a\in\mathcal{A}.$

The tuple $(\mathcal{A},\omega)$ defines a commutative probability space.
Another standard example that can be considered is the random matrices case.
Let us consider the algebra $\mathcal{A}$ consisting of valued $k\times k$
matrices over $L^{\infty-}(\Omega,\mu)$ where

$\mathcal{A}:=\mathcal{M}_{k}(L^{\infty-}(\Omega,\mu)).$

Define the state $\omega$ on $\mathcal{A}$ as:

$\omega(a):=\int_{\Omega}tr(a(x))\mathrm{d}\mu(x),\quad a\in\mathcal{A},$

where $tr(\cdot)$ is the normalized trace. The space $(\mathcal{A},\omega)$
define a non-commutative probability space which the space of random matrices
over $(\Omega,\Sigma,\mu)$.

We recall for a given non-commutative random variable $a\in\mathcal{A}$, the
$n$th moments of $a$ are given by

$m_{n}(\mu_{a}):=\int t^{n}\mathrm{d}\mu_{a}(t).$ (24)

Moreover for a given random variables $\\{a_{1},\cdots,a_{n}\\}$ in
$\mathcal{A}$, the moments are given by

$\omega(a_{1}\cdots
a_{n}):=\sum_{\pi\in\operatorname{NC}(n)}\kappa_{\pi}(a_{1},\cdots,a_{n}),$
(25)

where $\kappa_{\pi}$ are the _free cummulants_. The equation given above is
known as the _moments-cummulants formula_ , where the free independence can be
characterized by the vanishing of mixed cumulants (see [NS06, Chapter 11]).

In free probability theory, for two free independent random variables
$a_{1},a_{2}\in\mathcal{A}$, one can define a “convolution operation”. Mostly
in this work, we only shall deal with the _free multiplicative convolution_.
Let $a_{1}$ and $a_{2}$, two free independent random variables in
$\mathcal{A}$ with their respective distribution $\mu_{a_{1}}$ and
$\mu_{a_{2}}$. A free multiplicative convolution or simply a _free product_ is
defined by

$\mu_{a_{1}a_{2}}:=\mu_{a_{1}}\boxtimes\mu_{a_{2}},$ (26)

where $\mu_{a_{1}a_{2}}$ represents the distribution of $a_{1}\,a_{2}$. There
exists a standard and analytical way to compute the free product, like for the
free additive convolution, which can be done via the _S-transform_. The _S-
transform_ of a probability distribution $\mu_{a}$ is defined as:

$S_{\mu_{a}}(z):=\int\frac{1}{x-z}\mathrm{d}\mu_{a}(x),$ (27)

which is analogous to the R-transform for the free additive convolution, as we
shall describe. Moreover, it can also computed equivalently by _the formal
inverse of the moment-generating formal power series_ given by:

$S_{\mu_{a}}(z)=\frac{1-z}{z}M_{a}^{-1}(z),$ (28)

where $M_{a}^{-1}(z)$ is the formal inverse of the _moment-generating_ formal
power series given by

$M_{\mu_{a}}(z):=\sum_{k=1}^{\infty}\,m_{k,a}\,z^{k}.$ (29)

With the help of the S-transform, one can compute the free product where:

$S_{\mu_{a_{1}a_{2}}}(z)=S_{\mu_{a_{1}}}(z)\,S_{\mu_{a_{2}}}(z)=S_{\mu_{a_{1}\boxtimes\mu_{a_{2}}}}(z).$
(30)

In the following, we shall recall some standard distributions that are well-
known in the literature and will be highly used in this work.

The first distribution we shall consider here is the _semicircular law_ , it
is one of the most important distributions we encounter in free probability
theory. The semicircular distribution $\mu_{\text{SC}}(x)$ is defined by the
density:

$\mathrm{d}\mu_{\text{SC}}(x):=\frac{\sqrt{4-x^{2}}}{2\pi}\mathbbm{1}_{x\in[-2,2]}\mathrm{d}x.$
(31)

For an illustration, and by standard computation, one can compute the
S-transform of the semi-circular distribution:

$S_{\mu_{\text{SC}}}(z)=\frac{-z+\sqrt{z^{2}-4}}{2}.$

The first link that can be made, is the moments of the semicircular
distribution are intrinsically related to the Catalan numbers. One can easily
check that the following equality holds:

$\int x^{k}\mathrm{d}\mu_{\text{SC}}(x)=\mathrm{Cat}_{k},$ (32)

where $\mathrm{Cat}_{k}$ are the Catalan numbers see equation (19), and
Chapter 2 in [NS06] for more details. Moreover, one should say that the
S-transform gives another important link between free probability and
combinatorics by computing the moments of free product convolution of
Marc̆henko-Pastur distribution (see Theorem A.6).

Another well-known, due to Wigner [Wig93] shows the following result linking
the semicircular distribution and random Gaussian matrices.

######  Theorem A.2.

[Wig93] Let $N\in\mathbb{N}$, let $A_{N}$ be an $N\times N$ selfadjoint random
Gaussian matrix. Then $A_{N}$ converges weakly to a semicircular distribution
$\mu_{SC}(x)$.

We refer to [AGZ10] for a complete proof. As we have shown in this particular
case the existence of a deep link between random Gaussian matrices, the
semicircular law, and the Catalan numbers. Moreover, the semicircular law
plays an important role in free probability theory as a free central limit
distribution. We recall one of the main results in free probability theory,
see Theorem 8.10 in [NS06].

######  Theorem A.3.

Let $(\mathcal{A},\omega)$ a non-commutative probability space and
$a_{1},\cdots,a_{N}\in\mathcal{A}$ free independent and identically
distributed self-adjoint random variables. Assuming that $\omega(a_{i})=0$ for
$i\in[N]$ and denote by $\sigma^{2}:=\omega(a_{i}^{2})$ the variance of the
random variables $a_{i}$. Then the following holds:

$\frac{a_{1}+\cdots+a_{N}}{\sqrt{N}}\to\mu_{SC}(x).$

converges weakly to $\mu_{SC}(x)$ as $N\to\infty$. Where $s$ is a semicircular
of variance $\sigma^{2}$.

With this particular distribution, we have shown how random matrices,
combinatorics, and free probability theory can be related.

In the following, we will give another example of distribution that will play
an important role in this work. The second distribution we shall consider is
the _Marc̆henko-Pastur distribution_. We shall denote by $\mathrm{MP}(t)$
defined by:

$\displaystyle\mathrm{MP}(t)$ $\displaystyle:=\max(1-t,0)\delta_{0}+\nu_{t},$
$\displaystyle d\nu_{t}(x)$ $\displaystyle:=\frac{\sqrt{4t-(x-1-t)^{2}}}{2\pi
x}\mathbbm{1}_{(x-1-t)^{2}\leq 4t}\mathrm{d}x.$

Recall the Marc̆henko-Pastur distribution is deeply related to Wishart
matrices. Let $Z$ a Whishart matrix defined $Z:=\frac{1}{m}YY^{*}$, where
$Z\in\mathcal{M}_{nm}(\mathbb{C})$ where the entries of
$Y\in\mathcal{M}_{nm}(\mathbb{C})$ are complex random Gaussian variables. It
was shown by Marc̆henko and Pastur that the empirical distribution of Whishart
matrices converges to the $\mathrm{MP}(t)$ defined above. More precisely they
have shown the following theorem:

######  Theorem A.4.

Consider a Whishart matrix $Z$, and let $\mu_{n,m}$ its empirical distribution
given by:

$\mu_{n,m}:=\frac{1}{n}\sum_{z\in\operatorname{spec}(Z)}\delta_{z},$

Assuming that $n/m$ converges to $t$ as $n\to\infty$. Then $\mu_{n,m}$
converges (weakly) to $\mathrm{MP}(t)$ with $t>0$.

For a proof and more detailed statement of this result, we refer to Theorem
3.6 and Theorem 3.7 from [BS10]. In particular, what will an important role in
this work is the $\mathrm{MP}$, where the distribution is:

$\mathrm{d}\mathrm{MP}:=\frac{1}{2\pi}\sqrt{4x^{-1}-1}\,\mathrm{d}x,$ (33)

where we have used the shorthand notation $\mathrm{MP}$ instead of
$\mathrm{MP}(1)$.

As for the semicircular distribution described previously, one can relate the
moments of free convolution products of $\mathrm{MP}$ to Fuss-Catalan numbers.
We shall only give some relevant results for the Marc̆henko-Pastur
distribution to be as concise as possible, we refer to [BBCC11] for more
details and proofs.

######  Theorem A.5.

Let $\mathrm{MP}(t)$ the Marc̆henko-Pastur distribution. The S-transform is
given by:

$S_{\mathrm{MP}(t)}(z)=\frac{1}{t+z}.$

One of the main results of [BBCC11], relates the free product convolution of
$\mathrm{MP}(t)$ and combinatorics, in particular, we shall only give the
result for $\mathrm{MP}$ that will be relevant for this work.

######  Theorem A.6.

Let $\mathrm{MP}$ the Marc̆henko-Pastur distribution. Let
$\mathrm{MP}^{\boxtimes s}$ with $s\geq 2$, then we have

$\int_{\mathbb{R}}x^{n}\mathrm{d}\mathrm{MP}^{\boxtimes s}=\mathrm{FC}_{n,s},$
(34)

where $\mathrm{FC}_{n,s}$ are the Fuss-Catalan numbers.


2617 | Jiangxi | 13 | 49 | 236 | 71 | $11.7727$ | CE | 239 | $11.77$ | 3 | 49.1 | 239 | 76 | 359 | 56 | $11.7730$
2634 | James | 96 |  $-$50 | 269 |  $-$38 | $16.5147$ | C | 213 | $16.51$ | 2 | 33.7 | 126 |  $-$46 | 292 |  $-$43 | $16.5146$
2649 | Oongaq | 127 | 38 | 280 | 57 | $7.7854$ | C | 179 | $7.79$ | 3 | 11.4 | 172 | 33 | 356 | 75 | $7.7854$
2677 | Joan | 13 |  $-$68 | 242 |  $-$58 | $16.9788$ | CE | 149 | $16.98$ | 3 | 17.7 | 253 |  $-$35 | 53 |  $-$53 | $16.9787$
2706 | Borovsky | 111 | 68 | 303 | 46 | $63.80$ | C | 94 | $63.85$ | 2 | 15.0 | 317 | 67 |  |  | $63.79$
2715 | Mielikki | 20 | 55 | 179 | 50 | $33.599$ | CE | 172 | $33.62$ | 3- | 13.2 | 1 | 75 | 153 | 65 | $33.598$
2725 | David Bender | 124 |  $-$72 | 233 | 26 | $9.9574$ | CE | 249 | $9.96$ | 3- | 42.9 | 58 |  $-$57 | 198 |  $-$37 | $9.9580$
2839 | Annette | 155 |  $-$39 | 340 |  $-$48 | $10.4609$ | CE | 155 | $10.46$ | 3 | 7.3 | 154 |  $-$36 | 341 |  $-$49 | $10.4609$
2854 | Rawson | 36 |  $-$47 | 230 |  $-$70 | $4.77559$ | CE | 158 | $4.78$ | 3 | 7.2 | 336 |  $-$83 |  |  | $4.77559$
2889 | Brno | 40 | 56 | 199 | 44 | $9.5322$ | CE | 116 | $9.51$ | 2+ | 17.2 | 46 | 55 |  |  | $9.5320$
2957 | Tatsuo | 88 | 46 | 247 | 47 | $6.82041$ | CE | 219 | $6.82$ | 3 | 22.5 | 81 | 45 | 248 | 32 | $6.82042$
2962 | Otto | 70 | 44 |  |  | $2.67805$ | C | 241 | $2.68$ | 3 | 15.1 | 230 |  $-$58 |  |  | $2.53632$
2973 | Paola | 20 |  $-$57 | 196 |  $-$77 | $155.35$ | E | 71 | $24.00$ | 1 | 14.3 | 182 |  $-$79 | 41 |  $-$68 | $155.26$
3017 | Petrovic | 187 |  $-$71 | 353 |  $-$65 | $4.08037$ | CE | 241 | $4.08$ | 3 | 12.8 | 9 |  $-$55 |  |  | $4.08036$
3066 | McFadden | 113 |  $-$69 | 279 |  $-$21 | $32.752$ | C | 328 | $13.80$ | 3 | 13.5 | 132 |  $-$80 |  |  | $32.752$
3169 | Ostro | 134 |  $-$29 | 241 |  $-$54 | $6.50917$ | CE | 165 | $6.50$ | 3 | 4.7 | 247 |  $-$56 |  |  | $6.50916$
3210 | Lupishko | 38 | 57 | 269 | 98 | $14.2491$ | CE | 217 | $14.26$ | 2+ | 19.1 | 136 | 86 |  |  | $14.2492$
3232 | Brest | 98 | 56 | 287 | 71 | $154.04$ | E | 133 | $5.29$ | 2 | 20.3 | 36 | 78 | 159 | 59 | $154.03$
3266 | Bernardus | 230 |  $-$33 |  |  | $10.7596$ | C | 195 | $10.76$ | 3 | 6.2 | 227 |  $-$32 |  |  | $10.7595$
3314 | Beals | 31 | 66 | 242 | 42 | $5.46136$ | C | 100 | $5.46$ | 3 | 6.8 | 159 |  $-$42 | 358 |  $-$46 | $5.46233$
3332 | Raksha | 17 | 100 |  |  | $4.80563$ | CE | 239 | $4.81$ | 3 | 14.6 | 204 | 78 |  |  | $4.80563$
3376 | Armandhammer | 145 |  $-$10 | 325 | 10 | $7.9110$ | CE | 177 | $7.92$ | 3- | 7.9 | 316 | 11 | 136 |  $-$1 | $7.9112$
3383 | Koyama | 84 | 47 | 282 | 79 | $111.76$ | CE | 162 | $111.84$ | 2 | 10.6 | 70 | 68 |  |  | $111.77$
3613 | Kunlun | 304 | 82 | 347 | 57 | $308.9$ | CE | 127 |  |  |  | 311 | 67 | 80 | 69 | $308.9$
3623 | Chaplin | 15 |  $-$59 | 193 |  $-$53 | $8.3498$ | C | 105 | $8.36$ | 3 | 9.9 | 168 |  $-$50 | 345 |  $-$55 | $8.3498$
3772 | Piaf | 64 | 54 | 260 | 62 | $5.37611$ | CE | 208 | $5.38$ | 3 | 19.0 | 136 | 63 | 336 | 67 | $5.37617$
3776 | Vartiovuori | 119 |  $-$7 | 284 |  $-$65 | $11.3414$ | E | 221 | $11.34$ | 2 | 22.5 | 284 |  $-$64 |  |  | $11.3410$
3786 | Yamada | 75 | 59 | 218 | 44 | $4.03295$ | CE | 277 | $4.03$ | 3 | 15.8 | 218 | 48 | 84 | 52 | $4.03295$
3811 | Karma | 89 | 51 | 263 | 19 | $14.4236$ | C | 141 | $13.23$ | 2+ | 30.3 | 89 | 52 | 264 | 12 | $14.4234$
3883 | Verbano | 238 |  $-$50 | 349 |  $-$74 | $50.919$ | CE | 220 | $50.80$ | 2+ | 11.8 | 206 |  $-$75 | 346 |  $-$63 | $50.921$
3924 | Birch | 62 | 17 | 242 |  $-$2 | $18.6684$ | CE | 94 | $18.74$ | 2 | 16.8 | 238 | 17 | 57 | 37 | $18.6720$
3935 | Toatenmongakkai | 165 |  $-$10 | 345 |  $-$2 | $103.90$ | E | 104 | $106.30$ | 2 | 9.6 | 294 |  $-$84 |  |  | $104.29$
4012 | Geballe | 172 | 35 | 353 | 52 | $5.88574$ | E | 97 | $5.89$ | 3 | 5.8 | 145 | 35 | 326 | 45 | $5.88571$
4077 | Asuka | 36 | 62 | 272 | 65 | $7.9231$ | CE | 217 | $7.92$ | 3- | 19.5 | 267 | 44 | 57 | 45 | $7.9231$
4088 | Baggesen | 18 | 75 |  |  | $6.45273$ | E | 169 |  |  | 6.5 | 40 | 36 | 232 | 31 | $6.45277$
4102 | Gergana | 108 | 47 | 290 | 68 | $5.22345$ | E | 76 |  |  | 12.0 | 95 | 68 |  |  | $5.22340$
4132 | Bartok | 266 | 87 |  |  | $3.29632$ | C | 123 | $3.30$ | 3 | 9.7 | 186 | 87 |  |  | $3.29633$
4163 | Saaremaa | 70 | 37 | 263 | 56 | $26.327$ | E | 154 |  |  | 19.9 | 264 | 60 | 89 | 28 | $26.327$
4170 | Semmelweis | 111 | 51 | 315 | 80 | $5.30524$ | C | 147 | $5.31$ | 3- | 16.8 | 262 | 89 |  |  | $5.30526$
4222 | Nancita | 41 |  $-$58 | 240 |  $-$48 | $3.87292$ | CE | 129 | $3.87$ | 3 | 9.6 | 45 |  $-$42 | 238 |  $-$40 | $3.87292$
4271 | Novosibirsk | 97 | 43 | 302 | 68 | $8.8468$ | E | 153 | $8.85$ | 3 |  | 246 | 84 |  |  | $8.8468$
4285 | Hulkower | 181 |  $-$44 | 249 |  $-$65 | $6.14987$ | E | 93 | $6.15$ | 3 | 7.8 | 235 |  $-$65 |  |  | $6.14986$
4374 | Tadamori | 144 |  $-$68 | 290 |  $-$54 | $4.50495$ | C | 107 | $4.50$ | 3 | 5.7 | 190 |  $-$41 | 7 |  $-$54 | $4.50495$
4483 | Petofi | 88 | 52 |  |  | $4.33363$ | E | 127 | $4.33$ | 3 | 5.8 | 107 | 40 |  |  | $4.33299$
4611 | Vulkaneifel | 147 | 31 | 341 | 13 | $3.75596$ | E | 124 | $3.76$ | 3 | 11.0 | 197 |  $-$50 | 5 |  $-$86 | $3.75636$
4800 | $-$ | 111 |  $-$67 | 286 |  $-$44 | $6.21566$ | CE | 109 | $6.22$ | 2 | 14.1 | 274 | 16 | 94 |  $-$9 | $6.21486$
4810 | Ruslanova | 343 | 68 |  |  | $69.76$ | E | 72 | $69.76$ | 2 | 6.3 | 124 | 55 |  |  | $69.76$
4820 | Fay | 127 |  $-$82 | 344 |  $-$65 | $3.72739$ | C | 108 | $3.73$ | 3 | 8.6 | 248 |  $-$67 | 67 |  $-$40 | $3.72744$
5111 | Jacliff | 98 |  $-$57 | 292 |  $-$34 | $2.83989$ | E | 108 | $2.84$ | 3 | 6.5 | 259 |  $-$45 |  |  | $2.83990$
5247 | Krylov | 336 |  $-$48 |  |  | $82.29$ | CE | 160 | $81.50$ | 2 | 7.7 | 262 |  $-$42 |  |  | $82.29$
5281 | Lindstrom | 35 |  $-$75 | 209 |  $-$52 | $9.2512$ | CE | 154 | $9.25$ | 2 | 17.0 | 84 |  $-$81 | 238 |  $-$72 | $9.2511$
5488 | Kiyosato | 68 | 75 | 282 | 74 | $8.7632$ | CE | 165 | $8.79$ | 2 | 18.8 | 19 | 23 | 242 | 62 | $8.7631$
5596 | Morbidelli | 22 |  $-$64 | 194 |  $-$70 | $5.3992$ | E | 65 | $5.40$ | 3 | 5.7 | 173 |  $-$80 |  |  | $5.4004$
5647 | $-$ | 185 | 54 |  |  | $6.13971$ | E | 147 | $6.14$ | 3 | 8.6 | 266 | 69 |  |  | $6.13867$
5687 | Yamamotoshinobu | 209 |  $-$71 | 306 |  $-$86 | $154.88$ | E | 154 |  |  | 13.8 | 66 |  $-$89 |  |  | $154.87$
5776 | $-$ | 175 |  $-$66 | 333 |  $-$34 | $4.34076$ | E | 65 | $4.34$ | 2 |  | 360 |  $-$72 |  |  | $4.34079$
5925 | $-$ | 276 |  $-$32 |  |  | $5.39962$ | E | 63 | $5.40$ | 3 | 6.1 | 321 |  $-$63 | 128 |  $-$46 | $5.40076$
5933 | Kemurdzhian | 24 |  $-$31 | 201 |  $-$34 | $4.75566$ | E | 60 |  |  | 3.6 | 223 |  $-$62 | 40 |  $-$60 | $4.75651$
6882 | Sormano | 113 |  $-$37 | 316 |  $-$37 | $3.99835$ | CE | 108 | $3.69$ | 2 | 8.1 | 43 |  $-$33 | 248 |  $-$58 | $3.99835$
7151 | $-$ | 58 |  $-$48 | 243 |  $-$33 | $5.07202$ | E | 119 | $5.07$ | 3 | 9.4 | 182 |  $-$52 |  |  | $5.07205$
7233 | Majella | 40 |  $-$41 |  |  | $3.81244$ | E | 110 | $3.81$ | 3 |  | 80 |  $-$71 | 298 |  $-$87 | $3.81240$
8380 | Tooting | 152 |  $-$30 |  |  | $36.892$ | E | 90 | $36.93$ | 3 | 10.0 | 248 | 33 | 85 | 17 | $36.894$
8532 | $-$ | 110 | 49 | 307 | 12 | $112.59$ | E | 63 | $30.00$ | 2 | 8.8 | 292 | 68 |  |  | $112.61$
12008 | Kandrup | 19 |  $-$35 |  |  | $32.940$ | CE | 141 | $32.90$ | 3 | 4.2 | 351 |  $-$61 |  |  | $32.940$
12690 | $-$ | 48 |  $-$73 | 303 |  $-$46 | $147.34$ | E | 132 |  |  | 15.3 | 282 |  $-$62 | 112 |  $-$87 | $147.35$
16009 | $-$ | 86 | 71 | 292 | 44 | $16.6910$ | CE | 191 | $16.70$ | 2+ | 10.1 | 283 | 44 |  |  | $8.3476$
21652 | Vasishtha | 346 |  $-$49 |  |  | $16.287$ | E | 68 | $16.29$ | 3 | 10.5 | 336 |  $-$45 |  |  | $16.288$
Table 3: continued. 666 We provide ecliptic coordinates $\lambda$ and $\beta$ of up to two pole solutions, sidereal rotational period $P$ (its uncertainty is of the order of the last digit). The method (M) column indicates whether the rotation period was derived by the convex inversion (C), ellipsoid (E) approach, or both (CE) approaches. The final columns are the number of ASAS-SN measurements $N_{\mathrm{A}}$, the LCDB period with its reliability flag (Warner et al. 2009), the size $D$ from the MP3C database555https://mp3c.oca.eu/catalogue/index.htm, and the DAMIT rotation state solution.  Table 4: Physical properties of asteroids with new rotation period determinations based on the $V$-band ASAS-SN data. Asteroid | $P$ | M | $N_{\mathrm{A}}$ | $D$
---|---|---|---|---
| [hours] |  |  | [km]
835 | Olivia | $1104.0$ | C | 145 | 30.4
991 | McDonalda | $339.5$ | E | 178 | 38.6
1034 | Mozartia | $449.9$ | E | 216 | 9.7
1445 | Konkolya | $59.395$ | C | 96 | 20.3
1714 | Sy | $317.8$ | E | 193 | 14.0
1745 | Ferguson | $1078.2$ | C | 136 | 12.1
1755 | Lorbach | $7.9765$ | CE | 208 | 24.9
1787 | Chiny | $13.5609$ | E | 173 | 19.9
1984 | Fedynskij | $8.1405$ | E | 187 | 38.4
2027 | Shen Guo | $1117.3$ | E | 164 | 16.5
2051 | Chang | $12.0142$ | CE | 183 | 16.4
2138 | Swissair | $369.7$ | C | 244 | 12.9
2158 | Tietjen | $8.6581$ | E | 137 | 22.7
2165 | Young | $6.39009$ | CE | 143 | 27.1
2191 | Uppsala | $31.317$ | E | 213 | 17.5
2219 | Mannucci | $27.460$ | E | 172 | 39.1
2226 | Cunitza | $189.05$ | E | 159 | 14.6
2248 | Kanda | $24.736$ | E | 169 | 26.4
2404 | Antarctica | $2.26238$ | CE | 143 | 23.2
2405 | Welch | $14.3411$ | E | 123 | 26.4
2413 | van de Hulst | $211.96$ | E | 190 | 20.8
2475 | Semenov | $12.2370$ | E | 131 | 14.5
2502 | Nummela | $14.3151$ | E | 97 | 19.0
2660 | Wasserman | $628.3$ | E | 137 | 9.2
2780 | Monnig | $681.8$ | E | 91 | 4.8
2795 | Lepage | $40.368$ | E | 107 | 6.1
2819 | Ensor | $161.66$ | E | 130 | 9.7
2837 | Griboedov | $3.94988$ | C | 119 | 12.3
2909 | Hoshi-no-ie | $311.3$ | CE | 188 | 21.3
2949 | Kaverznev | $83.81$ | CE | 77 | 7.0
2967 | Vladisvyat | $8.3739$ | E | 176 | 32.9
3158 | Anga | $10.3203$ | E | 113 | 7.3
3181 | Ahnert | $1187.1$ | E | 134 | 8.0
3214 | Makarenko | $249.2$ | E | 165 | 21.2
3311 | Podobed | $191.43$ | E | 127 | 17.3
3346 | Gerla | $26.239$ | E | 208 | 34.6
3365 | Recogne | $254.2$ | E | 114 | 17.7
3380 | Awaji | $87.74$ | E | 125 | $-$
3650 | Kunming | $12.3703$ | E | 111 | 26.6
3681 | Boyan | $966.3$ | C | 107 | 4.2
3702 | Trubetskaya | $8.2905$ | E | 207 | 18.2
3863 | Gilyarovskij | $12.9588$ | E | 114 | 6.5
3955 | Bruckner | $7.5492$ | E | 205 | 18.1
4101 | Ruikou | $3.13391$ | E | 76 | 8.2
4103 | Chahine | $105.08$ | CE | 208 | 13.3
4121 | Carlin | $97.78$ | E | 74 | 6.9
4129 | Richelen | $288.8$ | E | 75 | 5.4
4256 | Kagamigawa | $1014.7$ | E | 110 | 7.5
4292 | Aoba | $291.1$ | C | 97 | 24.7
4380 | Geyer | $7.7282$ | E | 120 | 16.9
4593 | Reipurth | $5.9985$ | E | 96 | 12.3
5042 | Colpa | $169.62$ | E | 151 | 20.2
5077 | Favaloro | $4.59045$ | E | 68 | 4.5
5203 | Pavarotti | $6.93199$ | E | 97 | 5.0
5238 | Naozane | $80.61$ | E | 69 | 5.9
5650 | Mochihito-o | $601.3$ | CE | 196 | 11.4
5886 | Rutger | $3.32503$ | E | 142 | 17.3
6064 | Holasovice | $337.7$ | C | 71 | 3.8
6917 | $-$ | $351.9$ | CE | 74 | 4.4
7387 | Malbil | $7.5498$ | E | 64 | $-$
10314 | $-$ | $1311.5$ | E | 73 | 21.8
10426 | Charlierouse | $36.975$ | E | 147 | 9.2
11358 | $-$ | $10.7927$ | E | 84 | 13.6
11923 | $-$ | $7.1288$ | E | 62 | 2.8
13249 | Marcallen | $190.9$ | E | 123 | 20.8
13832 | $-$ | $98.43$ | E | 169 | 37.5
14720 | $-$ | $108.14$ | E | 149 | 8.5
20602 | $-$ | $7.3061$ | E | 79 | 23.7
27396 | Shuji | $203.68$ | E | 106 | 23.9
Table 4: continued. 777 We provide the sidereal rotational period $P$ (its
uncertainty is on the order of the last digit). The method column (M)
indicates whether the rotation period was derived by the convex inversion
approach (C), the ellipsoid approach (E), or both (CE). The final two columns
are the number of ASAS-SN measurements $N_{\mathrm{A}}$ and the size $D$ from
the MP3C database.


######  Lemma 10.

Given a stochastic game and a set $T$ of target states, Algorithm 2 computes
the supports of the distributions from which player $1$ is almost-sure winning
for weakly synchronizing in $T$. This algorithm can be implemented in PSPACE.

###### Proof.

The correctness of the algorithm follows from the arguments given above. We
show that this algorithm can be implemented in PSPACE by a similar proof as
for deterministic games (Lemma 6). We already showed that the number of
executions of the main loop (line 2) is at most $n^{2}$ (see _Termination_),
and since the period of the set $U$ (line 2) is at most $2^{n}$ times the
period of the game ${\mathcal{H}}$ (slices are subsets of $Q$), the final
value of $r$ (upon termination of the algorithm) is at most
$(2^{n})^{n^{2}}=2^{n^{3}}$.

A PSPACE implementation of Algorithm 2 can be obtained by using a PSPACE
procedure to determine the transitions of
${\mathcal{H}}\\!\upharpoonright\\![K]$ and
${\mathcal{H}}\\!\upharpoonright\\![S]$, as in the proof of Lemma 6. The
computation of the positive attractors, and almost-sure winning regions can
then be done in PSPACE as well. ∎

We obtain the following theorem, where the PSPACE upper bound is given by
Lemma 10, and the lower bound and memory requirement hold in the special case
of MDPs [DMS19, Theorem 6].

######  Theorem 3.

The membership problem for almost-sure weakly synchronizing in stochastic
games is PSPACE-complete, and pure counting strategies are sufficient for
player $1$. Infinite memory is necessary in general.

###  4.3 Other synchronizing objectives

The almost-sure winning region for the other synchronizing objectives can be
computed relatively easily.

######  Lemma 11.

For always synchronizing, the sure and almost-sure winning modes coincide:
$\langle\\!\langle
1\rangle\\!\rangle_{\mathit{sure}}^{\mathit{always}}(T)=\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{always}}(T)$.

###### Proof.

The inclusion $\langle\\!\langle
1\rangle\\!\rangle_{\mathit{sure}}^{\mathit{always}}(T)\subseteq\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{always}}(T)$ follows from the
definitions (Section 2). For the converse inclusion, consider an initial
distribution $d_{0}$ from which player $1$ has an almost-sure winning strategy
for always synchronizing in $T$. We claim that player $1$ has a strategy
$\sigma_{{\rm safe}}$ to ensure, for all plays
$\rho=q_{0}\,a_{0}b_{0}\,q_{1}\ldots q_{k}$ compatible with $\sigma$, that
$q_{i}\in T$ for all $0\leq i\leq k$ (i.e., player $1$ is sure-winning for the
safety objective $\Box T$ [dAH00]). By contradiction, if that is not the case,
then player $2$ has a strategy to ensure reaching a state in $Q\setminus T$
within at most $n$ steps with positive probability (at least
$\eta_{0}\cdot\eta^{n}$) against all strategies of player $1$, in
contradiction with player $1$ being almost-sure winning for always
synchronizing in $T$. Hence such a strategy $\sigma_{{\rm safe}}$ exists and
we conclude the proof by observing that $\sigma_{{\rm safe}}$ is sure winning
for always synchronizing in $T$. ∎

The following lemma generalizes to games a result that holds for MDPs [Shi14,
Section 5.1.2].

######  Lemma 12.

[SvdB18] In stochastic games, we have $\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{event}}(T)=\langle\\!\langle
1\rangle\\!\rangle_{\mathit{sure}}^{\mathit{event}}(T)\cup\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{weakly}}(T)$.

###### Proof.

The inclusions $\langle\\!\langle
1\rangle\\!\rangle_{\mathit{sure}}^{\mathit{event}}(T)\subseteq\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{event}}(T)$ and
$\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{weakly}}(T)\subseteq\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{event}}(T)$ follow from the
definitions (Section 2). For the converse, consider an initial distribution
$d_{0}$ from which player $1$ has an almost-sure winning strategy for
eventually synchronizing in $T$. Towards contradiction, assume that
$d_{0}\not\in\langle\\!\langle
1\rangle\\!\rangle_{\mathit{sure}}^{\mathit{event}}(T)\cup\langle\\!\langle
1\rangle\\!\rangle_{\mathit{almost}}^{\mathit{weakly}}(T)$. Then for all
player-$1$ strategies $\sigma$, there exist player-$2$ strategies $\tau_{\rm
e}$ and $\tau_{\rm w}$ such that ${\mathcal{G}}^{\sigma,\tau_{\rm e}}_{d_{0}}$
is not sure eventually synchronizing in $T$, and
${\mathcal{G}}^{\sigma,\tau_{\rm w}}_{d_{0}}$ is not almost-sure weakly
synchronizing in $T$. Let $\tau$ be the strategy playing the superposition of
$\frac{1}{2}\tau_{\rm e}$ and $\frac{1}{2}\tau_{\rm w}$. Consider $\tau_{\rm
w}$ and following the definitions, there exists $\varepsilon_{w}>0$ and
$i^{*}\geq 0$ such that ${\mathcal{G}}^{\sigma,\tau}_{i}(T)<1-\varepsilon_{w}$
for all $i\geq i^{*}$. Moreover, considering $\tau_{\rm e}$, we have
${\mathcal{G}}^{\sigma,\tau}_{i}(T)<1-\frac{\eta_{0}}{2}\cdot\eta^{i^{*}}$ for
all $i\leq i^{*}$. For
$\varepsilon=\min\\{\varepsilon_{w},\frac{\eta_{0}}{2}\cdot\eta^{i^{*}}\\}>0$,
we get ${\mathcal{G}}^{\sigma,\tau}_{i}(T)<1-\varepsilon$ for all $i\geq 0$,
in contradiction to player $1$ being almost-sure winning for eventually
synchronizing in $T$. ∎

The reduction presented in the proof of Theorem 2 also shows PSPACE-hardness
for almost-sure eventually synchronizing in deterministic games.

######  Lemma 13.

Let ${\mathcal{G}}$ be a stochastic game. Given a target set $T$, an initial
distribution $d_{0}$ almost-sure winning for strongly synchronizing in $T$ if
and only if $d_{0}$ is almost-sure winning for the coBüchi objective
$\Diamond\Box T$.

###### Proof.

First, if player $1$ is almost-sure winning for the coBüchi objective
$\Diamond\Box T$ in ${\mathcal{G}}$, then there exists a memoryless winning
strategy $\sigma_{\mathrm{as}}$ for player $1$, which is such that all states
in the (reachable) end-components of the MDP obtained from the game
${\mathcal{G}}$ after fixing the strategy $\sigma_{\mathrm{as}}$ are in $T$
[CY95]. It is then easy to show that the strategy $\sigma_{\mathrm{as}}$ is
almost-sure winning for strongly synchronizing in $T$.

For the converse direction, if player $1$ is not almost-sure winning for the
coBüchi objective $\Diamond\Box T$ in ${\mathcal{G}}$, then there exists a
strategy $\tau$ for player $2$, which we can assume to be memoryless [CJH04],
such that for all player-$1$ strategies $\sigma$ we have
$\mathrm{Pr}_{d_{0}}^{\sigma,\tau}(\Diamond\Box T)<1$. Hence in the MDP
${\mathcal{G}}_{\tau}$ obtained from ${\mathcal{G}}$ by fixing the strategy
$\tau$, player $1$ is not almost-sure winning for the coBüchi objective
$\Diamond\Box T$, which is equivalent to say that in ${\mathcal{G}}_{\tau}$ no
player-$1$ strategy is almost-sure winning for strongly synchronizing in $T$
[DMS19, Lemma 27], and concludes the proof. ∎

We note that in deterministic games, the sure and almost-sure winning modes
coincide for state-based objectives, thus it follows from Lemma 13 that for
strongly synchronizing the sure and almost-sure winning modes coincide in
deterministic games.

We summarize the results of Section 4 for almost-sure synchronizing.

######  Theorem 4.

The membership problem for almost-sure always and strongly synchronizing can
be solved in polynomial time, and pure memoryless strategies are sufficient
for player $1$.

The membership problem for almost-sure eventually and weakly synchronizing is
PSPACE-complete, and pure counting strategies are sufficient for player $1$.
Infinite memory is necessary in general.

##  5 Conclusion

Stochastic games with synchronizing objectives combine stochasticity with the
presence of an adversary and a flavour of imperfect information, which
together tend to bring undecidability in a continuous setting [Paz71, MHC03].
The form of imperfect information in these games differs from the traditional
setting where the strategy of player $1$ is uniform (the same action is played
in all states) [BGB12, CFO20]. Here, player $1$ can see the local state of the
game, but needs to enforce a global objective defined on state distributions,
which are not visible to player $1$. Beyond decidability, it is perhaps
surprising that the membership problem for games is no harder than for MDPs
(PSPACE-complete), although the proof techniques are significantly more
involved, mainly due to the presence of an adversary, and the lack of
determinacy.

The main question raised by this model is whether it is possible to extend it
with a form of communication, while remaining decidable. This would bring us
closer to a wide range of applications in synthetic biology [NDS+16, VLN19]
and chemical reaction networks [CKL18]. In another direction, considering
other classes of objectives, such as combination of multiple synchronizing
objectives, or more quantitative conditions (where the probability threshold
is not $1$) are completely open problems.

#### Acknowledgment

We are grateful to Mahsa Shirmohammadi and Marie van den Bogaard for
preliminary discussions about this problem and for inspiring the example of
Figure 3.

## References

  * [AAGT12] M. Agrawal, S. Akshay, B. Genest, and P. S. Thiagarajan.  Approximate verification of the symbolic dynamics of Markov chains.  In Proc. of LICS: Logic in Computer Science, pages 55–64. IEEE, 2012.
  * [AGV18] S. Akshay, B. Genest, and N. Vyas.  Distribution-based objectives for Markov decision processes.  In Proc. of LICS: Logic in Computer Science, pages 36–45. ACM, 2018.
  * [BDGG17] N. Bertrand, M. Dewaskar, B. Genest, and H. Gimbert.  Controlling a population.  In Proc. of CONCUR: Concurrency Theory, volume 85 of LIPIcs, pages 12:1–12:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
  * [BGB12] C. Baier, M. Größer, and N. Bertrand.  Probabilistic $\omega$-automata.  Journal of the ACM, 59(1):1:1–1:52, 2012.
  * [BGG17] N. Bertrand, B. Genest, and H. Gimbert.  Qualitative determinacy and decidability of stochastic games with signals.  Journal of the ACM, 64(5):33:1–33:48, 2017.
  * [BK08] C. Baier and J.-P. Katoen.  Principles of Model Checking.  MIT, 2008.
  * [BS07] J. C. Bradfield and C. Stirling.  Modal mu-calculi.  In Handbook of Modal Logic, volume 3 of Studies in logic and practical reasoning, pages 721–756. North-Holland, 2007.
  * [Büc62] J. R. Büchi.  On a decision method in restricted second order arithmetic.  In Proc. of International Congress of Logic, Methodology and Philisophical Science 1960, pages 1–11. Stanford University Press, 1962.
  * [BW18] J. C. Bradfield and I. Walukiewicz.  The mu-calculus and model checking.  In Handbook of Model Checking, pages 871–919. Springer, 2018.
  * [CDHR07] K. Chatterjee, L. Doyen, T. A. Henzinger, and J.-F. Raskin.  Algorithms for omega-regular games of incomplete information.  Logical Methods in Computer Science, 3(3:4), 2007.
  * [CFO20] T. Colcombet, N. Fijalkow, and P. Ohlmann.  Controlling a random population.  In Proc. of FoSSaCS: Foundations of Software Science and Computation Structures, LNCS 12077, pages 119–135. Springer, 2020.
  * [CH12] K. Chatterjee and T. A. Henzinger.  A survey of stochastic $\omega$-regular games.  Journal of Computer and System Sciences, 78(2):394–413, 2012.
  * [Cha07] K. Chatterjee.  Stochastic $\omega$-regular Games.  PhD thesis, University of California, Berkeley, 2007.
  * [Chu63] A. Church.  Logic, arithmetics, and automata.  In Proc. of International Congress of Mathematicians, 1962, pages 23–35. Institut Mittag-Leffler, 1963.
  * [CJH04] K. Chatterjee, M. Jurdzinski, and T. A. Henzinger.  Quantitative stochastic parity games.  In Proc. of SODA: Symposium on Discrete Algorithms, pages 121–130. SIAM, 2004.
  * [CKFL05] I. D. Couzin, J. Krause, N. R. Franks, and S. A. Levin.  Effective leadership and decision-making in animal groups on the move.  Nature, 433:513–516, 2005.
  * [CKL18] L. Cardelli, M. Kwiatkowska, and L. Laurenti.  Programming discrete distributions with chemical reaction networks.  Nat. Comput., 17(1):131–145, 2018.
  * [Cou09] I. D. Couzin.  Collective cognition in animal groups.  Trends in cognitive sciences, 13(1):36–43, 2009.
  * [CY95] C. Courcoubetis and M. Yannakakis.  The complexity of probabilistic verification.  Journal of the ACM, 42(4):857–907, 1995.
  * [dAH00] L. de Alfaro and T. A. Henzinger.  Concurrent omega-regular games.  In Proc. of LICS: Logic in Computer Science, pages 141–154. IEEE, 2000.
  * [dAHK07] L. de Alfaro, T. A. Henzinger, and O. Kupferman.  Concurrent reachability games.  Theoretical Computer Science, 386(3):188–217, 2007.
  * [DMS19] L. Doyen, T. Massart, and M. Shirmohammadi.  The complexity of synchronizing Markov decision processes.  Journal of Computer and System Sciences, 100:96–129, 2019.
  * [EL00] M. Elowitz and S. Leibler.  A synthetic oscillatory network of transcriptional regulators.  Nature, 403(335-338), 2000.
  * [Esp14] J. Esparza.  Keeping a crowd safe: On the complexity of parameterized verification (invited talk).  In Proc. of STACS: Symposium on Theoretical Aspects of Computer Science, volume 25 of LIPIcs, pages 1–10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014.
  * [Isa12] V. V. Isaeva.  Self-organization in biological systems.  Biology Bulletin of the Russian Academy of Sciences, 39:110–118, 2012.
  * [JS07] P. Jancar and Z. Sawa.  A note on emptiness for alternating finite automata with a one-letter alphabet.  Inf. Process. Lett., 104(5):164–167, 2007.
  * [Kan92] R. Kannan.  Lattice translates of a polytope and the frobenius problem.  Combinatorica, 12:161–177, 1992.
  * [KVAK10] V. A. Korthikanti, M. Viswanathan, G. Agha, and Y. Kwon.  Reasoning about MDPs as transformers of probability distributions.  In Proc. of QEST: Quantitative Evaluation of Systems, pages 199–208. IEEE Computer Society, 2010.
  * [Mar98] D. A. Martin.  The determinacy of Blackwell games.  The Journal of Symbolic Logic, 63(4):1565–1581, 1998.
  * [MHC03] O. Madani, S. Hanks, and A. Condon.  On the undecidability of probabilistic planning and related stochastic optimization problems.  Artif. Intell., 147(1-2):5–34, 2003.
  * [Mye16] C. J. Myers.  Engineering genetic circuits.  CRC Press, 2016.
  * [NDS+16] A. A. K. Nielsen, B. S. Der, J. Singh, P. Vaidyanathan, V. Paralanov, E. A. Strychalski, D. Ross, D. Densmore, and C. A. Voigt.  Genetic circuit design automation.  Science, 352(6281)(aac7341), 2016.
  * [Paz71] A. Paz.  Introduction to probabilistic automata.  Academic Press, 1971.
  * [PR90] A. Pnueli and R. Rosner.  Distributed reactive systems are hard to synthesize.  In Proc. of FOCS: Foundation of Computer Science, pages 746–757, 1990.
  * [Rei84] John H. Reif.  The complexity of two-player games of incomplete information.  Journal of Computer and System Sciences, 29(2):274–301, 1984.
  * [Sch14] S. Schewe.  Distributed synthesis is simply undecidable.  Inf. Process. Lett., 114(4):203–207, 2014.
  * [Shi14] M. Shirmohammadi.  Qualitative analysis of probabilistic synchronizing systems.  PhD thesis, Université Libre de Bruxelles, 2014.
  * [SvdB18] M. Shirmohammadi and M. van den Bogaard.  Personal communication, 2018.
  * [Tho97] W. Thomas.  Languages, automata, and logic.  In Handbook of Formal Languages, volume 3, Beyond Words, chapter 7, pages 389–455. Springer, 1997.
  * [Var85] M. Y. Vardi.  Automatic verification of probabilistic concurrent finite-state programs.  In Proc. of FOCS: Foundations of Computer Science, pages 327–338. IEEE Computer Society, 1985.
  * [VLN19] O. Vo, H.-M. Lee, and D. Na.  Synthetic bacteria for therapeutics.  Journal of Microbiology and Biotechnology, 29(6):845–855, 2019\.