# Describing the hierarchical gravitational three-body problem with force and
torque vectors

Barnabás Deme<EMAIL_ADDRESS>Institute of Physics, Eötvös
University, Pázmány P. s. 1/A, Budapest, 1117, Hungary

###### Abstract

We investigate the hierarchical gravitational three-body problem, in which a
binary is perturbed by a distant object that orbits on a Keplerian ellipse
around the binary itself. This phenomenon, known as Kozai-Lidov mechanism in
the literature, results in large-amplitude oscillations of the orbital
elements, like eccentricity, which may significantly influence the evolution
of many astrophysical systems: from minor bodies and planets to even
supermassive black holes. The standard approach found in the literature
describes this phenomenon in the framework of Hamiltonian mechanics. Here we
derive the long term evolution of the triple with elementary tools, treating
the binary as a dipole interacting with the gravitational field of the
tertiary and describe the dynamics using forces and torques instead of the
usual Hamiltonian formalism. This highlights another aspect of the problem and
is likely an easier way to introduce the problem at the undergraduate level.

##  I Introduction

The gravitational three-body problem is one of the oldest open questions of
physics.valtonen  In contrast to the two-body case, it is non-integrable since
it lacks the sufficient number of first integrals. masoliver  As a
consequence, instead of finding new first integrals, other attempts have been
made to understand the long term evolution of the system. For example, recent
efforts have focused on finding a statistical solution, i.e. to predict the
distribution of the orbital elements after a strong three-body
interaction.stone

Another approach, which has a longer history, is to make approximating
assumptions about the three-body configuration, for which the long-term
evolution may be explored analytically. One such assumption is to neglect the
mass of one of the bodies, which results in the restricted three-body problem.
The most famous discovery in this field is probably the prediction of the
equilibrium Lagrange points.szebehely

Besides the restricted configuration, three body systems in the hierarchical
configuration also received attention in the past decades. These systems
consist of a binary, which is perturbed by a distant tertiary. The members of
the binary constitute the inner binary, and their barycenter together with the
tertiary forms the outer binary (see Fig. 1). In this case, the ratio of the
inner and outer orbital separations ($|\mathbf{r}|/|\mathbf{R}|=r/R$) is a
small parameter.

The standard technique to describe the dynamics of such systems uses the
Hamiltonian formalism.goldstein  One finds the perturbing Hamiltonian,
expresses it with the canonical orbital elements (these are usually the so-
called Delaunay elements) and expands it into a power series with respect to
the small parameter. Depending on the desired accuracy, the Hamiltonian is
truncated at a particular order: in a multipole expansion, when the terms
smaller than $\mathcal{O}(r^{2}/R^{2})$ are omitted, it is called the
quadrupole approximation (we note, however, that the gravitational force is
the minus gradient of the potential in the Hamiltonian, and hence is on the
order of $\mathcal{O}(r/R)$ after differentiating with respect to
$\mathbf{r}$). The long-term evolution of the system may be derived by time-
averaging the perturbation over the inner and outer orbital periods. The
equations of motion are then obtained from this double-averaged Hamiltonian.
It turns out that sufficiently inclined triples (for which the $i$ angle
between the inner and outer orbital planes is sufficiently large) are subject
to large-amplitude eccentricity and inclination oscillations. This phenomenon
is called the Kozai-Lidov (KL) mechanism,zeipel ; lidov ; kozai ; ito_ohtsuka
which plays an important role in the dynamics of several astrophysical
phenomena: from the formation of hot Jupiters to the merger of black
holes.naoz

Although the Hamiltonian formalism is elegant and easy-to-use, it is abstract
in the sense that it does not highlight the role of force and torque vectors.
Even if we express the Hamiltonian with the angular momentum and eccentricity
vectors,katz ; rungelenzlaplace  it is non-trivial how the KL mechanism
follows from the basic equations of translational
($m\ddot{\mathbf{r}}=\mathbf{F}$) and rotational
($m(\mathbf{r}\times\ddot{\mathbf{r}})=\mathbf{r}\times\mathbf{F}$) motions.
The aim of this paper is to derive the KL mechanism from these expressions. Up
to the knowledge of the author, this approach is new in the literature.

The structure of the paper is as follows. In Sec. II we derive the force and
torque vectors of the KL mechanism. In Sec. III we discuss the most important
physical implications and give a qualitative picture of the dynamics.

Throughout the paper, the gravitational constant is set to 1. The scalar and
vectorial products of $\mathbf{a}$ and $\mathbf{b}$ are denoted by
$\mathbf{a}\mathbf{b}$ and $\mathbf{a}\times\mathbf{b}$, respectively.

##  II The KL force and torque

Figure 1: Top: The hierarchical three-body problem, in which
$|\mathbf{r}|\ll|\mathbf{R}|$ (the figure is not to scale). Bottom: The
orbital elements of the inner binary from the blue box in the upper panel. The
reference plane to which they are defined is the orbital plane of the outer
binary.

In what follows we consider a three-body configuration, in which the ratio of
the separations is small, hence we refer to it as hierarchical (see Fig. 1).
Two of the bodies, which we call primary and secondary, comprise the inner
binary. Let us measure mass in units of the primary mass. The secondary (with
mass $1\ll m$) is assumed to orbit on a circular orbit around the tertiary
($M$), which is also much more massive ($m\ll M$). For instance, this may
represent a star-planet-moon system so we refer to the objects as star, planet
and moon hereafter. The goal of this work is to describe the long-term, i.e.
secular evolution of the inner binary (the moon around the planet), which is
perturbed by the star. We use the quadrupole approximation, i.e., we keep only
those terms in the expression of the force which are $\mathcal{O}(r/R)$ (or
$\mathcal{O}(r^{2}/R^{2})$ in the expression of the potential/Hamiltonian).

The validity of these assumptions can be confirmed by the example of the Sun-
Earth-Moon system.beletsky  The ratio of the inner and outer separations is
$r/R\approx a_{\mathrm{Moon}}/a_{\mathrm{Earth}}\approx 3\times 10^{-3}$, so
the system is hierarchical enough to omit the next term in the Hamiltonian
after the quadrupole (as that is $\sim 10^{-9}$). If the mass of the Moon is
set to 1, then $1\ll m_{\mathrm{Earth}}\approx 80$ and $m_{\mathrm{Earth}}\ll
M_{\mathrm{Sun}}\approx 2.7\times 10^{7}$, so the orders of magnitudes assumed
for the masses are also correct. Moreover, as $e_{\mathrm{Earth}}\approx
0.017$, the assumption of a circular outer orbit is valid, too. We note that
the assumptions above (except hierarchicity) may be left and the results below
can be generalized in a straightforward way.

Let us examine the behaviour of the orbital angular momentum vector, which is

$\mathbf{J}=J\left(\begin{array}[]{c}\sin i\sin\Omega\\\ -\sin i\cos\Omega\\\
\cos i\\\ \end{array}\right),$ (1)

where $J=\sqrt{ma(1-e^{2})}$ (for the notations see Fig. 1). Orbital elements
hereafter refer to the inner (planet-moon) binary. We note here that the spins
of the bodies are not taken into account, because their relative contributions
to the angular momenta are negligible (the spin to orbital angular momentum
ratios are $2\times 10^{-5}$ and $7\times 10^{-7}$ for the Moon and Earth,
respectively). The evolution of the angular momentum is driven by a torque,
$\dot{\mathbf{J}}=\mathbf{T}=\mathbf{r}\times\mathbf{F}$, where the
$\mathbf{r}$ vector from the planet to the moon acts as the lever arm vector
and

$\mathbf{F}=-\frac{m}{r^{3}}\mathbf{r}+\mathbf{F}_{\mathrm{out}}.$ (2)

The first term on the right-hand side is the gravitational attraction on the
moon exerted by the planet, while the second is that on the moon by the star:

$\mathbf{F}_{\mathrm{out}}=M\frac{3\mathbf{R}(\mathbf{R}\mathbf{r})-R^{2}\mathbf{r}}{R^{5}}.$
(3)

This is completely analagous to the Coulomb force exerted on an
electromagnetic dipole, where $\mathbf{r}$ plays the role of the dipole
vector.jackson  Its physical motivation is that the inner (planet–moon) binary
cannot be treated to be point-like, because it has a finite, although small
extent ($r\sim a\ll R$) which can be modelled as a dipole in the first
approximation in a multipole expansion.

Now let us calculate the work this force does on the moon’s orbit. We are not
interested in those effects which happen within one orbital period, so we sum
up the $\mathbf{F}\mbox{ d}\mathbf{r}$ work elements along one orbit:

$W=\oint\mathbf{F}\mbox{ d}\mathbf{r}=\oint\mathbf{F}\dot{\mathbf{r}}\mbox{
d}t=\oint\left(-\frac{m}{r^{3}}\mathbf{r}+\mathbf{F}_{\mathrm{out}}\right)\dot{\mathbf{r}}\frac{1-e\cos
E}{m^{1/2}a^{-3/2}}\mbox{ d}E,$ (4)

where we used $\mathrm{d}t=\mathrm{d}l/(m^{1/2}a^{-3/2})$ and
$\mathrm{d}l=1-e\cos E\mbox{ d}E$ from the Kepler equation ($l$ and $E$ are
the so-called mean and eccentric anomalies, respectively; see Appendix A for
the technical details). In order to evaluate the integral we may use that

$\mathbf{r}=\left(\begin{array}[]{c}x\\\ y\\\ z\\\
\end{array}\right)=\mathbf{R}_{z}(\Omega)\mathbf{R}_{x}(i)\mathbf{R}_{z}(\omega)\left(\begin{array}[]{c}a(\cos
E-e)\\\ a\sqrt{1-e^{2}}\sin E\\\ 0\\\ \end{array}\right),$ (5)

and

$\dot{\mathbf{r}}=\left(\begin{array}[]{c}\dot{x}\\\ \dot{y}\\\ \dot{z}\\\
\end{array}\right)=\mathbf{R}_{z}(\Omega)\mathbf{R}_{x}(i)\mathbf{R}_{z}(\omega)\frac{m^{1/2}a^{-3/2}}{1-e\cos
E}\left(\begin{array}[]{c}-a\sin E\\\ a\sqrt{1-e^{2}}\cos E\\\ 0\\\
\end{array}\right),$ (6)

where $\mathbf{R}_{j}(\alpha)$ is the rotation matrix around axis $j$ by an
angle $\alpha$.

Calculating the integral in Eq. (4) is not complicated and eventually gives
zero: $W=0$. It is not surprising, because we know from first principles that
the loop integral of any force that is the gradient of a potential is zero. In
other words, apart from some small periodic oscillations on the orbital
timescale, the energy of the moon remains secularly constant. We note that the
integration above can be considered as an averaging with respect to the mean
anomaly $l$, hence we can also write

$\langle W\rangle_{l}=0.$ (7)

The torque is

$\mathbf{T}=\mathbf{r}\times\mathbf{F}=M\mathbf{r}\times\frac{3\mathbf{R}(\mathbf{R}\mathbf{r})-R^{2}\mathbf{r}}{R^{5}}.$
(8)

In order to understand how this torque drives the long-term evolution of the
planet-moon binary, we calculate its averaged value over one orbital period.
In doing so, similarly to what we did in Eq. (4), we sum up the small
$\mathbf{T}\mbox{ d}l$ elements to get the net torque that affects the
dynamics of the moon over several orbital times. However, unlike the case of
the mechanical work, the integration over the inner (planet–moon) orbit now
yields a non-vanishing torque, so we extend it to the outer orbit, too:

$\langle\langle\mathbf{T}\rangle_{\phi}\rangle_{l}=\tilde{\mathbf{T}}=\frac{3M}{8R^{3}}a^{2}\sin
i\left(\begin{array}[]{c}\cos
i\left(-2-3e^{2}+5e^{2}\cos(2\Omega)\right)\cos\Omega-5e^{2}\sin(2\omega)\sin\Omega\\\
\cos
i\left(-2-3e^{2}+5e^{2}\cos(2\Omega)\right)\sin\Omega+5e^{2}\sin(2\omega)\cos\Omega\\\
0\\\ \end{array}\right),$ (9)

where $\phi$ is the mean anomaly of the outer orbit. Just like previously,
$\langle...\rangle_{l}=\int_{0}^{2\pi}...(1-e\cos E)\mbox{ d}E/(2\pi)$ is the
averaging over the moon’s orbit around the planet, while
$\langle...\rangle_{\phi}=\int_{0}^{2\pi}...\mbox{ d}\phi/(2\pi)$ is the one
over the orbit of the planet-moon binary itself around the star. The reason
for why the latter integral does not have a Jacobian determinant similar to
$1-e\cos E$ is that the outer orbit (planet around the star) is circular.

In order to grasp the geometrical meaning of the vector in Eq. (9), we
decompose it into two components. We first examine the parallel projection of
$\tilde{\mathbf{T}}$ onto $\hat{\mathbf{e}}_{\mathbf{J}}$, the unit vector in
the direction of the inner (planet–moon) binary’s angular momentum. The
parallel component, which changes only the magnitude of the angular momentum
but not its direction, is

$\mathbf{T}_{\parallel}=\hat{\mathbf{e}}_{\mathbf{J}}\left(\hat{\mathbf{e}}_{\mathbf{J}}\tilde{\mathbf{T}}\right)=-\frac{15M}{8R^{3}}a^{2}e^{2}\sin^{2}i\sin(2\omega)\hat{\mathbf{e}}_{\mathbf{J}}.$
(10)

The direction of $\mathbf{J}$ is driven by the perpendicular component:

$\mathbf{T}_{\bot}=\tilde{\mathbf{T}}-\hat{\mathbf{e}}_{\mathbf{J}}\left(\hat{\mathbf{e}}_{\mathbf{J}}\tilde{\mathbf{T}}\right),$
(11)

which leaves the magnitude of $\mathbf{J}$ unchanged. The components of this
vector are

$(\mathbf{T}_{\bot})_{x}=-\frac{3a^{2}M\sin(2i)}{16R^{3}}\left((2+3e^{2}-5e^{2}\cos(2\omega))\cos\Omega+5e^{2}\cos
i\sin(2\omega)\sin\Omega\right),$ (12)
$(\mathbf{T}_{\bot})_{y}=\frac{3a^{2}M\sin(2i)}{16R^{3}}\left((-2-3e^{2}-5e^{2}\cos(2\omega))\sin\Omega+5e^{2}\cos
i\sin(2\omega)\cos\Omega\right),$ (13)
$(\mathbf{T}_{\bot})_{z}=\frac{15a^{2}e^{2}M\sin(2i)\sin
i\sin(2\omega)}{16R^{3}}.$ (14)

##  III Discussion

The dynamics governed by the forces and torques above has some remarkable
features. First, the inner semi-major axis is constant. It follows from the
fact that the work of the tertiary on the inner binary is zero (see Eq. (7)),
consequently the total orbital energy ($h$) is secularly conserved. As
$a=-m/(2h)$, the semi-major axis remains constant, too.

Secondly, $\langle\langle T_{z}\rangle\rangle$ turns out to be zero (see Eq.
(9)), which means that

$\dot{J}_{1,z}=0\to\sqrt{ma(1-e^{2})}\cos
i=\mathrm{const.}\to\sqrt{1-e^{2}}\cos i=\mathrm{const.},$ (15)

where we took into account that $a=\mathrm{const.}$ The last expression is
known as the Kozai constant, while the vanishing of the vertical torque is
coined the ’happy coincidence’ in the Hamiltonian framework (because it makes
the system integrable).lidov76

Thirdly, unlike the orbital energy, the inner angular momentum does not remain
constant but varies with time, because $\tilde{\mathbf{T}}\neq\mathbf{0}$. As
$a=\mathrm{const.}$, the evolution of its magnitude ($J=\sqrt{ma(1-e^{2})}$)
is identical to that of the inner eccentricity. Through $\sin(2\omega)$, it is
subject to a periodic driver,kozairesonance  which becomes more efficient with
increasing inclination (see Eq. (10)). In other words, the eccentricity of
highly inclined orbits oscillate. This is demonstrated in Fig. 2 by numerical
simulations. The top left panel shows the case initialized with
$i=80^{\circ}$: the KL mechanism is very effective, it enhances the
eccentricity significantly. The top right panel exhibits the opposite case,
where KL is very weak due to the low initial inclination ($i=10^{\circ}$). The
bottom panel is a zoom-in version of the top right. The small-amplitude
oscillations superposed on the long-term curves are the results of the inner
and outer orbital motions that we ignore by the orbit-averaging in Eq. (9).
Note that the inclination itself also changes in accord with the eccentricity,
because the two are related by the Kozai constant (see Eq. (15)).

Figure 2: Numerical integration of a hierarchical triple system with
$M=10^{6}$ and $m=10^{3}$ and with initial parameters $a_{1}=1$, $R=100$ and
$e=0.0$ (arbitrary units with the gravitational constant $G=1$). Top left: The
initial inclination is $i=80^{\circ}$. The initially zero inner eccentricity
is pumped up close to unity, i.e., to a very elongated orbit. Top right: The
same set-up but with $i=10^{\circ}$ initially. Bottom: The same as in the top
right panel, but with a 100× zoom-in on the $y$-axis.

The timescale of the oscillation of the orbital elements can be easily
estimated. The subject of the KL effect is the angular momentum: the rate of
its change is given by the double-averaged torque, see Eq. (9). The
characteristic timescale is given by $t_{\mathrm{KL}}\approx J/\dot{J}\approx
J/\tilde{T}$. Since the orbital elements (except $a$) vary with time due to
the torque, they affect the exact value of the timescale. However, $e\in[0,1]$
and the angles are in the arguments of sine and cosine functions, so they
induce variations only of order unity and can be omitted in an order-of-
magnitude formula. Hence

$t_{\mathrm{KL}}\approx\frac{J}{\tilde{T}}\approx\frac{\sqrt{ma}}{Ma^{2}/R^{3}}=\frac{m^{1/2}R^{3}}{Ma^{3/2}}.$
(16)

It is much longer than the outer orbital time, $t_{\mathrm{out}}\approx
M^{-1/2}R^{3/2}$ (i.e. it is secular), because

$\frac{t_{\mathrm{KL}}}{t_{\mathrm{outer}}}=\left(\frac{m}{M}\right)^{1/2}\left(\frac{R}{a}\right)^{3/2}$
(17)

and $1\ll R/a$.

In conclusion, the KL mechanism is a secular phenomenon in the hierarchical
gravitational three-body problem that keeps the semi-major axis constant but
makes the eccentricity and the inclination oscillate. The amplitude of
eccentricity oscillation is most prominent if the perturbing outer object
orbits in a perpendicular plane with respect to the binary.

We note here that the torque in Eq. (9) is not responsible for the evolution
of $\omega$ (the periapsis may precess even in the absence of torques). The
quantity that triggers the variation of $\omega$ could be the time-derivative
of the Runge-Lenz vector, just like the torque is the time-derivative of the
angular momentum vector.

*

##  Appendix A The Kepler equation

The Kepler equation expresses the connection between the eccentric ($E$) and
mean ($l$) anomalies:

$E-e\sin E=l,$ (18)

where $l$ is proportional to the time:

$l=l_{0}+m^{1/2}a^{-3/2}t.$ (19)

Differentiating Eq. (18) with respect to time yields

$(1-e\cos E)\dot{E}=m^{1/2}a^{-3/2},$ (20)

which we can rearrange as

$\mathrm{d}E=\frac{m^{1/2}a^{-3/2}}{1-e\cos E}\mathrm{d}t.$ (21)

###### Acknowledgements.

I thank Bence Kocsis for stimulating discussions. This project has received
funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme under grant agreement No 638435
(GalNUC) and by the Hungarian National Research, Development, and Innovation
Office grant NKFIH KH-125675.

## References

  * (1) M. Valtonen, and H. Karttunen The Three-Body Problem, 1st edition (Cambridge University Press, Cambridge, 2006).
  * (2) J. Masoliver and A. Ros, “Integrability and chaos: the classical uncertainty,” European Journal of Physics 32 (2), 431–458 (2011).
  * (3) N. C. Stone, and Nathan W. C. Leigh, “A statistical solution to the chaotic, non-hierarchical three-body problem,” Nature 576 (7787), 406–410 (2019).
  * (4) V. Szebehely, Theory of orbits. The restricted problem of three bodies, 1st edition (Academic Press, New York, 1967).
  * (5) H. Goldstein, C. Poole, and J. Safko, Classical mechanics, 3rd edition (Addison-Wesley, San Francisco, 2002).
  * (6) Y. Kozai, “Secular perturbations of asteroids with high inclination and eccentricity,” AJ 67, 591–598 (1962).
  * (7) M. L. Lidov, “The evolution of orbits of artificial satellites of planets under theaction of gravitational perturbations of external bodies,” Planetary and Space Science 9 (10), 719–759 (1962).
  * (8) H. von Zeipel, “Sur l’application des series de M. Lindstedt a l’etude du mouvement des cometes periodiques,” Astronomische Nachrichten 183 (22), 345 (1910).
  * (9) T. Ito and K. Ohtsuka, “The Lidov-Kozai Oscillations and Hugo von Zeipel,” MEEP 7, No. 1, 1-113 (2019).
  * (10) S. Naoz, “The Eccentric Kozai-Lidov Effect and Its Applications,” ARA&A 54, 441–489 (2016).
  * (11) B. Katz, S. Dong, and R. Malhotra, “Long-Term Cycling of Kozai-Lidov Cycles: Extreme Eccentricities and Inclinations Excited by a Distant Eccentric Perturber,” PhysRevLett. 107 (18), id.181101 (2011).
  * (12) The eccentricity vector is also known as Laplace or Runge-Lenz vector. For a review on the nomenclature, see H. Goldstein, “More on the prehistory of the Laplce or Runge-Lenz vector,” AJP 44 (11), 1123-1124 (1976).
  * (13) The secular evolution of the Sun-Earth-Moon system under the quadrupole approximation was already explored in V. V. Beletsky’s popular book. If the Moon was on a highly inclined orbit, it would fall onto the Earth within one year. See V. V. Beletsky, Essays on the motion of celestial bodies, 1st edition (Birkhäuser, Basel, 2001). Nevertheless, the history of exploring the long-term behaviour of the Sun-Earth-Moon triple is adventurous, see S. Bodenmann, “The 18th-century battle over lunar motion,” Physics Today 63 (1), 27 (2010).
  * (14) J. D Jackson, Classical electrodynamics, 3rd edition (Wiley, 1998).
  * (15) M. L. Lidov, and S. L. Ziglin, “Non-Restricted Double-averaged Three Body Problem in Hill’s Case,” CeMec. 13 (4), 471–489 (1976).
  * (16) We note that although $\omega$ generally rotates across the $[0,2\pi]$ interval, the more detailed calculation reveals that it may be tuned to librate around $\pm\pi/2$. This is called the Kozai resonance. Nevertheless, this fact does not alter our qualitative picture about the periodic nature of $\mathbf{T}_{\parallel}$.


# On the complexity of the universality and inclusion problems for unambiguous
context-free grammars
(Invited Paper)

Lorenzo Clemente Department of Mathematics, Informatics, and Mechanics
(MIMUW)This work has been partially supported by the Polish NCN grant
2017/26/D/ST6/00201. This is a technical report of an invited paper of the
same title to appear in the proceedings of VPT 2020.University of Warsaw
(Warsaw, Poland<EMAIL_ADDRESS>
###### Abstract

We study the computational complexity of universality and inclusion problems
for unambiguous finite automata and context-free grammars. We observe that
several such problems can be reduced to the universality problem for
unambiguous context-free grammars. The latter problem has long been known to
be decidable and we propose a PSPACE algorithm that works by reduction to the
zeroness problem of recurrence equations with convolution. We are not aware of
any non-trivial complexity lower bounds. However, we show that computing the
coin-flip measure of an unambiguous context-free language, a quantitative
generalisation of universality, is hard for the long-standing open problem
SQRTSUM.

##  1 Introduction

The purpose of this note is to attract attention to a long-standing open
problem in formal language theory. The problem in question is the exact
complexity of deciding universality of unambiguous context-free grammars
(UUCFG). A context-free grammar is _unambiguous_ if every accepted word admits
a unique parse tree, and the universality problems asks, for a given grammar
$G$ over a finite set of terminals $\Sigma$ (alphabet), whether $G$ accepts
every word $L(G)=\Sigma^{*}$. While the universality problem for context-free
grammars is undecidable [20], the same problem for unambiguous grammars is
long-known to be decidable (a corollary of [30, Theorem 5.5]), e.g., by
reducing to the first-order theory of the reals with one quantifier
alternation [30, eq. (3), page 149]. Since the latter fragment is decidable in
EXPTIME [17], this yields an EXPTIME upper bound for UUCFG. No non-trivial
lower bound for UUCFG seems to be known in the literature.

The typical way to solve a containment problem of the form $L\subseteq M$ is
to complement $M$ and solve $L\cap(\Sigma^{*}\setminus M)=\emptyset$. For
instance, when $L$ is regular and $M$ is deterministic context-free (DCFG),
this gives a PTIME procedure since DCFG languages are efficiently closed under
complement and intersection with regular languages, and their emptiness
problem is in PTIME. However, UCFG languages are not closed under complement
(the complement is not even context-free in general [19]), so the language-
theoretic approach is not available. As Salomaa and Soittola remark in their
book from 1978, “no proof is known for Theorem 5.5 which uses only standard
formal language theory”. To this day, we are not aware of a proof of
decidability for UUCFG using different techniques111 In a later book, Kuich
and Salomaa reprove decidability [24, Corollary 16.25] by using variable
elimination, which is arguably closer to algebraic geometry than formal
languages. . The UUCFG problem is not isolated in this respect.

##### State of the art.

Let $\mathcal{A},\mathcal{B}$ be two classes of language acceptors. Examples
include deterministic (DFA), unambiguous (UFA), and nondeterministic finite
automata (NFA), and similarly for context-free grammars we have the classes
DCFG, UCFG, and CFG. The “$\mathcal{A}\subseteq\mathcal{B}$” _inclusion
problem_ asks, given a language acceptor $A$ from $\mathcal{A}$ and $B$ from
$\mathcal{B}$, whether the languages they recognise satisfy $L(A)\subseteq
L(B)$. A summary of decidability and complexity result for inclusion problems
involving finite automata and grammars is presented in Fig. 1. Many entries in
the table are well-known. The problem $\textrm{NFA}\subseteq\textrm{NFA}$ is a
classic PSPACE-complete problem [27]. The problem
$\textrm{UFA}\subseteq\textrm{UFA}$ was shown in PTIME by Stearns and Hunt in
their seminal paper [34]222 An incomparable $\textsf{NC}^{2}$ upper bound for
this problem is also known [26, Fact 4.5] (c.f. [36, Theorem 2]). . The fact
that $\textrm{CFG}\subseteq\textrm{NFA}$ is EXPTIME-complete is somewhat less
known [21, Theorem 2.1]. The inclusion problems
$\mathcal{A}\subseteq\textrm{UFA}$ when $\mathcal{B}$ is DCFG, UCFG, or CFG do
not appear to have been studied before. The $\mathcal{A}\subseteq\mathcal{B}$
problem is undecidable as soon as both $\mathcal{A},\mathcal{B}$ are context-
free grammars, since $\textrm{DCFG}\subseteq\textrm{DCFG}$ is well-known to be
undecidable [20, Theorem 10.7, Point 2]. We have already observed that
$\textrm{NFA}\subseteq\textrm{DCFG}$ is in PTIME. The equivalence problem
$\textrm{NFA}=\textrm{UCFG}$ is shown to be decidable in [30, Theorem 5.5],
although no complexity bound is given. The more general inclusion
$\textrm{NFA}\subseteq\textrm{UCFG}$ does not seem to have been studied
before.

${\subseteq}$ | DFA | UFA | NFA | DCFG | UCFG | CFG
---|---|---|---|---|---|---
DFA | PTIME | PTIME |  PSPACE-c. [27] | PTIME | =UUCFG (Th. 8) | undec.
UFA | PTIME |  PTIME [34] |  PSPACE-c. [27] | PTIME | =UUCFG (Th. 8) | undec.
NFA | PTIME |  PTIME (Th. 7) |  PSPACE-c. [27] | PTIME | =UUCFG (Th. 8) | undec.
DCFG | PTIME |  $\leq$UUCFG (Th. 9) |  EXPTIME-c. [21] | undec. | undec. | undec.
UCFG | PTIME |  $\leq$UUCFG (Th. 9) |  EXPTIME-c. [21] | undec. | undec. | undec.
CFG | PTIME |  $\leq$UUCFG (Th. 9) |  EXPTIME-c. [21] | undec. | undec. | undec.

“$\leq$UUCFG”: the problem reduces in PTIME to UUCFG.

“$=$UUCFG”: the problem is PTIME inter-reducible with UUCFG.

Figure 1: Inclusion problems for various classes of regular and context-free
languages.

##### Contributions.

We establish several connections between inclusion problems
$\mathcal{A}\subseteq\mathcal{B}$ when $\mathcal{B}$ is UFA or UCFG with the
UUCFG problem. Our contributions are as follows.

  1. 1.

We observe that in many cases the inclusion problem $L\subseteq M$ reduces in
polynomial time to the sub-case where $L$ is deterministic (Section 3.1.1).
One application is lower bounds: Once we know that
$\textrm{CFG}\subseteq\textrm{NFA}$ is EXPTIME-hard [21, Theorem 2.1], we can
immediately deduce that the same lower bound carries over to
$\textrm{DCFG}\subseteq\textrm{NFA}$ [21, Theorem 3.1].

  2. 2.

We observe that in many cases the inclusion problem $L\subseteq M$ with $L$
deterministic reduces in polynomial time to the universality problem (Section
3.1.2). One application is upper bounds (combined with the previous point):
For instance, from the fact that $\textrm{UFA}=\Sigma^{*}$ is in PTIME we can
deduce that the more general problem $\textrm{NFA}\subseteq\textrm{UFA}$ is
also in PTIME (Theorem 7), which seems to be a new observation.

  3. 3.

We apply the last two points to show that the following inclusion problems
$\mathcal{A}\subseteq\mathcal{B}$ reduce to UUCFG:
$\mathcal{A}\in\left\\{\textrm{DCFG},\textrm{UCFG},\textrm{CFG}\right\\}$ and
$\mathcal{B}=\textrm{UFA}$ (Theorem 9);
$\mathcal{A}\in\left\\{\textrm{DFA},\textrm{UFA},\textrm{NFA}\right\\}$ and
$\mathcal{B}=\textrm{UCFG}$ (Theorem 8). Since UUCFG is a special instance of
the latter set of problems, they are PTIME inter-reducible with UUCFG.

  4. 4.

We show that UUCFG is in PSPACE (Theorem 10), which improves the EXPTIME upper
bound that can be extracted from [30]. A PSPACE upper bound for the same
problem has also been shown by S. Purgał in his master thesis [29, Section
3.7].

  5. 5.

We complement the upper bound in the previous point by showing that computing
the so-called _coin-flip measure_ of a UCFG (a quantitative problem
generalising universality; c.f. Section 4) is SQRTSUM-hard (Theorem 11). The
latter is a well-known problem in the theory of numerical computation, which
is not known to be in NP or NP-hard [2, 14].

The generic and simple polynomial time reductions of points 1. and 2. above do
not seem to be known in the literature. Beyond the seminal work on UFA [34],
they also apply to very recent contributions on expressive models such as
unambiguous register automata (c.f. [28] for equality atoms) and unambiguous
finite and pushdown Parikh automata [5]. In each of the cases above, one can
reduce from inclusion to universality. A non-example where the reduction
cannot be applied is unambiguous Petri-nets with coverability semantics [9].

The PSPACE upper bound on UUCFG is obtained by reduction to a more general
counting problem interesting on its own. We introduce a natural class of
number sequences ${f:\mathbb{N}\to\mathbb{N}}$ which we call _convolution
recursive_ (conv-rec). Examples include the Fibonacci $F(n+1)=F(n)+F(n-1)$ and
Catalan numbers ${C(n+1)=(C*C)(n)}$, where “$*$” denotes the convolution
product. We show that the function counting the number of words in $L(G)$ of a
given length is conv-rec if $G$ is UCFG. (This result is analogous to the
well-known fact that UCFG have algebraic generating functions [8].) The
_zeroness problem_ asks whether such a sequence is identically zero. Our last
contribution is a complexity upper-bound for the zeroness problem of conv-rec
sequences.

  1. 6.

We show that the zeroness problem of conv-rec sequences is in PSPACE (Theorem
4). We express this problem with a formula in the existential fragment for
first-order logic over the reals, which can be decided in PSPACE [7].

##  2 Convolution recursive sequences and their zeroness problem

##### Convolution recursive sequences.

Let $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, and $\mathbb{R}$ be the sets of
natural, resp., integer, rational, and real numbers. Let
$\mathbb{Q}[x_{\\_}1,\dots,x_{\\_}k]$ denote the ring of polynomials with
coefficients from $\mathbb{Q}$ and variables $x_{\\_}1,\dots,x_{\\_}k$. For
two sequences indexed by natural numbers $f,g:\mathbb{N}\to\mathbb{R}$, their
_sum_ $f+g$ is the sequence $(f+g)(n)=f(n)+g(n)$, and their _convolution_ is
the sequence $(f*g)(n)=\sum_{\\_}{k=0}^{n}f(k)\cdot g(n-k)$. The convolution
operation is associative $f*(g*h)=(f*g)*h$, commutative $f*g=g*f$, has as
(left and right) identity the sequence $1,0,0,\dots$, and distributes over the
sum operation $(f+g)*h=f*g+g*h$. Thus, sequences with the operations “$+$” and
“$*$” form a semiring. Let
$\sigma:(\mathbb{N}\to\mathbb{R})\to(\mathbb{N}\to\mathbb{R})$ be the
_(forward) shift operator_ on sequences, which is defined as $(\sigma
f)(n)=f(n+1)$. The _zeroness_ problem for a sequence
$f:\mathbb{N}\to\mathbb{R}$ amounts to decide whether $f(n)=0$ for every
$n\in\mathbb{N}$.

A _convolution polynomial_ $p(x_{\\_}1,\dots,x_{\\_}k)$ is a polynomial where
the multiplication operation is interpreted as convolution and a constant
$k\in\mathbb{Q}$ is interpreted as the sequence $k,0,0,\dots$. For example,
$4*(x_{\\_}1*x_{\\_}2)+3*(x_{\\_}2*x_{\\_}2)$ is a convolution polynomial of
two variables $x_{\\_}1,x_{\\_}2$. Let
$\mathbb{Q}_{*}[x_{\\_}1,\dots,x_{\\_}k]$ denote the ring of convolution
polynomials with variables $x_{\\_}1,\dots,x_{\\_}k$. A sequence
$f:\mathbb{N}\to\mathbb{R}$ is _convolution recursive_ (_conv-rec_) if there
are $k$ _auxiliary sequences_
$f_{\\_}1,\dots,f_{\\_}k:\mathbb{N}\to\mathbb{R}$ with $f_{\\_}1=f$ and $k$
convolution polynomials
$p_{\\_}1,\dots,p_{\\_}k\in\mathbb{Q}_{*}[x_{\\_}1,\dots,x_{\\_}k]$ s.t.,

$\displaystyle\left\\{\begin{array}[]{lcl}\sigma
f_{\\_}1&=&p_{\\_}1(f_{\\_}1,\dots,f_{\\_}k),\\\ &\vdots&\\\ \sigma
f_{\\_}k&=&p_{\\_}k(f_{\\_}1,\dots,f_{\\_}k).\end{array}\right.$ (4)

The _combined degree_ of the representation above is the sum of the degrees of
$p_{\\_}1,\dots,p_{\\_}k$. For example, the Catalan numbers
$C:\mathbb{N}\to\mathbb{N}$ are conv-rec (of combined degree two) since
$(\sigma C)(n)=(C*C)(n)$.

######  Lemma 1.

Let $f:\mathbb{N}\to\mathbb{R}$ be a conv-rec sequence of combined degree
$\leq d$. Then ${\lim_{\\_}{n\to\infty}\frac{f(n+1)}{f(n)}=O(d)}$.

###### Proof.

The maximal relative growth $\frac{f(n+1)}{f(n)}$ of a conv-rec sequence is
achieved when $f$ satisfies a recurrence of the form $\sigma f={f*\cdots*f}$
($d$ times) for some degree $d\in\mathbb{N}$. If $f(0)=1$, then the resulting
sequence is known as the Fuss-Catalan numbers [16] and it equals $f(n)={d\cdot
n+1\choose n}\frac{1}{d\cdot n+1}$. It can be checked by using Stirling’s
approximation $n!\sim\sqrt{2\pi n}\left(\frac{n}{e}\right)^{n}$ that
$\lim_{\\_}{n\to\infty}\frac{f(n+1)}{f(n)}=\frac{d^{d}}{(d-1)^{d-1}}=d\cdot(1+\frac{1}{d-1})^{d-1}$.
The latter quantity is upper bounded by $d\cdot e$ for every $d\geq 1$. ∎

##### Generatingfunctionology.

The _formal power series_ (a.k.a.  _ordinary generating function_) associated
with a number sequence $a:\mathbb{N}\to\mathbb{R}$ is the infinite polynomial
$g_{\\_}a(x)=\sum_{\\_}{n=0}^{\infty}a(n)\cdot x^{n}$. Let
$[x_{\\_}n]g_{\\_}a$ denote the coefficient $a(n)$ of $x^{n}$ in $g_{\\_}a$.
Let $f,f_{\\_}1,f_{\\_}2:\mathbb{N}\to\mathbb{R}$ be sequences. It is well
known that $g_{\\_}k(x)=k$ for $k\in\mathbb{R}$,
$g_{\\_}{f_{\\_}1+f_{\\_}2}=g_{\\_}{f_{\\_}1}+g_{\\_}{f_{\\_}2}$,
$g_{\\_}{f_{\\_}1*f_{\\_}2}=g_{\\_}{f_{\\_}1}\cdot g_{\\_}{f_{\\_}2}$, and
$g_{\\_}f(x)=f(0)+x\cdot g_{\\_}{\sigma f}(x)$. Consequently, if $f_{\\_}1$ is
conv-recursive with auxiliary sequences $f_{\\_}1,\dots,f_{\\_}k$, then their
generating functions $g_{\\_}{f_{\\_}1},\dots,g_{\\_}{f_{\\_}k}$ satisfy the
following system of polynomial equations

$\displaystyle\left\\{\begin{array}[]{rcl}g_{\\_}{f_{\\_}1}(x)&=&f_{\\_}1(0)+x\cdot\hat{p}_{\\_}1(g_{\\_}{f_{\\_}1}(x),\dots,g_{\\_}{f_{\\_}k}(x)),\\\
&\vdots&\\\
g_{\\_}{f_{\\_}k}(x)&=&f_{\\_}k(0)+x\cdot\hat{p}_{\\_}k(g_{\\_}{f_{\\_}1}(x),\dots,g_{\\_}{f_{\\_}k}(x)).\end{array}\right.$
(8)

where $\hat{p}_{\\_}i$ is the polynomial obtained from the convolution
polynomial $p_{\\_}i$ by replacing the convolution operation “$*$” on
sequences by the product operation “$\cdot$” on real numbers. Thus, the
generating function $g_{\\_}f$ of a conv-rec sequence $f$ is _algebraic_.

######  Lemma 2.

The system of equations (8) has a unique formal power series solution.

###### Proof.

By construction, $g_{\\_}f=(g_{\\_}{f_{\\_}1},\dots,g_{\\_}{f_{\\_}k})$ is a
formal power series solution of (8). We now argue that there is no other
solution. Assume that $g=(g_{\\_}1,\dots,g_{\\_}k)$ is a solution of (8). We
prove that, for every $n\in\mathbb{N}$,
$[x^{n}]g=([x^{n}]g_{\\_}1,\dots,[x^{n}]g_{\\_}1)$ equals
$[x^{n}]g_{\\_}f=([x^{n}]g_{\\_}{f_{\\_}1},\dots,[x^{n}]g_{\\_}{f_{\\_}k})$.
The base case follows immediately from (8), since
$[x^{0}]g_{\\_}i=f_{\\_}i(0)$ by definition. For the inductive step $n>0$,
notice that  1) from (8) we have
$[x^{n}]g_{\\_}i=[x^{n}](x\cdot\hat{p}_{\\_}i(g))=[x^{n-1}]\hat{p}_{\\_}i(g)$,
and  2) the latter quantity is a (polynomial) function of the coefficients
$[x^{i}]g$ for $0\leq i\leq n-1$.  By inductive assumption,
$[x^{i}]g=[x^{i}]g_{\\_}f$ for every $0\leq i\leq n-1$, and thus by the two
observations above $[x^{n}]g=[x^{n}]g_{\\_}f$. ∎

######  Lemma 3.

Let $d$ be the combined degree of $f=(f_{\\_}1,\dots,f_{\\_}k)$. The system
(8) has a unique solution
$g_{\\_}f(x^{*})=(g_{\\_}{f_{\\_}1}(x^{*}),\dots,g_{\\_}{f_{\\_}k}(x^{*}))\in\mathbb{R}^{k}$
for every $0\leq x^{*}<\frac{1}{d}$.

###### Proof.

Let $g_{\\_}f=(g_{\\_}{f_{\\_}1},\dots,g_{\\_}{f_{\\_}k})$ be the tuple of
formal power series of the sequences $f_{\\_}1,\dots,f_{\\_}k$. By Lemma 1,
$\lim_{\\_}{n\to\infty}\frac{f_{\\_}i(n+1)}{f_{\\_}i(n)}=O(d)$. Thus,
$g_{\\_}f(x^{*})=(g_{\\_}{f_{\\_}1}(x^{*}),\dots,g_{\\_}{f_{\\_}k}(x^{*}))\in\mathbb{R}^{k}$
converges for every $0\leq x^{*}<\frac{1}{d}$. By Lemma 2, $g_{\\_}f$ is the
unique formal power series solution of (8). ∎

######  Theorem 4.

The zeroness problem for conv-rec sequences is in PSPACE.

###### Proof.

Let $f_{\\_}1$ be a conv-rec sequence of combined degree $d$ with auxiliary
sequences $f_{\\_}2,\dots,f_{\\_}k$ satisfying (4). Consider the associated
generating functions $g=(g_{\\_}{f_{\\_}1},\dots,g_{\\_}{f_{\\_}k})$. Clearly,
$f_{\\_}1(n)=0$ for every $n\in\mathbb{N}$ if, and only if,
$g_{\\_}{f_{\\_}1}(x)=0$ for every $x$ sufficiently small. By Lemma 3,
$g(x^{*})$ is the unique solution of (8) for every $0\leq x^{*}<\frac{1}{d}$.
It thus suffices to say that, for every $0\leq x^{*}<\frac{1}{d}$, _all_
solutions $g(x^{*})$ of the system (8) satisfy $g_{\\_}{f_{\\_}1}(x^{*})=0$.
This can be expressed by the following universal first-order sentence over the
reals (where $\bar{y}=(y_{\\_}1,\dots,y_{\\_}k)$)

$\displaystyle\forall\left(0\leq
x<\frac{1}{d}\right){\;.\;}\forall\bar{y}{\;.\;}\bar{y}=f(0)+x\cdot\hat{p}(\bar{y})\to
y_{\\_}1=0.$

The sentence above can be decided in PSPACE by appealing to the existential
theory of the reals [7, Theorem 3.3]. ∎

##  3 Universality of unambiguous grammars

Let $\Sigma$ be a finite alphabet. We denote by $\Sigma^{*}$ the set of all
finite words over $\Sigma$, including the empty word $\varepsilon$. A
_language_ is a subset $L\subseteq\Sigma^{*}$. The concatenation of two
languages $L,M\subseteq\Sigma^{*}$ is _unambiguous_ if $w\in L\cdot M$ implies
that $w$ factors uniquely as $w=u\cdot v$ with $u\in L$ and $M\in v$. A
_context-free grammar_ (CFG) is a tuple $G=(\Sigma,N,S,{\leftarrow})$ where
$\Sigma$ is a finite alphabet of _terminal symbols_ , $N$ is a finite set of
_nonterminal symbols_ , of which $S\in N$ is the _starting nonterminal symbol_
, and ${\leftarrow}\subseteq N\times(N\cup\Sigma)^{*}$ is a set of
productions. A CFG is in _short Greibach normal form_ if productions are of
the form either $X\leftarrow\varepsilon$. or $X\leftarrow aYZ$. An _$X$
-derivation tree_ is a tree satisfying the following conditions: 1) the root
node $\varepsilon$ is labelled by the nonterminal $X\in X$, 2) every internal
node is labelled by a nonterminal from $N$, 3) whenever a node $u$ has
children $u\cdot 1,\dots,u\cdot k$ there exists a rule $Y\leftarrow
w_{\\_}1\cdots w_{\\_}k$ with $w_{\\_}i\in N\cup\Sigma$ s.t. $Y$ is the label
of $u$ and $w_{\\_}i$ is the label of $u\cdot i$, and 4) leaves are labelled
with terminal symbols from $\Sigma$. The _language recognised_ by a
nonterminal $X$ is the set $L(X)$ of words $w=a_{\\_}1\cdots
a_{\\_}n\in\Sigma$ s.t. there exists an $X$-derivation tree with leaves
labelled by (left-to-right) $a_{\\_}1,\dots,a_{\\_}n$; the language recognised
by $G$ is the language recognised by the starting nonterminal $L(G)=L(S)$. A
CFG $G$ is _unambiguous_ (UCFG) if for every accepted word $w\in L(G)$ there
exists exactly one derivation tree witnessing its acceptance. The universality
problem (UUCFG) asks, given a UCFG $G$, whether $L(G)=\Sigma^{*}$.

###  3.1 Reductions

In this section present PTIME reductions from inclusion problems for NFA and
UCFG to UUCFG. This serves us as a motivation to study the complexity of UUCFG
in Section 3.2. We proceed in two steps. In the first step, we present a
general l.h.s. determinisation procedure for inclusion problems (Section
3.1.1) which is widely applicable to essentially any machine-based model of
computation. In the second step, assuming a deterministic l.h.s., we show a
reduction from inclusion to universality (Section 3.1.2). We apply these two
reductions in Section 3.1.3.

####  3.1.1 L.h.s. determinisation for inclusion problems

It is an empirical observation that in many inclusion problems of the form
$L\subseteq M$ the major source of difficulty is with $M$ and not with $L$.
For example, for finite automata the inclusion problem is PSPACE-complete when
$M$ is presented by a NFA and in NLOGSPACE when it is presented by a DFA. In
either case, it is folklore that whether $L$ is presented as a NFA or DFA does
not matter. A more dramatic example is given when $L$ is regular and $M$
context-free, since the inclusion above is undecidable when $M$ is presented
by a CFG and in PTIME when it is presented by a DCFG.

In this section we give a formal explanation of this phenomenon by providing a
generic reduction of an inclusion problem as above to one where the l.h.s. $L$
is a deterministic language. The reduction will be applicable under mild
assumptions which are satisfied by most machine-based models of language
acceptors such as finite automata, Büchi automata, context-free
grammars/pushdown automata, Petri-nets, register automata, timed automata,
etc. For the language class of the r.h.s. $M$ it suffices to have closure
under inverse homomorphic images, and for the l.h.s. $L$ it suffices that we
can rename the input symbols read by transitions in a suitable machine
model333The reduction applies also to undecidable instances of the language
inclusion problem such as $\textrm{CFG}\subseteq\textrm{DCFG}$, however in
this case it is of no use since $\textrm{DCFG}\subseteq\textrm{DCFG}$ is known
to be undecidable [20, Theorem 10.7, Point 2].. Moreover, we argue that such
transformation preserves whether $M$ is recognised by a deterministic or an
unambiguous machine.

Let $\Sigma$ be a finite alphabet444The construction below can easily be
adapted to infinite alphabets of the form $\Sigma\times\mathbb{A}$, where
$\Sigma$ is finite and $\mathbb{A}$ is an infinite set of data values [4]..
Assume that $L=L(A)\subseteq\Sigma^{*}$ is recognised555Languages of infinite
words can be handled similarly. by a nondeterministic machine $A$ with
transitions of the form
$\delta=p\xrightarrow{a,\mathsf{op}}q\in\Delta_{\\_}A$, where $\mathsf{op}$ is
an optional operation that manipulates a local data structure (a stack, queue,
a tape of a Turing machine, etc…). The construction below does not depend on
what $\mathsf{op}$ does. We assume w.l.o.g. that $A$ is _total_ , i.e., for
every control location $p$ and input symbol $a\in\Sigma$ there exists a
transition of the form $p\xrightarrow{a,\\_}\\_\in\Delta_{\\_}A$. Consider a
new alphabet $\Sigma^{\prime}=\Delta_{\\_}A$, together with the projection
homomorphism $h:\Sigma^{\prime}\to\Sigma$ that maps a transition
$\delta=p\xrightarrow{a,\mathsf{op}}q\in\Delta_{\\_}A$ to its label
$h(\delta)=a\in\Sigma$. We modify $A$ into a new machine $A^{\prime}$ by
replacing each transition $\delta$ above with
$p\xrightarrow{\delta,\mathsf{op}}q\in\Delta_{\\_}{A^{\prime}}$. Intuitively,
$A^{\prime}$ behaves like $A$ except that it needs to declare which transition
$\delta$ it is actually taking in order to read $a=h(\delta)$. By
construction, $A^{\prime}$ is deterministic (in fact, every transition has a
unique label across the entire machine) and $L(A)=h(L(A^{\prime}))$ is the
homomorphic image of $L(A^{\prime})$.

We need to adapt the machine $B$ recognising $M=L(B)$ in order to preserve
inclusion. For every transition
$r\xrightarrow{a,\mathsf{op}}s\in\Delta_{\\_}B$ and for every
$\delta=p\xrightarrow{b,\mathsf{op}^{\prime}}q\in\Delta_{\\_}A$ with $b=a$, we
have in $B^{\prime}$ a transition
$r\xrightarrow{\delta,\mathsf{op}}s\in\Delta_{\\_}{B^{\prime}}$. Intuitively,
$B^{\prime}$ behaves like $B$ except that it reads additional information on
the transition taken by $A^{\prime}$. This information is not actually used by
$B^{\prime}$ during its execution but it is merely added in order to lift the
alphabet from $\Sigma$ to $\Sigma^{\prime}$. We have
$L(B^{\prime})=h^{-1}(L(B))$ is the inverse homomorphic image of $L(B)$. The
following lemma states the correctness of the reduction.

######  Lemma 5.

We have the following equivalence: $L(A)\subseteq L(B)\textrm{ if, and only
if, }L(A^{\prime})\subseteq L(B^{\prime}).$

###### Proof.

By generic properties of images and inverse images we have the following two
inclusions:

$\displaystyle L(A^{\prime})\subseteq h^{-1}(h(L(A^{\prime})))\quad\textrm{
and }\quad h(h^{-1}(L(B)))\subseteq L(B).$ (9)

For the “only if” direction, if $L(A)\subseteq L(B)$ holds, then
$h^{-1}(L(A))\subseteq h^{-1}(L(B))$, which, by the definition of $A^{\prime}$
and $B^{\prime}$, is the same as $h^{-1}(h(L(A)))\subseteq L(B^{\prime})$. By
(9), $L(A^{\prime})\subseteq h^{-1}(h(A^{\prime}))\subseteq L(B^{\prime})$, as
required. For the “if” direction, if $L(A^{\prime})\subseteq L(B^{\prime})$
holds, then also $h(L(A^{\prime}))\subseteq h(L(B^{\prime}))$ holds. Similarly
as above, we have $L(A)=h(L(A^{\prime}))\subseteq
h(L(B^{\prime}))=h(h^{-1}(L(B)))\subseteq L(B)$, as required. ∎

The following lemma states that the reduction above preserves whether $B$ is
deterministic or unambiguous. We mean here the following generic semantic
notion of unambiguity: $B$ is _unambiguous_ if for every $w\in\Sigma^{*}$,
there exists at most one accepting run of $B$ over $w$. (This notion
specialises to the classical notion of unambiguity of finite automata,
pushdown automata, Parikh automata, etc.)

######  Lemma 6.

If $B$ is deterministic, then so is $B^{\prime}$. If $B$ is unambiguous, then
so is $B^{\prime}$.

###### Proof.

A transition $p\xrightarrow{\delta,\mathsf{op}}q\in\Delta_{\\_}{B^{\prime}}$
in $B^{\prime}$ is obtained taking several distinct copies of a transition
${p\xrightarrow{a,\mathsf{op}}q\in\Delta_{\\_}B}$ in $B$ w.r.t. every possible
transition $\delta\in\Delta_{\\_}A$ over the same input symbol $h(\delta)=a$.
By way of contradiction, assume that $B$ is deterministic and that
$B^{\prime}$ is not deterministic. There are two distinct transitions
$p\xrightarrow{\delta,\mathsf{op}_{\\_}1}q_{\\_}1,p\xrightarrow{\delta,\mathsf{op}_{\\_}2}q_{\\_}2\in\Delta_{\\_}{B^{\prime}}$
in $B^{\prime}$ from the same control location $p$ and input
$\delta\in\Sigma^{\prime}$. If $\delta$ is labelled by $h(\delta)=a\in\Sigma$,
then by construction there are two distinct transitions
$p\xrightarrow{a,\mathsf{op}_{\\_}1}q_{\\_}1,p\xrightarrow{a,\mathsf{op}_{\\_}2}q_{\\_}2\in\Delta_{\\_}B$
in $B$ over the same input symbol $a$. This contradicts the fact that $B$ was
assumed to be deterministic, and thus $B^{\prime}$ must be deterministic as
well. An analogous argument shows that also unambiguity is preserved. ∎

####  3.1.2 From inclusion to universality

Let $\mathcal{L}$ and $\mathcal{M}$ be two classes of languages and let
$L\in\mathcal{L}$ and $M\in\mathcal{M}$. A naive approach to decide the
inclusion problem (and the most common) is to use the following equivalence:

$\displaystyle L\subseteq M\quad\textrm{ if, and only if, }\quad
L\cap(\Sigma^{*}\setminus M)=\emptyset.$ (10)

However, this requires complementation of $M$, which is either expensive
(exponential complexity for NFA) or just impossible (context-free languages
are not closed under complemenetation, even for the unambiguous subclass
[19]). However, we observe the following related reduction which works much
better in our setting:

$\displaystyle L\subseteq M\quad\textrm{ if, and only if, }\quad(M\cap
L)\;\cup\;(\Sigma^{*}\setminus L)=\Sigma^{*}.$ (11)

On the face of it, this looks more complicated than (10) because we now have
to perform a complementation (of $L$), an intersection, a union, and finally
we reduce to the universality problem instead of the nonemptiness, which is
still difficult in general. However, in our setting there are gains. First of
all, thanks to Section 3.1.1 we can assume that $L$ is a deterministic
language, and thus complementation is usually available (and cheap). Second,
while universality is still a difficult problem, it can be easier than
inclusion, e.g., DCFG inclusion is undecidable while DCFG universality is
decidable (even in PTIME).

In order to apply (11) we require that $\mathcal{L}$ is a deterministic class
efficiently closed under complement (i.e., a representation for the complement
is constructible in PTIME) and that the class $\mathcal{M}$ is closed under
disjoint unions and intersections with languages from $\mathcal{L}$. Most
deterministic languages classes, such as those recognised by deterministic
finte automata, deterministic context-free grammars, deterministic Parikh
automata, deterministic register automata, etc., satisfy the first
requirement666 A notable exception is deterministic Petri-net languages under
coverability semantics, since the complement of such languages intuitively
requires checking whether some counter is negative, which is impossible
without zero tests. In fact, if both a language and its complement are
deterministic Petri-net recognisable under coverability semantics, then they
are both regular [10]. . The second requirement is satisfied for classes of
languages for which the underlying machine models admit a product
construction777 As an example not satisfying this requirement, one can take
$\mathcal{L}=\mathcal{M}$ to be the class of DCFL, since they are not closed
under intersection. In fact, while we show in this paper that UUCFG is
decidable, the equivalence problem for UCFG is open. .

####  3.1.3 Applications

In this section we apply the reductions of Section 3.1.1 and Section 3.1.2 in
order to reduce certain inclusion problems to their respective universality
variant.

######  Theorem 7.

“$\textrm{NFA}\subseteq\textrm{UFA}$” is in PTIME.

While equivalence and inclusion of UFA is well-known to be in PTIME [34,
Corollary 4.7], the same complexity for the more general problem
“$\textrm{NFA}\subseteq\textrm{UFA}$” does not seem to have been observed
before.

###### Proof.

By Section 3.1.1, the problem reduces to
“$\textrm{DFA}\subseteq\textrm{UFA}$”. By (11), $L\subseteq M$ is equivalent
to $N:=M\cap L\cup(\Sigma^{*}\setminus L)=\Sigma^{*}$. Notice that $N$ is
effectively UFA, since the DFA language $L$ can be complemented in PTIME, the
intersection $M\cap L$ is also UFA and computable in quadratic time, and the
disjoint union of a UFA and a DFA is also a UFA computable in linear time.
Since the universality problem for unambiguous automata can be solved in
PTIME, also “$\textrm{DFA}\subseteq\textrm{UFA}$”, and thus
“$\textrm{NFA}\subseteq\textrm{UFA}$”, is in PTIME as well. ∎

######  Theorem 8.

“$\textrm{NFA}\subseteq\textrm{UCFG}$” is PTIME inter-reducible with UUCFG.

###### Proof.

By Section 3.1.1, the problem reduces to
“$\textrm{DFA}\subseteq\textrm{UCFG}$”. Thanks to Section 3.1.2, the latter
problem reduces to UUCFG since 1) DFA languages are efficiently closed under
complement (in PTIME), 2) UCFG languages are efficiently closed under
intersection with DFA languages (in PTIME), and 3) the disjoint union of a
UCFG language and a DFA language is a UCFG language. Thus,
“$\textrm{NFA}\subseteq\textrm{UCFG}$” reduces to UUCFG, and since UUCFG is a
special case of the former problem, “$\textrm{NFA}\subseteq\textrm{UCFG}$” is
PTIME inter-reducible with UUCFG. ∎

######  Theorem 9.

“$\textrm{CFG}\subseteq\textrm{UFA}$” reduces to UUCFG.

###### Proof.

By Section 3.1.1, “$\textrm{CFG}\subseteq\textrm{UFA}$” reduces to
“$\textrm{DCFG}\subseteq\textrm{UFA}$”, which in turn reduces to UUCFG thanks
to Section 3.1.2 because 1) DCFG languages are efficiently closed under
complement, 2) the intersection of a UFA and a DCFG language is efficiently
DCFG, and 3) the disjoint union of two DCFG languages is efficiently UCFG.
(The latter problem reduces to universality of two disjoint DCFG languages,
which in principle may be easier than UUCFG.) ∎

###  3.2 UUCFG in PSPACE

In this section we show that UUCFG is in PSPACE by reducing to the zeroness
problem for conv-rec sequences. This complexity upper bound appears also in
[29], albeit with a more direct argument reducing to systems of monotone
polynomial equations.

Let $\Sigma=\left\\{a,b\right\\}$ be a finite alphabet and let
$L\subseteq\Sigma^{*}$ be a language of finite words over $\Sigma$. The
_counting function_ of $L$ is the sequence $f_{\\_}L:\mathbb{N}\to\mathbb{N}$
s.t. for every $n\in\mathbb{N}$, $f_{\\_}L(n)=|L\cap\Sigma^{n}|$ counts the
number of words of length $n$ in $L$. Given a unambiguous context-free grammar
$G=(\Sigma,N,S,\leftarrow)$ in short Greibach normal form, let
$f_{\\_}X:=f_{\\_}{L(X)}:\mathbb{N}\to\mathbb{N}$ be the counting function of
the language $L(X)$ recognised by the nonterminal $X\in N$. It is well-known
that the $f_{\\_}X$’s satisfy the following system of equations with
convolution:

$\displaystyle f_{\\_}X(n+1)=\sum_{\\_}{X\leftarrow
aYZ}(f_{\\_}Y*f_{\\_}Z)(n).$ (12)

The initial condition is $f_{\\_}X(0)=1$ if $X\leftarrow\varepsilon$ and
$f_{\\_}X(0)=0$ otherwise. In other words, $f_{\\_}S$, which is the counting
function of the language $L(G)$ recognised by $G$, is conv-rec. Unambiguity is
used crucially to show that any word $w$ in $L(Y\cdot Z)$ factorises uniquely
as $w=u\cdot v$ with $u\in L(Y)$ and $v\in L(Z)$, which allows us to obtain
$f_{\\_}{L(Y\cdot Z)}=f_{\\_}{L(Y)}*f_{\\_}{L(Z)}$.

Clearly, $G$ is universal if, and only if, $f_{\\_}S$ is identically equal to
the sequence $g(n)=2^{n}$. The latter sequence is conv-rec since it satisfies
$g(n+1)=(g*g)(n)$, with the initial condition $g(0)=1$. Thus $G$ is universal
if, and only if, $f(n)=g(n)-f_{\\_}S(n)$ is identically zero. Since conv-rec
sequences are closed under subtraction, $f(n)$ is also conv-rec. By Theorem 4,
we can decide zeroness of $f$ in PSPACE, and thus the same upper bound holds
for UUCFG.

######  Theorem 10.

The universality problem for unambiguous context-free grammars UUCFG is in
PSPACE.

##  4 SQRTSUM-hardness of coin-flip measure

In this section we show that a quantitative generalisation of UUCFG is hard
for a well-known problem in numerical computing. Let
$\Sigma_{\\_}n=\left\\{a_{\\_}1,\dots,a_{\\_}n\right\\}$ be a finite alphabet
of $n$ distinct letters. Consider the following random process to generate a
finite word in $\Sigma^{*}$. At step $k$ we select one option
$a_{\\_}k\in\Sigma_{\\_}\varepsilon=\Sigma_{\\_}n\cup\left\\{\varepsilon\right\\}$
uniformly at random. If $a_{\\_}k=\varepsilon$, then we terminate and we
produce in output $a_{\\_}0\cdots a_{\\_}{k-1}$. Otherwise, we continue to the
next step $k+1$. It is easy to see that the probability to generate a word
depends only on its length and equals
$\mu_{\\_}\text{coin}(w)=\left(\frac{1}{|\Sigma|+1}\right)^{|w|+1}$. The
_coin-flip measure_ of a language of finite words $L\subseteq\Sigma^{*}$ is
$\mu_{\\_}\text{coin}(L)=\sum_{\\_}{w\in L}\mu_{\\_}\text{coin}(w).$ Clearly,
$0\leq\mu_{\\_}\text{coin}(L)\leq 1$, $\mu_{\\_}\text{coin}(L)=0$ iff
$L=\emptyset$, and $\mu_{\\_}\text{coin}(L)=1$ iff $L=\Sigma^{*}$.

Since $\mu_{\\_}\text{coin}(w)$ depends just on $\left|w\right|$, we can write
$\mu_{\\_}\text{coin}(L)=\sum_{\\_}{k=0}^{\infty}f_{\\_}L(k)\cdot\left(\frac{1}{n+1}\right)^{k+1}$,
where $f_{\\_}L(k)=\left|L\cap\Sigma^{k}\right|$ is the counting function of
$L$. In other words, one possible way of computing the coin-flip measure it by
evaluating the generating function $g_{\\_}{f_{\\_}L}(x)$ at $x=\frac{1}{n+1}$
(modulo a correction factor): $\mu_{\\_}\text{coin}(L)=\frac{1}{n+1}\cdot
g_{\\_}{f_{\\_}L}\left(\frac{1}{n+1}\right)$. Consequently, the coin-flip
measure of a regular language is rational, and that of an unambiguous context-
free language is algebraic (following from the analogous, and more general,
facts about the respective generating functions [8]). Let
$L,M\subseteq\Sigma_{\\_}n^{*}$ be two languages with unambiguous
concatenation $L\cdot M$. Then

$\displaystyle\mu_{\\_}\text{coin}(L\cdot
M)=(n+1)\cdot\mu_{\\_}\text{coin}(L)\cdot\mu(M).$ (13)

The _coin-flip comparison problem_ asks, given a language
$L\subseteq\Sigma^{*}$, a rational threshold $0\leq\varepsilon\leq 1$ encoded
in binary, and a comparison operator
${\sim}\in\left\\{\leq,<,>,\geq\right\\}$, whether
$\mu_{\\_}\text{coin}(L)\sim\varepsilon$ holds. The universality problem for
$L$ is the special case when $\varepsilon=1$. We now relate the coin-flip
comparison problem to an open problem in numerical computing. The _SQRTSUM
problem_ asks, given $d_{\\_}0,\dots,d_{\\_}n\in\mathbb{N}$ encoded in binary
and a comparison operator ${\sim}\in\left\\{{\leq},{<},{>},{\geq}\right\\}$,
whether 888 In fact, the problem reduces to the case when ${\sim}={\geq}$ is
fixed. By doing binary search in the interval $\left\\{0,1,\dots,n\cdot
d\right\\}$, with only $O(\log(n\cdot d))$ queries to (14) we can find the
unique $\hat{d}_{\\_}0\in\mathbb{N}$ s.t.
$\hat{d}_{\\_}0\leq\sum_{\\_}{i=1}^{n}\sqrt{d_{\\_}i}\leq\hat{d}_{\\_}0+1$. We
can then solve $\sum_{\\_}{i=1}^{n}\sqrt{d_{\\_}i}\leq d_{\\_}0$ by checking
$d_{\\_}0\leq\hat{d}_{\\_}0+1$, and similarly for the other comparison
operators. :

$\displaystyle\sum_{\\_}{i=1}^{n}\sqrt{d_{\\_}i}\sim d_{\\_}0.$ (14)

This problem can be shown to be in PSPACE by deciding the existential formula
$\exists x_{\\_}1,\dots,x_{\\_}n{\;.\;}x_{\\_}1^{2}=d_{\\_}1\land\cdots\land
x_{\\_}n^{2}=d_{\\_}n\land x_{\\_}1+\cdots+x_{\\_}n\sim d_{\\_}0$ over the
reals [7]. It is a long-standing open problem in the theory of numerical
computation whether SQRTSUM is in NP, or whether it is NP-hard [2, 14].

######  Theorem 11.

The coin-flip measure comparison problem is SQRTSUM-hard for UCFG.

In the rest of the section we prove the theorem above. Let
$d_{\\_}0,\dots,d_{\\_}n\in\mathbb{N}$ be the input to SQRTSUM. We assume
w.l.o.g. that $n$ is an odd number $\geq 3$. We construct a rational constant
$\varepsilon\in\mathbb{Q}$ and a UCFG
${G=(\Sigma_{\\_}n,N,X_{\\_}0,\leftarrow)}$ over a $n$-ary alphabet
$\Sigma_{\\_}n=\left\\{a_{\\_}1,\dots,a_{\\_}n\right\\}$ and nonterminals $N$
containing
$\left\\{X_{\\_}0,\dots,X_{\\_}n,C_{\\_}1,\dots,C_{\\_}n,A\right\\}$ plus some
auxiliary nonterminals (omitted for readability) s.t.
$\mu_{\\_}\text{coin}(L(G))\sim\varepsilon$ if, and only if, (14) holds. The
principal productions of the grammar are:

$\displaystyle X_{\\_}0$ $\displaystyle\leftarrow a_{\\_}1\cdot
X_{\\_}1\mid\cdots\mid a_{\\_}n\cdot X_{\\_}n,$ $\displaystyle X_{\\_}1$
$\displaystyle\leftarrow C_{\\_}1\mid A\cdot X_{\\_}1\cdot a_{\\_}n\cdot
X_{\\_}1,$ $\displaystyle\vdots$ $\displaystyle X_{\\_}n$
$\displaystyle\leftarrow C_{\\_}n\mid A\cdot X_{\\_}n\cdot a_{\\_}n\cdot
X_{\\_}n.$

The remaining nonterminals $C_{\\_}i$’s and $A$ will generate certain regular
languages to be determined below. Let $d=\max_{\\_}{i=1}^{n}d_{\\_}i$. For
every $1\leq i\leq n$, let $x_{\\_}i=1-\frac{\sqrt{d_{\\_}i}}{d}$. It is easy
to check that $x_{\\_}i$ is the least non-negative solution of

$\displaystyle x_{\\_}i$ $\displaystyle=c_{\\_}i+a\cdot
x_{\\_}i^{2}\quad\text{where
}c_{\\_}i:=\frac{1}{2}\left(1-\frac{d_{\\_}i}{d^{2}}\right)\text{ and
}a:=\frac{1}{2}.$ (15)

In the following, we write $\mu(X)$ for a non-terminal $X\in N$ as a shorthand
for $\mu_{\\_}\text{coin}(L(X))$. Since
$\mu(a_{\\_}1)=\cdots=\mu(a_{\\_}n)=\frac{1}{(n+1)^{2}}$, by (13) we have

$\displaystyle\mu(X_{\\_}0)=\frac{1}{n+1}(\mu(X_{\\_}1)+\cdots+\mu(X_{\\_}n))\text{
and
}\mu(X_{\\_}i)=\mu(C_{\\_}i)+(n+1)\cdot\mu(A)\cdot\mu(X_{\\_}i)^{2},i\in\left\\{1,\dots,n\right\\}.$
(16)

We aim at obtaining $\mu(X_{\\_}i)=x_{\\_}i$. By comparing (16) with (15) we
deduce that the nonterminals $C_{\\_}i$ and $A$ must generate languages of
measure $\mu(C_{\\_}i)=c_{\\_}i$, resp.,
$\mu(A)=\frac{a}{n+1}=\frac{1}{2(n+1)}$. Since the measures $a,c_{\\_}i$ are
rational, it suffices to find regular languages $L(A),L(C_{\\_}i)$. The main
difficulty is to define these language as to ensure that $G$ is unambiguous
and of polynomial size. In order to achieve this we further require that  1)
$L(A)\subseteq\Sigma_{\\_}{n-1}$is a finite set of words of length $1$ (single
letters) not containing letter $a_{\\_}n$, and  2)
$L(C_{\\_}i)\subseteq\Sigma_{\\_}{n-1}^{*}$is a set of words not containing
letter $a_{\\_}n$.

We first define $L(A)$. Let

$\displaystyle A\leftarrow a_{\\_}1\mid\cdots\mid a_{\\_}{\frac{n+1}{2}}.$

In order to avoid letter $a_{\\_}n$, we require $\frac{(n+1)}{2}\leq n-1$. The
latter condition is satisfied since we assumed $n\geq 3$. Thus,
$L(A)\subseteq\Sigma_{\\_}{n-1}$ is finite, contains only words of length $1$,
and has measure $\mu(A)=\frac{n+1}{2}\cdot\frac{1}{(n+1)^{2}}=\frac{a}{n+1}$,
as required.

The definition of $L(C_{\\_}i)$ of measure $\mu(C_{\\_}i)=c_{\\_}i$ is more
involved. In general, it is easy to construct a regular expression (or a
finite automaton) recognising a language of measure equal to a given rational
number. However, we have two constraints to respect:  1) we can use only
letters from $\Sigma_{\\_}{n-1}$, and  2) the regular expression must have
size polynomial in the bit encoding of $c_{\\_}i$.  The first constraint
entails an upper bound $\mu(\Sigma_{\\_}{n-1}^{*})=\frac{1}{2}$ on the maximal
measure that $L(C_{\\_}i)$ can have. However, this is not a problem in our
case since $c_{\\_}i<\frac{1}{2}$ by definition. The second constraint is
handled by the following lemma.

######  Lemma 12 (Representation lemma).

Let $n+1\in\mathbb{N}$ with $n\geq 2$ be a base, let $m\in\mathbb{N}$ s.t.
$1\leq m\leq n$, and let $c\in\mathbb{R}$ with $0\leq c\leq\frac{1}{n-m+1}$ be
a target rational measure written in reduced form as $c=\frac{p}{q},\textrm{
with }p,q\in\mathbb{N},\ p\leq q$. There exists an unambiguous regular
expression $e$ using only letters from $\Sigma_{\\_}m\subseteq\Sigma_{\\_}n$
recognising a language of measure $\mu(L(e))=c$. Moreover, if there exists
$\ell\in\mathbb{N}$ s.t. $q\,|\,(n+1)^{\ell}$, then $e$ can be taken of size
polynomial in $\log q$, $n$, and $\ell$.

We apply Lemma 12 with $m:=n-1$ and $c:=c_{\\_}i$ and obtain an unambiguous
regular expression $e$ recognising a language
$L(e)\subseteq\Sigma_{\\_}{n-1}^{*}$ of measure $c_{\\_}i$. We now argue that
$e$ can be taken of polynomial size. In order to achieve this, we assume
w.l.o.g. that $d=(n+1)^{2h}$ for some $h$. (This can be ensured by adding a
new integer $d_{\\_}{n+1}=(n+2)^{2h}$ for some $h$ large enough, and by
replacing $d_{\\_}0$ with $d_{\\_}0+\sqrt{d_{\\_}{n+1}}=d_{\\_}0+(n+2)^{h}$.)
Consequently,
$c_{\\_}i=\frac{\frac{d}{2}(d^{2}-d_{\\_}i)}{(n+1)^{4h}}=\frac{p}{q}$ with
$p,q\in\mathbb{N}$ relatively prime and $q\,|\,(n+1)^{4h}$, and thus $e$ has
polynomial size by taking $\ell=4h$ in the lemma. The set of polynomially many
production rules for nonterminal $C_{\\_}i$ is derived immediately from the
regular expression $e$ by adding some auxiliary nonterminals. Moreover, since
$e$ is unambiguous, the same applies to the rules for $C_{\\_}i$. This
completes the description of the grammar $G$.

######  Lemma 13.

The grammar $G$ is unambiguous.

###### Proof.

Since $L(G)=L(X_{\\_}0)$ is the union of languages $L(a_{\\_}1\cdot
X_{\\_}1),\dots,L(a_{\\_}n\cdot X_{\\_}n)$, and the latter are disjoint, it
suffices to show that the $L(X_{\\_}i)$’s are recognised unambiguously. Let
$w\in L(X_{\\_}i)$. If $w$ does not contain any $a_{\\_}n$, then necessarily
$w\in L(C_{\\_}i)$. Otherwise, let $w=ua_{\\_}nv$ where $v$ does not contain
any $a_{\\_}n$. Thus $v\in L(C_{\\_}i)$ and $u\in L(A\cdot X_{\\_}i)$. Since
$A$ produces only words of fixed length, $u=xw^{\prime}$ unambiguously with
$x\in A$ and $w^{\prime}\in L(X_{\\_}i)$. This argument shows that for any
$w\in L(X_{\\_}i)$ if we let $s$ be the number of $a_{\\_}n$ in $w$, then
$w\in L(A^{s}\cdot C_{\\_}i\cdot(a_{\\_}n\cdot C_{\\_}i)^{s})$. Since $A$
produces words of fixed length and $C_{\\_}i$ does not produce any word
containing $a_{\\_}n$, the latter concatenation is unambiguous and thus $w$ is
produced unambiguously by $X_{\\_}i$. ∎

Let $\varepsilon:=\frac{1}{n+1}\left(n-\frac{d_{\\_}0}{d}\right)$. The
following lemma states the correctness of the reduction.

######  Lemma 14.

We have $\mu(L(G))\sim\varepsilon$ if, and only if, (14) holds.

###### Proof.

Since $x_{\\_}i=1-\frac{\sqrt{d_{\\_}i}}{d}$, we have
$\mu(X_{\\_}0)=\mu(a_{\\_}1\cdot X_{\\_}1)+\cdots+\mu(a_{\\_}n\cdot
X_{\\_}n)=(n+1)(\mu(a_{\\_}1)\cdot\mu(X_{\\_}1)+\cdots+\mu(a_{\\_}n)\cdot\mu(X_{\\_}n))=\frac{1}{n+1}(\mu(X_{\\_}1)+\cdots+\mu(X_{\\_}n))=\frac{1}{n+1}(x_{\\_}1+\cdots+x_{\\_}n)=\frac{1}{n+1}\left(\left(1-\frac{\sqrt{d_{\\_}1}}{d}\right)+\cdots+\left(1-\frac{\sqrt{d_{\\_}n}}{d}\right)\right)=\frac{1}{n+1}\left(n-\frac{\sqrt{d_{\\_}1}+\cdots+\sqrt{d_{\\_}n}}{d}\right)$,
and thus $\sum_{\\_}{i=1}^{n}\sqrt{d_{\\_}i}\sim d_{\\_}0$ if, and only if,
$\mu(L(X))\sim\varepsilon$, as required. ∎

##  5 Discussion

We have shown novel PSPACE upper bounds for several inclusion problems on UCFG
and finite automata. We did not address language equivalence problems $L=M$,
which in principle can be easier to decide than the corresponding inclusions.
For instance, while $\textrm{DCFG}\subseteq\textrm{DCFG}$ is undecidable [20,
Theorem 10.7, Point 2], $\textrm{DCFG}=\textrm{DCFG}$ is decidable by the
result of G. Sénizergues [31]. It is worth remarking that decidability of the
equivalence problem $\textrm{UCFG}=\textrm{UCFG}$ is not known. In fact, this
is a special case of the _multiplicity equivalence problem_ for CFG, which
asks whether two CFGs have the same number of derivations for every word they
accept. Decidability of the latter problem is open as well [23] and inter-
reducible with the language equivalence for probabilistic pushdown automata
[15]. The restriction of the $\textrm{UCFG}=\textrm{UCFG}$ equivalence problem
to words of a given length has been studied in [25].

##### Number sequences and the zeroness problem.

We obtained the PSPACE upper bound for UUCFG by reducing to the zeroness
problem for conv-rec sequences. Conv-rec sequences generalise linear
difference recurrence with constant coefficients (a.k.a.  _constant-recursive_
or _C-finite_ [22]; c.f. also [3] and citations therein) by allowing the
convolution product in the recurrence. They are a special case of more
expressive classes such as P-recursive [22, Ch. 7] (a.k.a.  _holonomic_) and
polynomial recursive sequences [6]. The zeroness problem for P-recursive
sequences is decidable [37] and the same holds for polynomial recursive
sequences (as a corollary of the existence of cancelling polynomials [6,
Theorem 11]). However, no complexity upper bounds are known for those more
general classes.

##### Coin-flip measure.

As a complement to the PSPACE upper bound for UUCFG, we have shown that the
coin-flip measure comparison problem
$\mu_{\\_}\text{coin}(L(G))\sim\varepsilon$ of a UCFG $G$ with
${\sim}\in\left\\{{\leq},{<},{\geq},{>}\right\\}$ and $0\leq\varepsilon\leq 1$
is SQRTSUM-hard. The main difficulty is that the measure is generated
according to a fixed stochastic process. If we relax this constraint and
generate the measure according to an arbitrary finite Markov process, then one
can obtain SQRTSUM-hardness already for DCFG.

It is known that the quantitative decision problem for
$\mu_{\\_}G(\Sigma^{*})$ where $G$ is a stochastic context-free grammar (SCFG)
is SQRTSUM-hard [14]. Our setting is incomparable: On the one hand we fix a
particular measure, namely the coin-flip measure $\mu_{\\_}{\text{coin}}$
(which corresponds to a fixed SCFG with rules $X\leftarrow\varepsilon\mid
a_{\\_}1\cdot X\mid\cdots\mid a_{\\_}n\cdot X$). On the other hand, we are
interested in the quantity $\mu_{\\_}\text{coin}(L(G))$ where $G$ is an
arbitrary UCFG (and thus not necessarily universal).

We leave it as an open problem to establish the exact complexity of the
universality problem for UCFG and the coin-flip measure 1 problem. When the
system of polynomial equations obtained from the grammar is _probabilistic_
(PPS999The sum of all coefficients is at most 1.) the measure 1 problem is in
PTIME [14] (and even in strongly polynomial time [12]). However, the equations
obtained from UCFG are monotone (MPS) but not PPS in general. As an example,
consider a singleton alphabet $\Sigma=\left\\{a\right\\}$ and productions of
the form $X_{\\_}0\leftarrow a$ and, for $n\geq 0$, $X_{\\_}{n+1}\leftarrow
X_{\\_}n\cdot X_{\\_}n$. The corresponding MPS system is
$x_{\\_}0=\frac{1}{2^{2}}$ and $x_{\\_}{n+1}=2\cdot x_{\\_}n^{2}$. The former
system is not a PPS, since in the second equation the coefficients sum up to
$2$. It may be argued that by the change of variable $z_{\\_}n:=2\cdot
x_{\\_}n$ we obtain the system $z_{\\_}0=\frac{1}{2}$ and
$z_{\\_}{n+1}=z_{\\_}n^{2}$ which is PPS. However, this transformation reduces
the value 1 problem on the original MPS to the value $1/2$ problem in the new
PPS, and the latter problem is not known to be in PTIME.

One source of difficulty in the UUCFG problem is that witnesses of non-
universality can have exponential length. Extending the previous example,
consider the additional rules $Y_{\\_}0\leftarrow\varepsilon$ and
$Y_{\\_}{n+1}\leftarrow Y_{\\_}n\mid X_{\\_}n\cdot Y_{\\_}n$. The nonterminal
$X_{\\_}n$ generates a single word $L(X_{\\_}n)=\left\\{a^{2^{n}}\right\\}$ of
length $2^{n}$. It can be verified by induction that $Y_{\\_}n$ generates all
words $L(Y_{\\_}n)=\left\\{a^{0},a^{1},\dots,a^{2^{n}-1}\right\\}$ of length
$\leq 2^{n}-1$, and consequently the grammar is unambiguous. Thus
$L(Y_{\\_}n)$ is not universal, however the shortest witness has length
$2^{n}$. In terms of measures,
$\mu_{\\_}\text{coin}(L(X_{\\_}n))=\frac{1}{2^{2^{n}+1}}$ and
$\mu_{\\_}\text{coin}(L(Y_{\\_}n))=1-\frac{1}{2^{2^{n}+1}}$, and thus UCFG
have measures that can be exponentially close to 0, resp., to 1. Since a word
of length $n$ over a unary alphabet has measure $\frac{1}{2^{n+1}}=2^{-O(n)}$,
if language $L$ is not universal $\mu_{\\_}\text{coin}(L)<1$, then there is a
non-universality witness of length at most $\log(1-\mu_{\\_}\text{coin}(L))$.
Thus upper bounds on $1-\mu_{\\_}\text{coin}(L)$ yield upper bounds on the
shortest non-universality witness.

##### The “$\textrm{CFG}\subseteq\textrm{UFA}$” problem.

We have shown that $\textrm{CFG}\subseteq\textrm{UFA}$ reduces to
$\textrm{DCFG}\subseteq\textrm{UFA}$ and, in turn, the latter reduces to UUCFG
and thus can be solved in PSPACE. This needs not be optimal and there are
reasons to suspect that better algorithms may be obtained. If we interpret a
DCFG $G$ as a stochastic context-free grammar (SCFG), then query
$L(G)\subseteq L(A)$ is equivalent to $\mu_{\\_}G(L(A))=1$ when $A$ is
unambiguous, where $\mu_{\\_}G$ is the measure generated by $G$ (a
generalisation of the coin-flip measure). When $A$ is DFA, $\mu_{\\_}G(L(A))$
can be approximated in PTIME [13]. Generalising this result for $A$ being UFA
would put $\textrm{DCFG}\subseteq\textrm{UFA}$ in PTIME.

##### The regularity problem for UCFG.

There are other problems which are known to be undecidable for CFG but
decidable for DCFG, such as the regularity problem [33, 35, 32]. An
interesting open problem [11] is whether the regularity problem is decidable
for UCFG.

##### Acknowledgements.

I warmly thank Alberto Pettorossi for his encouragement and guidance during my
first steps in doing research. I also thank an anonymous reviewer for his
helpful comments on a preliminary version of this draft.

## References

  * [1]
  * [2] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen & Peter Bro Miltersen (2009): _On the Complexity of Numerical Analysis_.  SIAM J. Comput. 38(5), pp. 1987–2006, 10.1137/070697926.  Available at http://dx.doi.org/10.1137/070697926.
  * [3] Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote & Filip Mazowiecki (2020): _A Robust Class of Linear Recurrence Sequences_.  In Maribel Fernández & Anca Muscholl, editors: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020), LIPIcs 152, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 9:1–9:16.
  * [4] Mikołaj Bojańczyk, Bartek Klin & Sławomir Lasota (2014): _Automata theory in nominal sets_.  Logical Methods in Computer Science Volume 10, Issue 3, 10.2168/LMCS-10(3:4)2014.  Available at https://lmcs.episciences.org/1157.
  * [5] Alin Bostan, Arnaud Carayol, Florent Koechlin & Cyril Nicaud (2020): _Weakly-unambiguous Parikh automata and their link to holonomic series_.  In: To appear in ICALP’20.
  * [6] Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk & Géraud Sénizergues (2020): _On polynomial recursive sequences_.  In: To appear in ICALP’20.
  * [7] John Canny (1988): _Some Algebraic and Geometric Computations in PSPACE_.  In: Proc. of STOC ’88, ACM, New York, NY, USA, pp. 460–467, 10.1145/62212.62257.  Available at http://doi.acm.org/10.1145/62212.62257.
  * [8] N. Chomsky & M. P. Schützenberger (1963): _The Algebraic Theory of Context-Free Languages_.  In P. Braffort & D. Hirschberg, editors: Computer Programming and Formal Systems, Studies in Logic and the Foundations of Mathematics 35, Elsevier, pp. 118 – 161, https://doi.org/10.1016/S0049-237X(08)72023-8.  Available at http://www.sciencedirect.com/science/article/pii/S0049237X08720238.
  * [9] Wojciech Czerwiński, Diego Figueira & Piotr Hofman (2020): _Universality Problem for Unambiguous VASS_.  Available at https://hal.archives-ouvertes.fr/hal-02483495.  Working paper or preprint.
  * [10] Wojciech Czerwinski, Slawomir Lasota, Roland Meyer, Sebastian Muskalla, K. Narayan Kumar & Prakash Saivasan (2018): _Regular Separability of Well-Structured Transition Systems_.  In Sven Schewe & Lijun Zhang, editors: Proc. of CONCUR’18, LIPIcs 118, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 35:1–35:18, 10.4230/LIPIcs.CONCUR.2018.35.  Available at http://drops.dagstuhl.de/opus/volltexte/2018/9573.
  * [11] Volker Diekert & Steffen Kopecki (2010): _Complexity Results and the Growths of Hairpin Completions of Regular Languages_.  In: Proc. of CIAA’10, CIAA’10, Springer-Verlag, Berlin, Heidelberg, pp. 105–114.
  * [12] Javier Esparza, Andreas Gaiser & Stefan Kiefer (2010): _Computing Least Fixed Points of Probabilistic Systems of Polynomials_.  In Jean-Yves Marion & Thomas Schwentick, editors: STACS’10, LIPIcs 5, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 359–370, 10.4230/LIPIcs.STACS.2010.2468.  Available at http://drops.dagstuhl.de/opus/volltexte/2010/2468.
  * [13] Kousha Etessami, Alistair Stewart & Mihalis Yannakakis (2013): _Stochastic Context-free Grammars, Regular Languages, and Newton’s Method_.  In: Proc. of ICALP’13, Springer-Verlag, pp. 199–211, 10.1007/978-3-642-39212-220.  Available at http://dx.doi.org/10.1007/978-3-642-39212-2_20.
  * [14] Kousha Etessami & Mihalis Yannakakis (2009): _Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations_.  J. ACM 56(1), pp. 1:1–1:66, 10.1145/1462153.1462154.  Available at http://doi.acm.org/10.1145/1462153.1462154.
  * [15] Vojtěch Forejt, Petr Jančar, Stefan Kiefer & James Worrell (2014): _Language equivalence of probabilistic pushdown automata_.  Information and Computation 237, pp. 1–11, https://doi.org/10.1016/j.ic.2014.04.003.  Available at http://www.sciencedirect.com/science/article/pii/S0890540114000625.
  * [16] Ronald Graham, Donald Knuth & Oren Patashnik (1994): _Concrete Mathematics_ , 2nd edition.  Addison Wesley.
  * [17] D. Yu Grigor’ev (1988): _Complexity of deciding Tarski algebra_.  Journal of Symbolic Computation 5(1), pp. 65–108, https://doi.org/10.1016/S0747-7171(88)80006-3.  Available at http://www.sciencedirect.com/science/article/pii/S0747717188800063.
  * [18] Wright E.M. Hardy G.H. (2008): _An introduction to the theory of numbers_ , 6ed. edition.  OUP.
  * [19] Thomas N. Hibbard & Joseph Ullian (1966): _The Independence of Inherent Ambiguity From Complementedness Among Context-Free Languages_.  J. ACM 13(4), pp. 588–593.
  * [20] John Hopcroft & Jeffrey Ullman (1979): _Introduction to Automata Theory, Languages, and Computation_.  Addison-Wesley.
  * [21] Takumi Kasai & Shigeki Iwata (1992): _Some Problems in Formal Language Theory Known as Decidable are Proved EXPTIME Complete_.  数理解析研究所講究録 796\.
  * [22] Manuel Kauers & Peter Paule (2011): _C-Finite Sequences_ , pp. 63–86.  Springer Vienna, Vienna, 10.1007/978-3-7091-0445-34.  Available at https://doi.org/10.1007/978-3-7091-0445-3_4.
  * [23] Werner Kuich (1994): _On the Multiplicity Equivalence Problem for Context-Free Grammars_.  In: Proceedings of the Colloquium in Honor of Arto Salomaa on Results and Trends in Theoretical Computer Science, Springer-Verlag, Berlin, Heidelberg, pp. 232—250.
  * [24] Werner Kuich & Arto Salomaa (1986): _Semirings, Automata, Languages_.  EATCS Monographs on Theoretical Computer Science 5, Springer.  Available at http://gen.lib.rus.ec/book/index.php?md5=c22e327ec8a3a010137c7809f7a5abe1.
  * [25] B. Litow (1996): _Bounded length UCFG equivalence_.  In Tetsuo Asano, Yoshihide Igarashi, Hiroshi Nagamochi, Satoru Miyano & Subhash Suri, editors: Algorithms and Computation, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 239–246.
  * [26] P. Massazza & N. Sabadini (1989): _Some applications and techniques for generating functions_.  In Josep Díaz & Fernando Orejas, editors: TAPSOFT ’89, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 321–336.
  * [27] A. R. Meyer & L. J. Stockmeyer (1972): _The Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space_.  In: Proceedings of the 13th Annual Symposium on Switching and Automata Theory, SWAT ’72, IEEE Computer Society, Washington, DC, USA, pp. 125–129.
  * [28] Antoine Mottet & Karin Quaas (2019): _The Containment Problem for Unambiguous Register Automata_.  In Rolf Niedermeier & Christophe Paul, editors: Proc. of STACS’19, LIPIcs 126, Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, pp. 53:1–53:15, 10.4230/LIPIcs.STACS.2019.53.  Available at http://drops.dagstuhl.de/opus/volltexte/2019/10292.
  * [29] Stanisław Purgał (2018): _Learning regular languages offline from a positive sample_.  Master’s thesis, University of Warsaw.
  * [30] Arto Salomaa & Marti Soittola (1978): _Automata-theoretic aspects of formal power series_.  Texts and Monographs in Computer Science, Springer.  Available at http://gen.lib.rus.ec/book/index.php?md5=1E7B3DCFFFC7F6146062637382E5067D.
  * [31] Géraud Sénizergues (1997): _The equivalence problem for deterministic pushdown automata is decidable_.  In Pierpaolo Degano, Roberto Gorrieri & Alberto Marchetti-Spaccamela, editors: Proc. of ICALP’97, Springer Berlin Heidelberg, Berlin, Heidelberg, pp. 671–681.
  * [32] Priti Shankar & B. S. Adiga (1991): _A Graph-based Regularity Test for Deterministic Context-free Languages_.  Theor. Comput. Sci. 88(1), pp. 117–125, 10.1016/0304-3975(91)90076-E.  Available at http://dx.doi.org/10.1016/0304-3975(91)90076-E.
  * [33] R.E. Stearns (1967): _A regularity test for pushdown machines_.  Information and Control 11(3), pp. 323 – 340, http://dx.doi.org/10.1016/S0019-9958(67)90591-8.  Available at http://www.sciencedirect.com/science/article/pii/S0019995867905918.
  * [34] Richard E. Stearns & Harry B. Hunt (1981): _On the equivalence and containment problems for unambiguous regular expressions, grammars, and automata_.  In: Proc. of SFCS’81, IEEE Computer Society, Washington, DC, USA, pp. 74–81, 10.1109/SFCS.1981.29.  Available at http://dx.doi.org/10.1109/SFCS.1981.29.
  * [35] Leslie G. Valiant (1975): _Regularity and Related Problems for Deterministic Pushdown Automata_.  J. ACM 22(1), pp. 1–10, 10.1145/321864.321865.  Available at http://doi.acm.org/10.1145/321864.321865.
  * [36] Tzeng Wen-Guey (1996): _On path equivalence of nondeterministic finite automata_.  Information Processing Letters 58(1), pp. 43–46.
  * [37] Doron Zeilberger (1990): _A holonomic systems approach to special functions identities_.  Journal of Computational and Applied Mathematics 32(3), pp. 321–368, https://doi.org/10.1016/0377-0427(90)90042-X.  Available at http://www.sciencedirect.com/science/article/pii/037704279090042X.

##  Appendix A Appendix

See 12

###### Proof.

Fix an alphabet $\Sigma_{\\_}n$ and let $m\leq n$ as in the statement of the
lemma. If $m=n$ then there is no difficulty since we can just look at the
periodic expansion $c=\sum_{\\_}{i=0}\frac{c_{\\_}i}{(n+1)^{i+1}}$ of $c$ in
base $n+1$, where crucially $0\leq c_{\\_}i\leq n$, and one can just interpret
$c_{\\_}i$ as the number of words of length $i$ that the regular expression
must accept (since there are $n^{i}$ such words of length $i$, this can always
be done, perhaps with the exception of $i=0$). However, we work under the more
general constraint $m\leq n$, which requires a refinement of the analysis
above.

There are $m^{k}$ words of length $k$ over
$\Sigma_{\\_}m\subseteq\Sigma_{\\_}n$, and thus the measure
$\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{*})$ (which is always computed w.r.t.
alphabet $\Sigma_{\\_}n$) satisfies

$\displaystyle\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{*})=\sum_{\\_}{k=0}^{\infty}\frac{m^{k}}{(n+1)^{k+1}}=\frac{1}{n+1}\cdot\sum_{\\_}{k=0}^{\infty}\left(\frac{m}{n+1}\right)^{k}=\frac{1}{n+1}\cdot\frac{1}{1-\frac{m}{n+1}}=\frac{1}{n-m+1}.$
(17)

We consider two cases. If $c=\frac{1}{n-m+1}$, then just let
$e=\Sigma_{\\_}m^{*}$, and we are done. Otherwise, assume $c<\frac{1}{n-m+1}$.
Our aim is to find some $k\in\mathbb{N}$ and write $c$ as

$\displaystyle
c=\sum_{\\_}{i=0}^{k}\frac{c_{\\_}i}{(n+1)^{i+1}}+\sum_{\\_}{j=1}^{\infty}\frac{d_{\\_}j}{(n+1)^{k+j+1}},\quad\textrm{
with }0\leq c_{\\_}i\leq m^{i}\text{ and }0\leq d_{\\_}j\leq n.$ (18)

Intuitively, $c_{\\_}i$ counts the number of words of length $i$ in $L(e)$ for
$0\leq i\leq k$, and $d_{\\_}j$ counts the number of words of length $k+j$ in
$L(e)$ for $j\geq 1$. Moreover, in the first part the $c_{\\_}i$’s are allowed
to be very big (up to $m^{i}$) and in the second part the $d_{\\_}j$’s must be
small (up to $n$). Thus we will be able to interpret the $d_{\\_}j$’s as
digits in the base $n+1$ expansion of the second quantity. We now find the
required value for $k$. Generalising (17), the measure of all words of length
at most $k\in\mathbb{N}$ over the sub-alphabet $\Sigma_{\\_}m$ is (always
computed w.r.t. $\Sigma_{\\_}n$)

$\displaystyle\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{\leq
k})=\sum_{\\_}{i=0}^{k}\frac{m^{i}}{(n+1)^{i+1}}=\frac{1}{n-m+1}\left(1-\left(\frac{m}{n+1}\right)^{k+1}\right).$
(19)

Since
$c<\frac{1}{n-m+1}=\lim_{\\_}{k\to\infty}\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{\leq
k})$, there is some $k$ s.t. $c<\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{\leq k})$.
Let $k$ be such a minimal number, i.e.,
$\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{\leq k-1})\leq
c<\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{\leq k})$. Consequently, for this choice
of $k$ we have $c_{\\_}0=m^{0},c_{\\_}1=m^{1},\dots,c_{\\_}{k-1}=m^{k-1}$, and
$0\leq c_{\\_}k<m^{k}$ where

$\displaystyle\mu_{\\_}{\Sigma_{\\_}n}(\Sigma_{\\_}m^{\leq
k-1})+\frac{c_{\\_}k}{(n+1)^{k+1}}\leq
c<\mu_{\\_}{\Sigma_{\\_}n}(\Sigma_{\\_}m^{\leq
k-1})+\frac{c_{\\_}k+1}{(n+1)^{k+1}}.$

For complexity considerations, we note that $k$ satisfies
$c<\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{\leq k})$, and thus
$k>\frac{\log(1-(n-m+1)c)}{\log
m-\log(n+1)}-1=\frac{-\log(1-(n-m+1)c)}{\log(n+1)-\log m}$. The minimal
denominator is achieved by $m=n$, and the maximal numerator by $m=1$.
Performing this substitution, we can see that one can take
$k>\frac{-\log(1-nc)}{\log(n+1)-\log n}$. Since $-\log(1-nc)=O(\log q)$ and
$\log(n+1)-\log n=\log\frac{n+1}{n}=\log(1+\frac{1}{n})=O(\frac{1}{n})$, we
obtain

$\displaystyle k=O(n\log q).$ (20)

This choice of $k$ also guarantees $n\leq m^{k}$. Let
$d:=c-\left(\mu_{\\_}{\Sigma_{\\_}n}(\Sigma_{\\_}m^{\leq
k-1})+\frac{c_{\\_}k}{(n+1)^{k+1}}\right)$ be the remaining part of $c$ after
all terms up to $k$ have been considered: Thus, $d$ is small in the sense that
$0\leq d<\frac{1}{(n+1)^{k+1}}$. Since
$\sum_{\\_}{j=1}^{\infty}\frac{n}{(n+1)^{j+1}}=\frac{1}{n+1}$, we can write
$d$ in base $n+1$ as required by (18):

$\displaystyle
d=\frac{1}{(n+1)^{k}}\sum_{\\_}{j=1}^{\infty}\frac{d_{\\_}j}{(n+1)^{j+1}},\quad\textrm{
with }0\leq d_{\\_}j\leq n\leq m^{k}.$

The coefficients are small numbers $d_{\\_}j$ at most $n$, which can thus be
interpreted as digits in base $n+1$. Since $d$ is a rational number, the
sequence $d_{\\_}1,d_{\\_}2,\dots$ is ultimately periodic [18], i.e., there
exists a threshold $j_{\\_}1\in\mathbb{N}$ and a period $l\in\mathbb{N}$ s.t.
, for every $j\geq j_{\\_}1$, $d_{\\_}{j+l}=d_{\\_}j.$ Let
$\gamma_{\\_}1=d_{\\_}{j_{\\_}1},\gamma_{\\_}2=d_{\\_}{j_{\\_}1+1},\dots,\gamma_{\\_}l=d_{\\_}{j_{\\_}1+l-1}$
be the coefficients comprising the period. Consequently,

$\displaystyle d$
$\displaystyle=\frac{1}{(n+1)^{k}}\left(\sum_{\\_}{j=1}^{j_{\\_}1-1}\frac{d_{\\_}j}{(n+1)^{j+1}}+\sum_{\\_}{s=0}^{\infty}\left(\frac{\gamma_{\\_}1}{(n+1)^{j_{\\_}1+sl+1}}+\cdots+\frac{\gamma_{\\_}l}{(n+1)^{j_{\\_}1+sl+l}}\right)\right)$
$\displaystyle=\frac{1}{(n+1)^{k}}\left(\sum_{\\_}{j=1}^{j_{\\_}1-1}\frac{d_{\\_}j}{(n+1)^{j+1}}+\frac{1}{(n+1)^{j_{\\_}1-1}}\sum_{\\_}{s=0}^{\infty}\frac{\gamma}{(n+1)^{(s+1)l+1}}\right)=$
(21)
$\displaystyle=\frac{1}{(n+1)^{k}}\left(\sum_{\\_}{j=1}^{j_{\\_}1-1}\frac{d_{\\_}j}{(n+1)^{j+1}}+\frac{\gamma}{(n+1)^{j_{\\_}1}}\frac{1}{(n+1)^{l}-1}\right),$
(22)

where $\gamma:=\gamma_{\\_}1(n+1)^{l-1}+\cdots+\gamma_{\\_}l(n+1)^{0}$ is the
number of words of length $k+j_{\\_}1-1+(s+1)l$, for every $s\in\mathbb{N}$.

We are now ready to build the regular expression $e$. We begin with a basic
building block. For a given length $k$ and a cardinality $0\leq h\leq m^{k}$
written in base $m$ as $h=\sum_{\\_}{i=0}^{k}h_{\\_}i\cdot m^{i}$ ($0\leq
h_{\\_}i<m$), consider the regular expression $e_{\\_}{h,k}$ s.t.
$e_{\\_}{h,k}=\Sigma_{\\_}m^{k}$ if $h=m^{k}$, and otherwise:

$\displaystyle
e_{\\_}{h,k}=a_{\\_}m^{k-1}\cdot(a_{\\_}1+\cdots+a_{\\_}{h_{\\_}0})\cdot\Sigma_{\\_}m^{0}+a_{\\_}m^{k-2}\cdot(a_{\\_}1+\cdots+a_{\\_}{h_{\\_}1})\cdot\Sigma_{\\_}m^{1}+\cdots+a_{\\_}m^{0}\cdot(a_{\\_}1+\cdots+a_{\\_}{h_{\\_}{k-1}})\cdot\Sigma_{\\_}m^{k-1}.$

######  Claim 15.

The expression $e_{\\_}{h,k}$ is unambiguous and $L(e_{\\_}{h,k})$ contains
precisely $h$ words of length $k$. Consequently,
$\mu_{\\_}\text{coin}(L(e_{\\_}{h,k}))=\frac{h}{(n+1)^{k+1}}$.

###### Proof (of the claim).

All words recognised by $e_{\\_}{h,k}$ have length $k$. The $i$-th block
$a_{\\_}m^{k-i-1}\cdot(a_{\\_}1+\cdots+a_{\\_}{h_{\\_}i})\cdot\Sigma_{\\_}m^{i}$
contains $h_{\\_}i\cdot m^{i}$ words since there are $h_{\\_}i$ distinct
options to choose a letter from $a_{\\_}1+\cdots+a_{\\_}{h_{\\_}i}$ and
$m^{i}$ distinct options to choose a word from $\Sigma_{\\_}m^{i}$. The
languages of different blocks are disjoint, since the prefix
$a_{\\_}m^{k-i-1}$ uniquely determines the block (since $h_{\\_}i<m$ and thus
$a_{\\_}1+\cdots+a_{\\_}{h_{\\_}i}$ does not contain $a_{\\_}m$). Similarly,
the two concatenations in a block are unambiguous, and thus $e_{\\_}{h,k}$ is
unambiguous. ∎

The sought expression of measure $c$ is

$\displaystyle e=\Sigma_{\\_}m^{\leq
k-1}+e_{\\_}{c_{\\_}k,k}+e_{\\_}{d_{\\_}1,k+1}+\cdots+e_{\\_}{d_{\\_}{j_{\\_}1-1},k+j_{\\_}1-1}+e_{\\_}{\gamma,k+j_{\\_}1-1+l}\cdot
e_{\\_}{1,l}^{*}.$ (23)

######  Claim 16.

The expression $e$ is well defined provided $k\geq l\cdot\frac{\log(n+1)}{\log
m}-1+l$.

###### Proof (of the claim).

The $e_{\\_}{d_{\\_}j,k+j}$’s are well defined since $d_{\\_}j\leq n\leq
m^{k}\leq m^{k+j}$ and thus there are $d_{\\_}j$ words of length $k+j$ over
alphabet $\Sigma_{\\_}m$.) In order for $e_{\\_}{\gamma,k+j_{\\_}1-1+l}$ to be
well defined we need $\gamma\leq m^{k+j_{\\_}1-1+l}$. Since
$\gamma\leq(n+1)^{l}$ and $n\leq m^{k}$, it suffice to require $(n+1)^{l}\leq
m^{k-1+l}$. The latter condition follows from the assumption. ∎

######  Claim 17.

The expression $e$ is unambiguous and $\mu_{\\_}\text{coin}(L(e))=c$.

###### Proof (of the claim).

Unambiguity follows from the fact that  1) all disjuncts of $e$ recognise
disjoint languages, since $\Sigma_{\\_}m^{\leq k-1}$ recognises only words of
length $\leq k-1$, $e_{\\_}{c_{\\_}k,k}$ only words of length $k$,
$e_{\\_}{d_{\\_}1,k+1}$ only words of length $k+1$, …,
$e_{\\_}{d_{\\_}{j_{\\_}1-1},k+j_{\\_}1-1}$ only words of length
$k+j_{\\_}1-1$, and $e_{\\_}{\gamma,k+j_{\\_}1-1+l}\cdot e_{\\_}{1,l}^{*}$
only words of length $\geq k+j_{\\_}1-1+l$, and  2) all disjuncts
$e_{\\_}{c_{\\_}k,k},e_{\\_}{d_{\\_}1,k+1},\dots,e_{\\_}{d_{\\_}{j_{\\_}1-1},k+j_{\\_}1-1}$
are unambiguous by 15, and $e_{\\_}{\gamma,k+j_{\\_}1-1+l}\cdot
e_{\\_}{1,l}^{*}$ is unambiguous since $e_{\\_}{1,l}^{*}$ contains only one
word of length $l$.  In general
$\mu_{\\_}\text{coin}(L^{k})=(n+1)^{k-1}\mu_{\\_}\text{coin}(L)^{k}$ (by (13),
when such power is unambiguous) and thus
$\mu_{\\_}\text{coin}(L^{*})=\mu_{\\_}\text{coin}(L^{0}\cup
L^{1}\cup\cdots)=\mu_{\\_}\text{coin}(L^{0})+\mu_{\\_}\text{coin}(L^{1})+\cdots=\frac{1}{n+1}(((n+1)\mu_{\\_}\text{coin}(L))^{0}+((n+1)\mu_{\\_}\text{coin}(L))^{1}+\cdots)=\frac{1}{n+1}\cdot\frac{1}{1-(n+1)\mu_{\\_}\text{coin}(L)}$
when the Kleene iteration is unambiguous. Since
$\mu_{\\_}\text{coin}(L(e_{\\_}{1,l}))=\frac{1}{(n+1)^{l+1}}$, we obtain
$\mu_{\\_}\text{coin}(L(e_{\\_}{1,l}^{*}))=\frac{1}{n+1}\cdot\frac{1}{1-(n+1)\frac{1}{(n+1)^{l+1}}}=\frac{(n+1)^{l-1}}{(n+1)^{l}-1}.$
Consequently,

$\displaystyle\mu_{\\_}\text{coin}(L(e_{\\_}{\gamma,k+j_{\\_}1-1+l}\cdot
e_{\\_}{1,l}^{*}))$
$\displaystyle=(n+1)\cdot\mu_{\\_}\text{coin}(L(e_{\\_}{\gamma,k+j_{\\_}1-1+l}))\cdot\mu_{\\_}\text{coin}(L(e_{\\_}{1,l}^{*}))=$
$\displaystyle=(n+1)\cdot\frac{\gamma}{(n+1)^{k+j_{\\_}1+l}}\cdot\frac{(n+1)^{l-1}}{(n+1)^{l}-1}=$
$\displaystyle=\frac{\gamma}{(n+1)^{k+j_{\\_}1}}\cdot\frac{1}{(n+1)^{l}-1}.$

By (22), $\mu_{\\_}\text{coin}(L(e))=\mu_{\\_}\text{coin}(\Sigma_{\\_}m^{\leq
k-1})+\mu_{\\_}\text{coin}(L(e_{\\_}{c_{\\_}k,k}))+\mu_{\\_}\text{coin}(L(e_{\\_}{d_{\\_}1,k+1}))+\cdots+\mu_{\\_}\text{coin}(L(e_{\\_}{d_{\\_}{j_{\\_}1-1},k+j_{\\_}1-1}))+\mu_{\\_}\text{coin}(L(e_{\\_}{\gamma,k+j_{\\_}1-1+l}\cdot
e_{\\_}{1,l}^{*}))=c$, as required. ∎

######  Claim 18.

The expression $e$ has size $O((n\log q+j_{\\_}1+l+1)^{3})$.

###### Proof (of the claim).

The size of $e_{\\_}{h,k}$ is $|e_{\\_}{h,k}|=O(k\cdot(m+k))=O(k\cdot(n+k))$,
since $m\leq n$. Thus the size of $e$ is $|e|\leq O((k+n+j_{\\_}1+l+1)^{3})$.
By (20), $|e|\leq O((n\log q+j_{\\_}1+l+1)^{3})$, as required. ∎

If we further assume that $q\,|\,(n+1)^{\ell}$ for some $\ell\in\mathbb{N}$,
then we argue that we can take $e$ to have size polynomial in $\log q$, $n$,
and $\ell$. By (20) and the additional assumption on $q$,

$\displaystyle k=O(n\ell\log(n+1)).$ (24)

We can write $d=\frac{r}{s}$ with $r,s\in\mathbb{N}$ and $r\leq s$ relatively
prime, where $s\,|\,(n+1)^{k+1}$. If we decompose the base $n+1$ in prime
factors as $n+1=p_{\\_}1^{z_{\\_}1}p_{\\_}2^{z_{\\_}2}\cdots
p_{\\_}m^{z_{\\_}m}$ with $z_{\\_}1,\dots,z_{\\_}m\in\mathbb{N}$, then $s$ is
of the form $s=p_{\\_}1^{t_{\\_}1}p_{\\_}2^{t_{\\_}2}\cdots
p_{\\_}m^{t_{\\_}m}$ with $t_{\\_}i\leq(k+1)z_{\\_}i$. By [18, Theorem
136]101010Strictly speaking, [18, Theorem 136] requires that the base $n+1$ be
a product of primes. However, as explained in the paragraph preceding the
statement of the theorem, no difficulty arises if $n+1$ has square divisors;
c.f. also the first footnote on page 145., $d$ can be written in base $(n+1)$
with a _finite_ expansion of length
$j_{\\_}1=\max\left\\{\frac{t_{\\_}1}{z_{\\_}1},\dots,\frac{t_{\\_}m}{z_{\\_}m}\right\\}=O(k+1)$.
In particular, the period has zero length $l=0$. By (24),
$j_{\\_}1=O(n\ell\log(n+1))$. By applying 18 to this case, we obtain a regular
expression $e$ of size $O((n\log q+j_{\\_}1+l+1)^{3})\leq O((n\log
q+n\ell\log(n+1)+1)^{3})$ which is polynomial in $\log q=O(\ell\log n)$,
$\ell$, and $n$, as required. ∎