18140 LABEL:LastPageApr. 09, 2021Mar. 15, 2022 Bbbk C G cc

*A prior version [CKMP20] appeared at CONCUR’20. The present paper contains full proofs and strengthens some of the results.

# The Big-O Problem

Dmitry Chistikova  Centre for Discrete Mathematics and its Applications
(DIMAP) & Department of Computer Science, University of Warwick, UK  ,  Stefan
Kieferb  Department of Computer Science, University of Oxford, UK  ,  Andrzej
S. Murawskib  and  David Purserc  Max Planck Institute for Software Systems,
Saarland Informatics Campus, Germany

###### Abstract.

Given two weighted automata, we consider the problem of whether one is big-O
of the other, i.e., if the weight of every finite word in the first is not
greater than some constant multiple of the weight in the second.

We show that the problem is undecidable, even for the instantiation of
weighted automata as labelled Markov chains. Moreover, even when it is known
that one weighted automaton is big-O of another, the problem of finding or
approximating the associated constant is also undecidable.

Our positive results show that the big-O problem is polynomial-time solvable
for unambiguous automata, $\coNP$-complete for unlabelled weighted automata
(i.e., when the alphabet is a single character) and decidable, subject to
Schanuel’s conjecture, when the language is bounded (i.e., a subset of
$w_{1}^{*}\dots w_{m}^{*}$ for some finite words $w_{1},\dots,w_{m}$) or when
the automaton has finite ambiguity.

On labelled Markov chains, the problem can be restated as a ratio total
variation distance, which, instead of finding the maximum difference between
the probabilities of any two events, finds the maximum ratio between the
probabilities of any two events. The problem is related to
$\varepsilon$-differential privacy, for which the optimal constant of the
big-O notation is exactly $\exp(\varepsilon)$.

###### Key words and phrases:

Weighted automata, asymptotics, labelled Markov chains, differential privacy

Dmitry Chistikov was supported in part by the Royal Society International
Exchanges scheme (IEC\R2\170123).

Stefan Kiefer was supported by a Royal Society Research Fellowship.

Andrzej S. Murawski was supported by a Royal Society Leverhulme Trust Senior
Research Fellowship and the International Exchanges Scheme (IE161701).

During the development of this work David Purser was affiliated with the
University of Warwick, UK, where he was supported by the UK EPSRC Centre for
Doctoral Training in Urban Science (EP/L016400/1) and in part by the Royal
Society International Exchanges scheme (IEC\R2\170123).

##  1\. Introduction

Weighted automata over finite words are a well-known and powerful model of
computation, a quantitative analogue of finite-state automata. Special cases
of weighted automata include nondeterministic finite automata and labelled
Markov chains, two standard formalisms for modelling systems and processes.
Algorithms for analysis of weighted automata have been studied both in the
early theory of computing and more recently by the infinite-state systems and
algorithmic verification communities.

Given two weighted automata $\mathcal{A}$, $\mathcal{B}$ over an algebraic
structure $(\mathcal{S},{+},{\times})$, the equivalence problem asks whether
the two associated functions
$f_{\mathcal{A}},f_{\mathcal{B}}\colon\Sigma^{*}\to\mathcal{S}$ are equal:
$f_{\mathcal{A}}(w)=f_{\mathcal{B}}(w)$ for all finite words $w$ over the
alphabet $\Sigma$. Over the ring $(\mathbb{Q},{+},{\times})$, equivalence is
decidable in polynomial time by the results of Schützenberger [Sch61] and
Tzeng [Tze92]; subsequently, fast parallel ( and ) algorithms have been found
for this problem [Tze96, KMO+13]. In contrast, for semirings the equivalence
problem is hard: undecidable [Kro94, ABK11] for the semiring
$(\mathbb{Q},{\max},{+})$ and -hard [MS72] for the Boolean semiring (for which
weighted automata are usual nondeterministic finite automata and equivalence
is equality of recognized languages). For the ring
$(\mathbb{Q},{+},{\times})$, replacing $=$ with $\leq$ makes the problem
harder: the question of whether $f_{\mathcal{A}}(w)\leq f_{\mathcal{B}}(w)$
for all $w\in\Sigma^{*}$ is undecidable—even if $f_{\mathcal{A}}$ is constant
[Paz14]. This problem subsumes the universality problem for (Rabin)
probabilistic automata, yet another subclass of weighted automata (see, e.g.,
[Fij17]).

The problem of whether $f_{\mathcal{A}}(w)\leq f_{\mathcal{B}}(w)$ holds for
all $w\in\Sigma^{*}$ has often been considered, under different semirings, but
also for other forms of weighted automata, in which, e.g., $\limsup$ or
(discounted) limit averages are used to combine the weights along a run. For
example, most decidability and complexity results in [CDH10, BCV18] are on
such weighted automata. Alternatively, to regain decidability in view of the
undecidability result mentioned in the previous paragraph, one can consider
semantic restrictions on the weighted automaton, e.g., the assumption that,
for every $w$, all runs on $w$ have the same weight. This route has been
taken, e.g., in [FGR15].

In this paper, we introduce and study another natural problem, in which the
condition $f_{\mathcal{A}}(w)\leq f_{\mathcal{B}}(w)$ is relaxed. Given
$\mathcal{A}$ and $\mathcal{B}$ as above, is it true that there exists a
constant $c>0$ such that

$f_{\mathcal{A}}(w)\leq c\cdot f_{\mathcal{B}}(w)\qquad\text{for all
$w\in\Sigma^{*}$\,?}$

Using standard mathematical notation, this condition asserts that
$f_{\mathcal{A}}(w)=O(f_{\mathcal{B}}(w))$ as $|w|\to\infty$, and we refer to
this problem as the _big-O_ problem accordingly.111There also exists a related
but slightly different definition of big-O; see Section 3.3 for details on the
corresponding version of our big-O problem. The _big- $\Theta$_ problem (which
turns out to be computationally equivalent to the big-O problem), in line with
the $\Theta(\cdot)$ notation in analysis of algorithms, asks whether
$f_{\mathcal{A}}=O(f_{\mathcal{B}})$ and $f_{\mathcal{B}}=O(f_{\mathcal{A}})$.

We restrict our attention to the ring $(\mathbb{Q},{+},{\times})$ and only
consider _non-negative weighted automata_ , i.e., those in which all
transitions have non-negative weights. We remark that, even under this
restriction, weighted automata still form a superclass of (Rabin)
probabilistic automata, a non-trivial and rich model of computation. Our
initial motivation to study the big-O problem came from yet another formalism,
labelled Markov chains (LMCs). One can think of the semantics of LMCs as
giving a probability distribution or subdistribution on the set of all finite
words. LMCs, often under the name Hidden Markov Models, are widely employed in
a diverse range of applications; in computer-aided verification, they are
perhaps the most fundamental model for probabilistic systems, with model-
checking tools such as Prism [KNP11] or Storm [DJKV17] based on analyzing LMCs
efficiently. All the results in our paper (including hardness results) hold
for LMCs too. Our main findings are as follows.

  * •

The big-O problem for non-negative WA and LMCs turns out to be undecidable in
general, by a reduction from nonemptiness for probabilistic automata.

  * •

In the unary case, i.e., if the input alphabet $\Sigma$ is a singleton, the
big-O problem becomes decidable and is, in fact, complete for the complexity
class . Unary LMCs are a simple and pure probabilistic model of computation:
they run in discrete time and can terminate at any step; the big-O problem
refers to this termination probability in two LMCs (or two WA). Our upper
bound argument refines an analysis of growth of entries in powers of non-
negative matrices by Friedland and Schneider [Sch86], and the lower bound is
obtained by a reduction from unary NFA universality [SM73].

  * •

In a more general bounded case, i.e., if the languages of all words $w$
associated with non-zero weight are included in $w_{1}^{*}w_{2}^{*}\ldots
w_{m}^{*}$ for some finite words $w_{1},\ldots,w_{m}\in\Sigma^{*}$ (that is,
are _bounded in the sense of Ginsburg and Spanier_ ; see [Gin66, Chapter 5]
and [GS64]), the big-O problem is decidable subject to Schanuel’s conjecture.
This is a well-known conjecture in transcendental number theory [Lan66], which
implies that the first-order theory of the real numbers with the exponential
function is decidable [MW96]. Intuitively, our reliance on this conjecture is
linked to the expressions for the growth rate in powers of non-negative
matrices. These expressions are sums of terms of the form $\rho^{n}\cdot
n^{k}$, where $n$ is the length of a word, $k\in\mathbb{N}$, and $\rho$ is an
algebraic number. Our algorithms (however implicitly) need to compare for
equality pairs of real numbers of the form $\log\rho_{1}/\log\rho_{2}$, where
$\rho_{i}$ are algebraic, and it is an open problem in number theory whether
there is an effective procedure for this task (the four exponentials
conjecture asks whether two such ratios can ever be equal; see, e.g.,
Waldschmidt [Wal00, Sections 1.3 and 1.4]).

Bounded languages form a well-known subclass of regular languages. In fact, a
regular (or even context-free) language $L$ is bounded if and only if the
number of words of length $n$ in $L$ is at most polynomial in $n$. All other
regular languages have, in contrast, exponential growth rate (a fact
rediscovered multiple times; see, e.g., references in Gawrychowski et al.
[GKRS10]). Bounded languages have been studied from combinatorial and
algorithmic points of view since the 1960s [GS64, GKRS10], and have recently
been used, e.g., in the analysis of quantitative information flow problems in
computer security [Mes19b, Mes19a]. In the context of labelled Markov chains,
languages that are subsets of $a_{1}^{*}a_{2}^{*}\ldots a_{m}^{*}$ (for
individual letters $a_{1},\ldots,a_{m}\in\Sigma$) model consecutive arrival of
$m$ events in a discrete-time system. It is curious that natural decision
problems for such simple systems can lead to intricate algorithmic questions
in number theory at the border of decidability.

  * •

For unambiguous automata, i.e., where every word has at most one accepting
path, the big-O problem is also decidable and can be solved in polynomial
time.

  * •

For finitely ambiguous automata, i.e., where there exists $k$, such that every
word has at most $k$ accepting paths, the big-O problem is decidable subject
to Schanuel’s conjecture, similarly to the case of bounded languages.

#### Further motivation and related work

In the labelled Markov chain setting, the big-O problem can be reformulated as
a boundedness problem for the following function. For two LMCs $\mathcal{A}$
and $\mathcal{B}$, define the (asymmetric) _ratio variation function_ by

$\mathit{r}(\mathcal{A},\mathcal{B})=\sup_{E\subseteq\Sigma^{*}}\left(\frac{f_{\mathcal{A}}(E)}{f_{\mathcal{B}}(E)}\right),$

where $f_{\mathcal{A}}(E)$ and $f_{\mathcal{B}}(E)$ denote the total
probability mass associated with an arbitrary set of finite words
$E\subseteq\Sigma^{*}$ in $\mathcal{A}$ and $\mathcal{B}$, respectively. Here
we assume $\frac{0}{0}=0$ and $\frac{x}{0}=\infty$ for $x>0$. Observe that,
because $\max(\frac{a}{b},\frac{c}{d})\geq\frac{a+c}{b+d}$ for $a,b,c,d\geq
0$, the supremum over $E\subseteq\Sigma^{*}$ can be replaced with supremum
over $w\in\Sigma^{*}$. Consequently, the big-O problem for LMCs is equivalent
to deciding whether $\mathit{r}(\mathcal{A},\mathcal{B})<\infty$, we give a
formal proof of this in Section 3.

Finding the value of $\mathit{r}$ amounts to asking for the optimal (minimal)
constant in the big-O notation. Further, one can consider a symmetric variant,
the _ratio distance_ :
$\mathit{rd}(\mathcal{A},\mathcal{B})=\max\\{\mathit{r}(\mathcal{A},\mathcal{B}),\mathit{r}(\mathcal{B},\mathcal{A})\\}$,
by analogy with big-$\Theta$ (Section 3.1 also applies when $\mathit{r}$ is
replaced with $\mathit{rd}$). Now, $\mathit{rd}$ is a ratio-oriented variant
of the classic _total variation distance_ $\mathit{tv}$, defined by
$\mathit{tv}(\mathcal{A},\mathcal{B})=\sup_{E\subseteq\Sigma^{*}}(f_{\mathcal{A}}(E)-f_{\mathcal{B}}(E))$,
which is a well-established way of comparing two labelled Markov chains [CK14,
Kie18]. We also consider the problem of approximating $\mathit{r}$ (as well as
$\mathit{rd}$) to a given precision and the problem of comparing it with a
given constant (threshold problem), showing that both are undecidable.

The ratio distance $\mathit{rd}$ is also equivalent to the exponential of the
_multiplicative total variation distance_ defined in [CGPX14, Smi08] in the
context of differential privacy. Consider a system $\mathcal{M}$, modelled by
a single labelled Markov chain, where output words are observable to the
environment but we want to protect the privacy of the starting configuration.
Let $R\subseteq Q\times Q$ be a symmetric relation, which relates the starting
configurations intended to remain indistinguishable. Given $\varepsilon\geq
0$, we say that $\mathcal{M}$ is $\varepsilon$-differentially private (with
respect to $R$) if, for all $(s,s^{\prime})\in R$, we have $f_{s}(E)\leq
e^{\varepsilon}\cdot f_{s^{\prime}}(E)$ for every (observable) set of traces
$E\subseteq\Sigma^{*}$ [DMNS06, CMP19]. Here in the subscript of $f$ and
elsewhere, references to states $s$ and $s^{\prime}$ replace references to
LMCs/automata: $\mathcal{M}$ stays implicit, and we specify which state it is
executed from.222It is standard that two automata $\mathcal{A},\mathcal{B}$
can be merged into the same automaton by taking the disjoint union (relabeling
states where necessary) and assigning $s,s^{\prime}$ as the starting state of
$\mathcal{A},\mathcal{B}$ respectively. Note that there exists such an
$\varepsilon$ if and only if $\mathit{r}(s,s^{\prime})<\infty$ for all
$(s,s^{\prime})\in R$ or, equivalently, (the LMC $\mathcal{M}$ executed from)
$s$ is big-O of (the LMC $\mathcal{M}$ executed from) $s^{\prime}$ for all
$(s,s^{\prime})\in R$. In fact, the minimal such $\varepsilon$ satisfies
$e^{\varepsilon}=\max_{(s,s^{\prime})\in R}\mathit{r}(s,s^{\prime})$, thus
$\mathit{r}$ captures the level of differential privacy between $s$ and
$s^{\prime}$.

Our results show that even deciding whether the multiplicative total variation
distance is finite or $+\infty$ is, in general, impossible. Likewise, it is
undecidable whether a system modelled by a labelled Markov chain provides any
degree of differential privacy, however low.

##  2\. Preliminaries

Let $\mathbb{N},\mathbb{Z},\mathbb{Q}$ and $\mathbb{R}$ be the natural,
integer, rational and real numbers respectively. When accompanied by a
constraint in the subscript, we restrict to the subset of numbers satisfying
the constraint. For example, $\mathbb{N}_{\geq k}$ are the natural numbers
greater than or equal to $k$, and in particular, $\mathbb{N}_{>0}$ are the
positive natural numbers.

######  Definition 2.0.

A _weighted automaton_ $\mathcal{W}$ over the $(\mathbb{Q},{+},{\times})$
semiring is defined as a 4-tuple $\langle Q,\Sigma{},M,F\rangle$, where $Q$ is
a finite set of _states_ , $\Sigma$ is a finite _alphabet_ ,
$M:\Sigma{}\to\mathbb{Q}^{Q\times Q}$ is a _transition weighting function_ ,
and $F\subseteq Q$ is a set of _final states_. We consider only non-negative
weighted automata, i.e. $M(a)(q,q^{\prime})\geq 0$ for all $a\in\Sigma$ and
$q,q^{\prime}\in Q$.

In complexity-theoretic arguments, we assume that each weight is given as a
pair of integers (numerator and denominator) in binary. The description size
is then the number of bits required to represent $\langle
Q,\Sigma,M,F\rangle$, including the bit size of the weights.

Each weighted automaton defines functions $f_{s}:\Sigma^{*}\to\mathbb{R}$,
where for all $s\in Q$

$f_{s}(w)=\sum_{t\in F}\left(M(a_{1})\times M(a_{2})\times\dots\times
M(a_{n})\right)_{s,t}\qquad\text{ for $w=a_{1}a_{2}\dots
a_{n}\in\Sigma^{\ast}$ }$

and $A\times B$ is standard matrix multiplication. We refer to $f_{s}(w)$ as
_the weight of $w$ from state $s$_. Without loss of generality, a weighted
automaton can have a single final state. If not, introduce a new unique final
state $t$ s.t. $M(a)(q,t)=\sum_{q^{\prime}\in F}M(a)(q,q^{\prime})$ for all
$q\in Q$,$a\in\Sigma$.

We will typically define weighted automata by listing transitions as
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle a$}]{p}q^{\prime}$
(to mean $M(a)(q,q^{\prime})=p$) with the assumption that any unspecified
transition has weight $0$.

######  Definition 2.0.

We denote by $\mathcal{L}_{s}(\mathcal{W})$ the set of $w\in\Sigma^{\ast}$
with $f_{s}(w)>0$, that is, with positive weight from $s$. Equivalently, this
is the language of $\mathcal{N}_{s}(\mathcal{W})$, the non-deterministic
finite automaton (NFA) formed from the same set of states (and final states)
as $\mathcal{W}$, start state $s$, and transitions
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}q^{\prime}$
whenever $M(a)(q,q^{\prime})>0$.

Given $s,s^{\prime}\in Q$, we say that _$s$ is big-O of $s^{\prime}$_ if there
exists $C>0$ such that $f_{s}(w)\leq C\cdot f_{s^{\prime}}(w)$ for all
$w\in\Sigma^{*}$. The paper studies the following problem.

######  Definition 2.0 (Big-O Problem).

input Weighted automaton $\langle Q,\Sigma{},M,F\rangle$ and $s,s^{\prime}\in
Q$ output Is $s$ big-O of $s^{\prime}$?

In the paper we also work with labelled Markov chains. In particular, they
will appear in examples and hardness (including undecidability) arguments. As
they are a special class of weighted automata, this will imply hardness (resp.
undecidability) for weighted automata in general. On the other hand, our
decidability results will be phrased using weighted automata, which makes them
applicable to labelled Markov chains.

######  Definition 2.0.

A _labelled Markov chain_ (LMC) is a (non-negative) weighted automaton
$\langle Q,\Sigma{},M,F\rangle$ such that, for all $q\in Q\setminus F$, we
have $\sum_{q^{\prime}\in Q}\sum_{a\in\Sigma{}}M(a)(q,q^{\prime})=1$ and
$M(a)(q,q^{\prime})=0$ for all $a\in\Sigma{},q\in F$ and $q^{\prime}\in Q$.

Since final states have no outgoing transitions, w.l.o.g., one can assume a
unique final state. For LMCs, the function $f_{s}$ can be extended to a
measure on the powerset of $\Sigma^{\ast}$ by $f_{s}(E)=\sum_{w\in
E}f_{s}(w)$, where $E\subseteq\Sigma^{*}$. The measure is a subdistribution:
$\sum_{w\in\Sigma^{*}}f_{s}(w)\leq 1$.

Probabilistic automata are similar to LMCs, except that $M(a)$ is stochastic
for every $a$, rather than $\sum_{a\in\Sigma}M(a)$ being stochastic.

######  Definition 2.0.

A probabilistic automaton $\mathcal{A}$ is a non-negative weighted automaton
with a distinguished start state $q_{s}$ such that $\sum_{q^{\prime}\in
Q}M(a)(q,q^{\prime})=1$ for all $q\in Q$ and $a\in\Sigma$. We use the notation
$\mathbb{P}_{\mathcal{A}}(w)=f_{q_{s}}(w)$, where $q_{s}$ is the start state
of the probabilistic automaton $\mathcal{A}$.

We will also consider unary weighted automata, and similarly LMCs, where
$|\Sigma|=1$. Then we will often omit $\Sigma$ on the understanding that
$\Sigma=\\{a\\}$, and describe transitions with a single transition matrix
$A=M(a)$ so that $f_{s}(a^{n})=A_{s,t}^{n}$, where $t$ is the unique final
state. Note that $A^{n}_{s,t}$ stands for $(A^{n})(s,t)$, and not
$(A(s,t))^{n}$. Using the notation of regular expressions, we can write
$\mathcal{L}_{s}(\mathcal{W})\subseteq a^{\ast}$. It will turn out fruitful to
consider several larger classes of languages:

######  Definition 2.0.

Let $L\subseteq\Sigma^{\ast}$. $L$ is _bounded_ [GS64] if $L\subseteq
w_{1}^{\ast}w_{2}^{\ast}\cdots w_{m}^{\ast}$ for some
$w_{1},\dots,w_{m}\in\Sigma^{*}$. $L$ is _letter-bounded_ if $L\subseteq
a_{1}^{*}a_{2}^{*}\dots a_{m}^{*}$ for some $a_{1},\dots,a_{m}\in\Sigma$. $L$
is _plus-letter-bounded_ if $L\subseteq a_{1}^{+}a_{2}^{+}\dots a_{m}^{+}$ for
some $a_{1},\dots,a_{m}\in\Sigma$.

In each case, if the language of an NFA is suitably bounded, one can extract a
corresponding bounding regular expression [GKRS10].

##  3\. Related problems

In this section we show three related problems to the Big-O problem: the ratio
variation function, the Big-$\Theta$ problem and the eventually Big-O problem.
In particular, Section 3.1, relating the ratio variation function, will be
useful when we show undecidability.

###  3.1. Ratio variation functions and distances

We introduced in Section 1 the ratio variation function
$\mathit{r}(s,s^{\prime})=\sup_{E\subseteq\Sigma^{*}}(f_{s}(E)/f_{s^{\prime}}(E))$,
(now specified between two different starting states) and the ratio distance
$\mathit{rd}(s,s^{\prime})=\max\\{\mathit{r}(s,s^{\prime}),\mathit{r}(s^{\prime},s)\\}$
on labelled Markov chains. The supremum is taken over _sets_ of words,
reflecting its origin as a generalisation of the total variation distance.
However, over labelled Markov chains this is not necessary, as the supremum
function can be taken over individual words. The big-O problem is also taken
over individual words, and taken in the formulation
$\mathit{r}(s,s^{\prime})=\sup_{w\in\Sigma^{*}}(f_{s}(w)/f_{s^{\prime}}(w))$
the connection between the notion ratio variation function and the big-O
problem becomes clear:

######  Observation 3.0.

We have $\mathit{r}(s,s^{\prime})<\infty$ if and only if $s$ is big-O of
$s^{\prime}$. Furthermore, if finite, $\mathit{r}(s,s^{\prime})$ is the
minimum value of $C$ witnessing that $s$ is big-O of $s^{\prime}$.

We now formally show this reformulation of the ratio variation distance.

######  Proposition 3.0.

For $\mathit{r}$ on labelled Markov chains, it is sufficient to consider the
supremum over $w\in\Sigma^{*}$ rather than $E\subseteq\Sigma^{*}$.

###### Proof of Section 3.1.

We will show we can approximate any event by a finite subset, then we can
always simplify an event with more than one word, and not decrease the ratio.

Suppose $\frac{a+c}{b+d}>\frac{a}{b}$ and $\frac{a+c}{b+d}>\frac{c}{d}$. By
the first inequality, we have $ab+bc>ab+ad$, so $bc>ad$. But by the second
inequality, we have $ad+cd>bc+cd$, so $ad>bc$. This is a contradiction.

By repeated application of this technique, a _finite_ set can always be
simplified until the set has just a single element, resulting in a ratio which
is no smaller. That is, there exists $w^{\prime}\in E$ such that,

$\frac{f_{\mathcal{A}}(E)}{f_{\mathcal{B}}(E)}=\frac{\sum_{w\in
E}f_{\mathcal{A}}(w)}{\sum_{w\in
E}f_{\mathcal{B}}(w)}\leq\frac{f_{\mathcal{A}}(w^{\prime})}{f_{\mathcal{B}}(w^{\prime})}.$
(1)

Now, we show that the consideration of finite sets is sufficient: consider an
event $E\subseteq\Sigma^{*}$, then for every $\lambda>0$ there is a
$k\in\mathbb{N}$ such that $f_{\mathcal{A}}(E\cap\Sigma^{>k})\leq\lambda$, so
then $f_{\mathcal{A}}(E\cap\Sigma^{\leq k})\leq f_{\mathcal{A}}(E)\leq
f_{\mathcal{A}}(E\cap\Sigma^{\leq k})+\lambda$ [Kie18, Lemma 12]. For any
$\varepsilon$, by choice of sufficiently small $\lambda$ there is a finite set
$E^{\prime}$ such that
$\frac{f_{\mathcal{A}}(E^{\prime})}{f_{\mathcal{B}}(E^{\prime})}-\varepsilon\leq\frac{f_{\mathcal{A}}(E)}{f_{\mathcal{B}}(E)}\leq\frac{f_{\mathcal{A}}(E^{\prime})}{f_{\mathcal{B}}(E^{\prime})}+\varepsilon$.

Consider
$\sup_{E\subseteq\Sigma^{*}}\frac{f_{\mathcal{A}}(E)}{f_{\mathcal{B}}(E)}$,
this is equivalent to
$\lim_{k\to\infty}\sup_{E\subseteq\Sigma^{*}\cap\Sigma^{\leq
k}}\frac{f_{\mathcal{A}}(E)}{f_{\mathcal{B}}(E)}$ and by Eq. 1 this is
equivalent to $\lim_{k\to\infty}\sup_{w\in\Sigma^{*}\cap\Sigma^{\leq
k}}\frac{f_{\mathcal{A}}(w)}{f_{\mathcal{B}}(w)}=\sup_{w\in\Sigma^{*}}\frac{f_{\mathcal{A}}(w)}{f_{\mathcal{B}}(w)}$.∎

###  3.2. The big-$\Theta$ problem

One could consider whether $s$ is big-$\Theta$ of $s^{\prime}$, defined as $s$
is big-O of $s^{\prime}$ and $s^{\prime}$ is big-O of $s$; or equivalently for
LMCs, whether $\mathit{rd}(s,s^{\prime})<\infty$. We note that these two
notions reduce to each other, justifying our consideration of only the big-O
problem. There is an obvious reduction from big-$\Theta$ to big-O making two
oracle calls (a Cook reduction), but, as we show below, this can be
strengthened to a single call preserving the answer (a Karp reduction). In the
other direction, one can ask if $s$ big-O of $s^{\prime}$ using big-$\Theta$
by asking if a linear combination of $s$ and $s^{\prime}$ is big-$\Theta$ of
$s^{\prime}$: this ensures that the answer to $s^{\prime}$ is big-O of $s$ and
$s^{\prime}$ is always true, essentially leaving only $s$ and $s^{\prime}$
big-O of $s^{\prime}$ to be checked, which depends only on whether $s$ is
big-O of $s^{\prime}$.

######  Lemma 3.0.

The big-O problem is interreducible with the big-$\Theta$ problem.

###### Proof.

(a) Reduction to big-$\Theta$

(b) Reduction to big-O

Figure 1. Reductions between big-O and big-$\Theta$

######  Direction 1 (big-O problem reduces to the big-$\Theta$ problem).

To ask if $s$ is big-O of $s^{\prime}$, add states $q,q^{\prime}$ using the
construction of Fig. 1(a), then ask if $q$ is big-$\Theta$ of $q^{\prime}$.

$\frac{f_{q}(aw)}{f_{q^{\prime}}(aw)}=\frac{0.5f_{s}(w)+0.5f_{s^{\prime}}(w)}{f_{s^{\prime}}(w)}<C\iff\frac{f_{s}(w)}{f_{s^{\prime}}(w)}<2C-1$
$\frac{f_{q^{\prime}}(aw)}{f_{q}(aw)}=\frac{f_{s^{\prime}}(w)}{0.5f_{s}(w)+0.5f_{s^{\prime}}(w)}\leq
2$

######  Direction 2 (big-$\Theta$ problem reduces to the big-O problem).

Given an automaton with weighting function $f$, let us construct a new
automaton $f^{\prime}$ by replacing every transition
$t=q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle a$}]{p}q^{\prime}$
with $q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{p}[t]\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{1}q^{\prime}$, where $[t]$ is a new state. The effect of this procedure
is that $f_{s}(a_{1}\dots a_{n})=f^{\prime}_{s}(a_{1}a_{1}\dots a_{n}a_{n})$.
Any word of odd length has weight zero in $f^{\prime}$. Given a word
$w=a_{1}\dots a_{n}$, denote by $\tilde{w}=a_{1}a_{1}\dots a_{n}a_{n}$.

Let us choose any character $a\in\Sigma$. We now add states
$q,q^{\prime},\bullet_{1},\bullet_{2}$ as follows:

  1. (1)

$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle a$}]{0.5}s$ and
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{0.5}\bullet_{1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{1}s^{\prime}$

  2. (2)

$q^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{0.5}s^{\prime}$ and
$q^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{0.5}\bullet_{2}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{1}s$

We claim that to ask if $s$ is big-$\Theta$ of $s^{\prime}$ is equivalent to
asking if $q$ is big-O of $q^{\prime}$. The idea of the construction is
provided in Fig. 1(b). Then we obtain the requisite bounds as follows:

$\frac{f^{\prime}_{q}(a\tilde{w})}{f^{\prime}_{q^{\prime}}(a\tilde{w})}=\frac{0.5f_{s}(w)}{0.5f_{s^{\prime}}(w)}<C\iff\frac{f_{s}(w)}{f_{s^{\prime}}(w)}<C,$
$\frac{f^{\prime}_{q}(aa\tilde{w})}{f^{\prime}_{q^{\prime}}(aa\tilde{w})}=\frac{0.5f_{s^{\prime}}(w)}{0.5f_{s}(w)}<C\iff\frac{f_{s^{\prime}}(w)}{f_{s}(w)}<C.$

Each of the reductions operates in logarithmic space.∎

###  3.3. The Eventually Big-O Problem

Readers familiar with the big-O notation may recall definition on
$f,g:\mathbb{N}\to\mathbb{N}$, of the form: $f$ is $O(g)$ if $\exists C,k>0$
$\forall n>k\ f(n)\leq C\,g(n)$. Despite excluding finitely many points, when
$g(n)\geq 1$, it is equivalent to the definition we use, $\exists{C>0}\
\forall{n>0}\ f(n)\leq C\,g(n)$, by taking $C$ large enough to deal with the
finite prefix.

In the paper, though, we formally consider $s$ to not be big-O of $s^{\prime}$
if there exists even a single word $w$ such that $f_{s}(w)>0$ and
$f_{s^{\prime}}(w)=0$. However, for weighted automata, we could amend our
definition to “eventually big-O” as follows: $\exists C>0,k>0:\forall
w\in\Sigma^{\geq k}\ f_{s}(w)\leq C\cdot f_{s^{\prime}}(w)$.333It is
instructive to juxtapose these definitions with classic definitions in
analysis, following, e.g., de Bruijn’s classic monograph [dB81, Section 1.2].
For two nonnegative functions $f,g\colon\mathbb{R}\to\mathbb{R}$:  • $f=O(g)$
on a set $S\subseteq\mathbb{R}$ if there is $c>0$ such that $f(x)\leq c\cdot
g(x)$ for all $x\in S$, • $f=O(g)$ as $x\to a$ (as $x\to\infty$, respectively)
if there is a neighbourhood of $a$ (of $\infty$, respectively) such that
$f=O(g)$ in that neighbourhood, in the sense defined above. It is now clear
that our definition of big-O from Section 2 asserts
$f_{s}(w)=O(f_{s^{\prime}}(w))$ for all $w\in\Sigma^{*}$, i.e., on the set
$\Sigma^{*}$. In comparison, the “eventually big-O” asserts that
$f_{s}(w)=O(f_{s^{\prime}}(w))$ as $|w|\to\infty$.

The Eventually Big-O Problem and Big-O Problem are also interreducible. We
delay showing this equivalence to Section 6.1, as it depends on some further
technical development.

Allowing additive error (in addition to the multiplicative error) in the
inequality can also capture a similar relaxation of the Big-O problem.
Colcombet and Daviaud [CD13] study the problem of _affine domination_ , which
asks whether there exists $c>0$ such that $f_{s}(w)\leq c\cdot
f_{s^{\prime}}(w)+c$ for all $w\in\Sigma^{*}$? The problem is shown decidable
for weighted automata over the tropical $(\mathbb{N}\cup\\{\infty\\},\min,+)$
semiring, contrasting the containment problem ($f_{s}(w)\leq
f_{s^{\prime}}(w)$ for all $w\in\Sigma^{*}$?) which is also undecidable in
that semiring. We observe that both containment and the big-O problem are
undecidable in the $(\mathbb{Q}_{\geq 0},+,\times)$ semiring that we are
considering.

##  4\. Big-O, Threshold and Approximation problems are undecidable

We show that the big-O problem is undecidable. We also establish
undecidability for several other problems related to computing and
approximating the ratio variation distance. Recall that this corresponds to
identifying the optimal constant for positive instances of the big-O problem
or the level of differential privacy between two states in a labelled Markov
chain. Results in this section are presented on ratio total variation
distances on labelled Markov chains, and thus apply to the big-O problem in
the more general weighted automata.

In the following definition, a _promise problem_ (see e.g., [ESY84]) restricts
the inputs to the problem. An algorithm professing to decide the problem need
only give a correct answer on the inputs conforming to the promise. If the
input does not meet the promise, then the answer is not specified and can be
arbitrary (including non-termination). In particular, it need not be decidable
whether the promise holds.

######  Definition 4.0.

The _asymmetric threshold problem_ takes an LMC along with two states
$s,s^{\prime}$ and a constant $\theta$, and asks if
$\mathit{r}(s,s^{\prime})\leq\theta$. The variant under the promise of
boundedness promises that $\mathit{r}(s,s^{\prime})<\infty$; i.e., the input
to the problem is restricted to the instances where it is known that
$\mathit{r}(s,s^{\prime})<\infty$.

The strict variant of each problem replaces $\leq$ with $<$.

The _asymmetric additive approximation task_ takes an LMC, two states
$s,s^{\prime}$ and a constant $\gamma$, and asks for $x$ such that
$|\mathit{r}(s,s^{\prime})-x|\leq\gamma$. The _asymmetric multiplicative
approximation task_ takes an LMC, two states $s,s^{\prime}$ and a constant
$\gamma$, and asks for $x$ such that
${1}-{\gamma}\leq\frac{x}{\mathit{r}(s,s^{\prime})}\leq 1+\gamma$.

In each case, the symmetric variant is obtained by replacing $\mathit{r}$ with
$\mathit{rd}$.

######  Theorem 4.0.

  * •

The big-O problem is undecidable, even for LMCs.

  * •

Each variant of the threshold problem (asymmetric/symmetric, non-
strict/strict) is undecidable, even under the promise of boundedness.

  * •

All variants of the approximation tasks (asymmetric/symmetric,
additive/multiplicative) are recursively unsolvable, even under the promise of
boundedness.

The proof of Section 4 will reduce from the emptiness problem for
probabilistic automata (recall Section 2). The problem Empty asks, given a
probabilistic automaton $\mathcal{A}$, if
$\mathbb{P}_{\mathcal{A}}(w)\leq\frac{1}{2}$ for all words $w\in\Sigma^{*}$.
(Is the language
$\\{w\in\Sigma^{*}\mid\mathbb{P}_{\mathcal{A}}(w)>\frac{1}{2}\\}$ empty?) It
is known to be undecidable [Paz14, Fij17]. Recall, we use the notation
$\mathbb{P}_{\mathcal{A}}(w)$ to refer to the probability mass in the
probabilistic automaton, and the notation $f_{s}(w)$ for the weight (from
state $s$) in the labelled Markov chain.

###### Proof idea for Section 4.

We reduce from Empty. We assume we are given _any_ probabilistic automaton
$\mathcal{A}$, for which we would like to decide the emptiness problem. We
first show a construction which will construct a specific labelled Markov
chain from the probabilistic automaton. The resulting labelled Markov chain
will have the property that answering any of the questions of Section 4 would
allow us to answer the emptiness problem for the probabilistic automaton
$\mathcal{A}$. Therefore, an algorithm to decide any of the questions in
Section 4 would give an algorithm to decide the emptinenss problem. Since the
emptiness problem is undecidabile, meaning there is no algorithm that can
decide whether any given probabilistic automaton is empty or not, then there
can be no algorithm to decide any of these questions.

The construction creates two branches of a labelled Markov chain. The first
simulates the probabilistic automaton using the original weights multiplied by
a scalar ($\frac{1}{4}$ in the case $|\Sigma|=2$). The other branch will
process each letter from $\Sigma$ with equal weight (also $\frac{1}{4}$ in an
infinite loop). Consequently, if there is a word accepted with probability
greater than $\frac{1}{2}$, the ratio between the two branches will be greater
than $1$. The construction will enable words to be processed repeatedly, so
that the ratio can then be pumped unboundedly. Certain linear combinations of
the branches entail a gap promise, entailing undecidability of the threshold
and approximation tasks. ∎

We now implement the proof idea: first we show the properties required of the
construction and (in Section 4.1) how these properties imply Section 4. Then
we show the construction (in Section 4.2) and prove that the desired
properties hold (in Section 4.3).

Given any probabilistic automaton $\mathcal{A}$, we construct a labelled
Markov chain with three distinguished starting states $s,s^{\prime}$ and
$s^{\prime\prime}$. These states will exhibit the following the properties:

######  Properties 4.0.

  * •

If $\mathcal{A}\not\in\textsc{Empty}$ then $\mathit{r}(s,s^{\prime})=\infty$.

  * •

If $\mathcal{A}\in\textsc{Empty}$ then $\mathit{r}(s,s^{\prime})\leq 2$.

  * •

If $\mathcal{A}\not\in\textsc{Empty}$ then
$49<\mathit{r}(s,s^{\prime\prime})\leq 51$.

  * •

If $\mathcal{A}\in\textsc{Empty}$ then $\mathit{r}(s,s^{\prime\prime})\leq 2$.

  * •

$\mathit{r}(s^{\prime},s)\leq 2$ and $\mathit{r}(s^{\prime\prime},s)\leq 2$.

###  4.1. Section 4 imply Section 4

The following lemma plays a key role in proving the result. In its statement,
“undecidable to distinguish” means that the corresponding _promise problem_ is
undecidable. In other words, if the input is not in one of the two cases which
should be distinguished between, the answer is not specified and can be
arbitrary (including non-termination).

Due to the undecidability of Empty, a construction satisfying Section 4
immediately establishes the following undecidability results:

######  Lemma 4.0.

  * •

Given an LMC along with two states $s,s^{\prime}$ and constant $c$, it is
undecidable to distinguish between $\mathit{r}(s,s^{\prime})\leq c$ and
$\mathit{r}(s,s^{\prime})=\infty$.

  * •

Given an LMC along with two states $s,s^{\prime\prime}$ and two numbers $c$
and $C$ such that $c<C$, it is undecidable to distinguish between
$\mathit{r}(s,s^{\prime\prime})\leq c$ and
$C\leq\mathit{r}(s,s^{\prime\prime})<\infty$.

Both statements remain true if $\mathit{r}$ is replaced with $\mathit{rd}$.
This is because $\mathit{r}(s^{\prime},s)\leq 2$ and
$\mathit{r}(s^{\prime\prime},s)\leq 2$ ensures that $\mathit{r}(s,s^{\prime})$
and $\mathit{r}(s,s^{\prime\prime})$ dominate in the computation of
$\mathit{rd}$, thus the proceeding four statements hold when replaced by
$\mathit{rd}$.

Before we give the construction satisfying Section 4, we show how Section 4.1
shows our theorem.

###### Proof of Section 4.

We reason by contradiction using Section 4.1. For the big-O problem, it
suffices to observe that, if it were decidable, one could use it to solve the
first promise problem from the Lemma (recall that in a promise problem the
input is guaranteed to fall into one of the two cases). This would contradict
Section 4.1.

Similarly, the decidability of the (asymmetric) threshold problem would allow
us to distinguish between $\mathit{r}(s,s^{\prime})\leq c$ and
$C\leq\mathit{r}(s,s^{\prime})<\infty$ (second promise problem from the Lemma)
by considering the instance $\mathit{r}(s,s^{\prime})\leq\frac{c+C}{2}$ (non-
strict variant) or $\mathit{r}(s,s^{\prime})<\frac{c+C}{2}$ (strict variant).
A positive answer (regardless of the variant) implies
$\mathit{r}(s,s^{\prime})\leq c$, while a negative one yields
$\mathit{r}(s,s^{\prime})\geq C$, which suffices to distinguish the cases.
Note that in both cases $\mathit{r}(s,s^{\prime})$ is bounded, so the
reasoning remains valid if it is known in advance that
$\mathit{r}(s,s^{\prime})$ is bounded.

For additive (asymmetric) approximation, we observe that finding $x$ such that
$|\mathit{r}(s,s^{\prime})-x|\leq\frac{C-c}{4}$ and comparing it with
$\frac{c+C}{2}$ makes it possible to distinguish between
$\mathit{r}(s,s^{\prime})\leq c$ and $C\leq\mathit{r}(s,s^{\prime})<\infty$.
This is because $\mathit{r}(s,s^{\prime})\leq c$ then implies
$x<\frac{c+C}{2}$ and $C\leq\mathit{r}(s,s^{\prime})$ implies
$\frac{c+C}{2}<x$.

In the multiplicative case, finding $x$ such that
$1-\frac{C-c}{4C}\leq\frac{x}{\mathit{r}(s,s^{\prime})}\leq 1+\frac{C-c}{4C}$
and comparing $x$ with $\frac{c+C}{2}$ yields an analogous argument.

Since Section 4.1 also applies to $\mathit{rd}$, all of our results hold when
$\mathit{r}$ is replaced by $\mathit{rd}$. ∎

###  4.2. The construction

We now show how to build, given a probabilistic automaton, a labelled Markov
chain that satisfies Section 4. (We prove that the construction indeed
satisfies these properties in the next section.)

######  Construction 4.0.

For both cases, we reduce from Empty. We show our construction for
$\Sigma{}=\\{a,b\\}$, but the procedure can be generalised to arbitrary
alphabets.

The construction will create two branches of a labelled Markov chain. The
first, from state $q_{s}$, will simulate the given probabilistic automaton
using the original weights multiplied by the same scalar (in this case
$\frac{1}{4}$). The other branch, from state $s_{0}$, will process each letter
from $\Sigma$ with equal weight (also $\frac{1}{4}$ in an infinite loop).
Consequently, if there is a word accepted with probability greater than
$\frac{1}{2}$, the ratio between the two branches will be greater than $1$.
The construction will make it possible to process words repeatedly, so that
the ratio can then be pumped unboundedly.

Formally, suppose we are given a probabilistic automaton $\mathcal{A}=\langle
Q,\Sigma,M,F\rangle$ with start state $q_{s}$. First observe that w.l.o.g.
$q_{s}$ is not accepting, since in this case the empty word is accepted with
probability $1$, and thus there is a word with probability greater than
$\frac{1}{2}$ and a trivial positive instance of the big-O problem can be
returned.

We construct the LMC $\langle
Q^{\prime},\Sigma^{\prime},\delta,F^{\prime}\rangle$ taking
$Q^{\prime}=Q\uplus\\{s,s^{\prime},s^{\prime\prime},s_{0},t\\}$ where $\uplus$
denotes disjoint union,
$\Sigma^{\prime}=\\{a,b,\mathit{acc},\mathit{rej},{\vdash}\\}$,
$F^{\prime}=\\{t\\}$ and $\delta$ as specified below. First we simulate the
probabilistic automaton with a scaling factor of $\frac{1}{4}$: for all
$q,q^{\prime}\in Q$,

$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{\frac{1}{4}M(a)(q,q^{\prime})}q^{\prime}\quad\quad
q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
b$}]{\frac{1}{4}M(b)(q,q^{\prime})}q^{\prime}.$

Originally accepting runs trigger a restart, while rejecting ones are
redirected to $t$:

$\text{if }q\in
F:q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\mathit{acc}$}]{\frac{1}{2}}q_{s}\quad\text{
and }\quad\text{if }q\not\in
F:q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\mathit{rej}$}]{\frac{1}{2}}t.$

We then add a part of the chain which behaves equally, rather than according
to the probabilistic automaton:

$s_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{\frac{1}{4}}s_{0}\quad\quad
s_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
b$}]{\frac{1}{4}}s_{0}\quad\quad
s_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\mathit{acc}$}]{\frac{1}{4}}s_{0}\quad\quad
s_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\mathit{rej}$}]{\frac{1}{4}}t.$

The construction is illustrated in Fig. 2. To complete the reduction, we add
the following transitions from $s,s^{\prime},s^{\prime\prime}$:

$s\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\vdash$}]{\frac{1}{2}}s_{0}\quad\quad
s\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\vdash$}]{\frac{1}{2}}q_{s}\quad\quad
s^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\vdash$}]{1}s_{0}\quad\quad
s^{\prime\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\vdash$}]{\frac{99}{100}}s_{0}\quad\quad
s^{\prime\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\vdash$}]{\frac{1}{100}}q_{s}.$

Figure 2. Reduction; where $q_{a}$ represents accepting states of the
probabilistic automaton, $q_{r}$ represents rejecting states and $q_{s}$
represents the start state (assumed to be rejecting).

###  4.3. Proof that the construction satisfies Section 4

It remains to show that Section 4.2 satisfies Section 4, which we show in the
following two lemmas.

######  Lemma 4.0.

If $\mathcal{A}\not\in\textsc{Empty}$ then $\mathit{r}(s,s^{\prime})=\infty$.
If $\mathcal{A}\in\textsc{Empty}$ then $\mathit{r}(s,s^{\prime})\leq 2$. In
either case, $\mathit{r}(s^{\prime},s)\leq 2$.

###### Proof.

First observe that

$\frac{f_{s}({\vdash}w^{\prime})}{f_{s^{\prime}}({\vdash}w^{\prime})}=\frac{\frac{1}{2}f_{s_{0}}(w^{\prime})+\frac{1}{2}f_{q_{s}}(w^{\prime})}{f_{s_{0}}(w^{\prime})}=\frac{1}{2}+\frac{1}{2}\frac{f_{q_{s}}(w^{\prime})}{f_{s_{0}}(w^{\prime})}.$
(2)

If there is a word $w$ that is accepted by the automaton with probability
$>\frac{1}{2}$, then let $w^{\prime}_{i}=(w\ \mathit{acc})^{i}\ \mathit{rej}$
and we have

$\frac{f_{q_{s}}(w^{\prime}_{i})}{f_{s_{0}}(w^{\prime}_{i})}=\frac{((\frac{1}{4})^{|w|}\mathbb{P}(w)\frac{1}{2})^{i}\cdot\frac{1}{2}}{((\frac{1}{4})^{|w|}\frac{1}{4})^{i}\cdot\frac{1}{4}}=2\cdot(2\mathbb{P}(w))^{i}.$
(3)

Since $\mathbb{P}(w)>\frac{1}{2}$ then $2\mathbb{P}(w)>1$ and we have:

$\lim_{i\to\infty}\frac{f_{s}({\vdash}w^{\prime}_{i})}{f_{s^{\prime}}({\vdash}w^{\prime}_{i})}=\infty\quad\text{
and }\quad\mathit{r}(s,s^{\prime})=\mathit{rd}(s,s^{\prime})=\infty.$

If there is no such word then $\forall
w\in\Sigma^{*}:\mathbb{P}(w)\leq\frac{1}{2}$, then probability ratio of all
words is bounded. All words stating from states $s$ and $s^{\prime}$ start
with ${\vdash}$ and are terminated by $\mathit{rej}$, so in general all words
take the form $w={\vdash}(w_{1}\ \mathit{acc})\dots(w_{n}\
\mathit{acc})(w_{n+1}\ \mathit{rej})$. Let us consider the probability of
$w^{\prime}=(w_{1}\ \mathit{acc})\dots(w_{n}\ \mathit{acc})(w_{n+1}\
\mathit{rej})$ words from $s_{0}$ and $q_{s}$. Then:

$\displaystyle\frac{f_{q_{s}}(w^{\prime})}{f_{s_{0}}(w^{\prime})}$
$\displaystyle=\frac{\left(\prod_{i=1}^{n}\frac{1}{2}(\frac{1}{4})^{|w_{i}|}\mathbb{P}(w_{i})\right)\left((\frac{1}{4})^{|w_{n+1}|}(1-\mathbb{P}(w_{n+1}))\frac{1}{2}\right)}{(\frac{1}{4})^{|w_{1}|+\dots+|w_{n}|}(\frac{1}{4})^{n}(\frac{1}{4})^{|w_{n+1}|}\frac{1}{4}}$
(4)
$\displaystyle\leq\frac{\left((\frac{1}{4})^{|w_{1}|+\dots+|w_{n}|}(\frac{1}{2})^{n}(\frac{1}{2})^{n}\right)\left((\frac{1}{4})^{|w_{n+1}|}\frac{1}{2}\right)}{(\frac{1}{4})^{|w_{1}|+\dots+|w_{n}|+n}(\frac{1}{4})^{|w_{n+1}|}\frac{1}{4}}$
(as $\forall i:\mathbb{P}(w_{i})\leq\frac{1}{2}$) $\displaystyle=2.$ (5)

Then using Eq. 2 for every word $w$ we have
$\frac{1}{2}\leq\frac{f_{s}(w)}{f_{s^{\prime}}(w)}\leq\frac{3}{2}$ and
$\mathit{r}(s,s^{\prime})\leq\frac{3}{2}$ and $\mathit{rd}(s,s^{\prime})\leq
2$. ∎

######  Lemma 4.0.

If $\mathcal{A}\not\in\textsc{Empty}$ then
$49<\mathit{r}(s,s^{\prime\prime})\leq 51$. If $\mathcal{A}\in\textsc{Empty}$
then $\mathit{r}(s,s^{\prime\prime})\leq 2$. In either case,
$\mathit{r}(s^{\prime\prime},s)\leq 2$.

###### Proof.

We first observe that
$\frac{f_{s^{\prime\prime}}({\vdash}w)}{f_{s}({\vdash}w)}$ is always $\leq 2$,
resulting in the only interesting direction being
$\frac{f_{s}({\vdash}w)}{f_{s^{\prime\prime}}({\vdash}w)}$:

$\displaystyle\frac{f_{s^{\prime\prime}}({\vdash}w)}{f_{s}({\vdash}w)}$
$\displaystyle=\frac{\frac{99}{100}f_{s_{0}}(w)+\frac{1}{100}f_{q_{s}}(w)}{\frac{1}{2}f_{s_{0}}(w)+\frac{1}{2}f_{q_{s}}(w)}$
$\displaystyle=\frac{\frac{99}{100}f_{s_{0}}(w)}{\frac{1}{2}f_{s_{0}}(w)+\frac{1}{2}f_{q_{s}}(w)}+\frac{\frac{1}{100}f_{q_{s}}(w)}{\frac{1}{2}f_{s_{0}}(w)+\frac{1}{2}f_{q_{s}}(w)}$
$\displaystyle\leq\frac{\frac{99}{100}f_{s_{0}}(w)}{\frac{1}{2}f_{s_{0}}(w)}+\frac{\frac{1}{100}f_{q_{s}}(w)}{\frac{1}{2}f_{q_{s}}(w)}$
$\displaystyle=\frac{2\cdot 99}{100}+\frac{2}{100}=2.$

We observe that for all words ${\vdash}w$, the quantities $\mathit{r}$ and
$\mathit{rd}$ are bounded:

$\displaystyle\frac{f_{s}({\vdash}w)}{f_{s^{\prime\prime}}({\vdash}w)}$
$\displaystyle=\frac{\frac{1}{2}f_{s_{0}}(w)+\frac{1}{2}f_{q_{s}}(w)}{\frac{99}{100}f_{s_{0}}(w)+\frac{1}{100}f_{q_{s}}(w)}$
$\displaystyle=\frac{\frac{1}{2}f_{s_{0}}(w)}{\frac{99}{100}f_{s_{0}}(w)+\frac{1}{100}f_{q_{s}}(w)}+\frac{\frac{1}{2}f_{q_{s}}(w)}{\frac{99}{100}f_{s_{0}}(w)+\frac{1}{100}f_{q_{s}}(w)}$
$\displaystyle\leq\frac{\frac{1}{2}f_{s_{0}}(w)}{\frac{99}{100}f_{s_{0}}(w)}+\frac{\frac{1}{2}f_{q_{s}}(w)}{\frac{1}{100}f_{q_{s}}(w)}$
$\displaystyle\leq\frac{100}{2\cdot 99}+\frac{100}{2}\leq 51.$

If there is a word $w$ that is accepted by the automaton with probability
$>\frac{1}{2}$, then we consider the sequence of words $w^{\prime}_{i}=(w\
\mathit{acc})^{i}\ \mathit{rej}$:

$\frac{f_{s}({\vdash}w^{\prime}_{i})}{f_{s^{\prime\prime}}({\vdash}w^{\prime}_{i})}=\frac{\frac{1}{2}f_{s_{0}}(w^{\prime}_{i})+\frac{1}{2}f_{q_{s}}(w^{\prime}_{i})}{\frac{99}{100}f_{s_{0}}(w^{\prime}_{i})+\frac{1}{100}f_{q_{s}}(w^{\prime}_{i})}\geq\frac{\frac{1}{2}f_{q_{s}}(w^{\prime}_{i})}{\frac{99}{100}f_{s_{0}}(w^{\prime}_{i})+\frac{1}{100}f_{q_{s}}(w^{\prime}_{i})}.$

By the previous proof (Eq. 3) we know
$\frac{f_{q_{s}}(w^{\prime}_{i})}{f_{s_{0}}(w^{\prime}_{i})}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
i\to\infty$}]{}\infty$, thus
$\frac{f_{s_{0}}(w^{\prime}_{i})}{f_{q_{s}}(w^{\prime}_{i})}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
i\to\infty$}]{}0$. Consider

$\frac{\frac{99}{100}f_{s_{0}}(w^{\prime}_{i})+\frac{1}{100}f_{q_{s}}(w^{\prime}_{i})}{\frac{1}{2}f_{q_{s}}(w^{\prime}_{i})}=\frac{2}{100}+\frac{2\cdot
99}{100}\left(\frac{f_{s_{0}}(w^{\prime}_{i})}{f_{q_{s}}(w^{\prime}_{i})}\right)\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
i\to\infty$}]{}\frac{2}{100}$

then

$\frac{\frac{1}{2}f_{q_{s}}(w^{\prime}_{i})}{\frac{99}{100}f_{s_{0}}(w^{\prime}_{i})+\frac{1}{100}f_{q_{s}}(w^{\prime}_{i})}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
i\to\infty$}]{}\frac{100}{2}=50.$

So for all $\varepsilon$ there exists an $i$ such that
$\frac{f_{s}({\vdash}w^{\prime}_{i})}{f_{s^{\prime\prime}}({\vdash}w^{\prime}_{i})}\geq
50-\varepsilon$. In particular for example $\mathit{r}(s,s^{\prime\prime})\geq
49$.

If there is no such word then $\mathbb{P}(w)\leq\frac{1}{2}$ for all
$w\in\Sigma^{*}$. We show that the total variation distance will be small. All
words starting from state $s$ and $s^{\prime}$ start with ${\vdash}$ and are
terminated by $\mathit{rej}$, so in general all words take the form
$w={\vdash}(w_{1}\ \mathit{acc})\dots(w_{n}\ \mathit{acc})(w_{n+1}\
\mathit{rej})$. Let us consider the probability of such words from
$s,s^{\prime\prime}$:

$\displaystyle\frac{f_{s}(w)}{f_{s^{\prime\prime}}(w)}=\frac{\frac{1}{2}f_{s_{0}}(w^{\prime})+\frac{1}{2}f_{q_{s}}(w^{\prime})}{\frac{99}{100}f_{s_{0}}(w^{\prime})+\frac{1}{100}f_{q_{s}}(w^{\prime})}$
$\displaystyle\leq\frac{\frac{1}{2}f_{s_{0}}(w^{\prime})+\frac{1}{2}f_{q_{s}}(w^{\prime})}{\frac{99}{100}f_{s_{0}}(w^{\prime})}$
$\displaystyle\leq\frac{100}{99}\cdot\left(\frac{1}{2}+\frac{1}{2}\frac{f_{q_{s}}(w^{\prime})}{f_{s_{0}}(w^{\prime})}\right)$
$\displaystyle\leq\frac{100}{99}\cdot\frac{3}{2}$ (by Eq. 5)
$\displaystyle\leq 2.$

This creates a significant gap between the case where there is a word with
probability greater than one half and not; in particular if there exists $w$
with $\mathbb{P}(w)>\frac{1}{2}$ then $49<\mathit{r}(s,s^{\prime\prime})\leq
51$ and $49<\mathit{rd}(s,s^{\prime\prime})\leq 51$, but if no such word
exists then $\mathit{r}(s,s^{\prime\prime})\leq 2$ and
$\mathit{rd}(s,s^{\prime\prime})\leq 2$. ∎

######  Remark 4.0.

The classic _non-strict_ threshold problem for the total variation distance
(i.e. whether $\mathit{tv}(s,s^{\prime})\leq\theta$) is known to be
undecidable [Kie18], like our distances. However, it is not known if its
strict variant (i.e. whether $\mathit{tv}(s,s^{\prime})<\theta$) is also
undecidable. In contrast, in our case, both variants are undecidable. Further
note that (additive) approximation of $\mathit{tv}$ is possible [Kie18, CK14],
but this is not the case for our distances $\mathit{r}$ and $\mathit{rd}$.

##  5\. The relation to the Value-1 Problem

In the previous section we have shown the undecidability of the big-O problem
using the undecidability of the emptiness problem for probabilistic automata.
Another proof of undecidability can be obtained using the Value-1 problem,
shown to be undecidable in [GO10]: indeed, we will show in this section that
the big-O problem and the Value-1 problem are interreducible.

The Value-1 problem asks whether there exists a sequence of words with
probability tending to 1:

######  Definition 5.0 (Value-1 problem).

input | Probabilistic automaton $\mathcal{A}$
---|---
output | For all $\delta>0$, does there exist a word $w$ such that $\mathbb{P}_{\mathcal{A}}(w)>1-\delta$ ?

We will exhibit a close, but not complete, connection between the Value-1
problem and big-O problem by reducing in both directions between the two, see
Section 5.1. In this section we are concerned only with matters of
decidability, and thus do not consider whether the reductions are efficient.

Our main decidability results (in Sections 7, 8, and 9) are independent of the
findings of this section, so it can be skipped during the first reading.
However, Section 5.2 below justifies these further developments, showing why
the connection exhibited here does not entail decidability results for the
big-O problem by a transfer from decidable cases of Value-1.

###  5.1. Interreduction between Value-1 and the big-O problem

######  Proposition 5.0.

The Value-1 problem reduces to the big-O problem.

###### Proof.

Assume we are given a probabilistic automaton $\mathcal{A}=\langle
Q,\Sigma,M,F_{\mathcal{A}}\rangle$ and a dedicated starting state $q_{0}\in
Q$, which accepts words $w$ with probability $\mathbb{P}_{\mathcal{A}}(w)$.
First construct $\mathcal{A}^{\prime}$ in which words $w$ are accepted with
probability
$\mathbb{P}_{\mathcal{A}^{\prime}}(w)=1-\mathbb{P}_{\mathcal{A}}(w)$, by
inverting accepting states, that is, $\mathcal{A}^{\prime}=\langle
Q,\Sigma,M,F_{\mathcal{A}^{\prime}}\rangle$ with
$F_{\mathcal{A}^{\prime}}=Q\setminus F_{\mathcal{A}}$.

Let us first consider the idea of the proof. Consider the probabilistic
automaton $\mathcal{B}$ such that $\mathcal{B}(w)=1$ for all $w\in\Sigma^{*}$.
Then $\mathcal{B}$ is not big-O of $\mathcal{A}^{\prime}$ if and only if there
is a sequence of words for which
$\mathcal{A}^{\prime}(w_{i})\xrightarrow{i\to\infty}0$. Since we wish to show
the undecidability even for labelled Markov chains, we adjust the weight at
each step by the size of the alphabet in order to encode a probabilistic
automaton inside the labelled Markov chain. The remainder of the proof
formally builds this construction.

Construct a Markov chain $\mathcal{M}_{\mathcal{A}^{\prime}}=\langle
Q^{\prime},\Sigma^{\prime},M^{\prime},F^{\prime}\rangle$, where
$Q^{\prime}=Q\cup\\{s,s^{\prime},s_{0},\mathit{rej},\mathit{acc}\\}$,
$\Sigma^{\prime}=\Sigma\cup\\{\$\\}$ (assuming $\$\not\in\Sigma$) and
$F^{\prime}=\\{\mathit{acc}\\}$. The probabilistic automaton
$\mathcal{A}^{\prime}$ will be simulated by
$\mathcal{M}_{\mathcal{A}^{\prime}}$. The map $M^{\prime}(a)(q,q^{\prime})=p$
is described using the notation
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle a$}]{p}q^{\prime}$ as
follows:

For all $q\in Q:$

$\forall q^{\prime}\in
Q:q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{(1/|\Sigma^{\prime}|)M(a)(q,q^{\prime})}q^{\prime}\text{ for all
}a\in\Sigma$ $\text{if }q\in
F_{{\mathcal{A}^{\prime}}}:q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\$$}]{(1/|\Sigma^{\prime}|)}\mathit{acc}\quad\text{
and }\quad\text{if }q\not\in
F_{{\mathcal{A}^{\prime}}}:q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\$$}]{(1/|\Sigma^{\prime}|)}\mathit{rej}$
$s^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\$$}]{1}q_{0}\quad\quad
s\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\$$}]{1}s_{0}\quad\quad
s_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle\$$}]{(1/|\Sigma^{\prime}|)}\mathit{acc}\quad\quad\text{
and }\quad\quad s_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
a$}]{(1/|\Sigma^{\prime}|)}s_{0}\text{ for all }a\in\Sigma.$

Note the only words with positive probability are words of the form
$\$\Sigma^{*}\$\subseteq\Sigma^{\prime*}$. Then given a word $w\in\Sigma^{*}$,
$f_{s}(\$w\$)=\left(\frac{1}{|\Sigma|+1}\right)^{|w\$|}$ and
$f_{s^{\prime}}(\$w\$)=\left(\frac{1}{|\Sigma|+1}\right)^{|w\$|}(1-\mathbb{P}_{\mathcal{A}}(w))$.

Then if there is a sequence of words $(w_{i})_{i}$ for which
$\mathbb{P}_{\mathcal{A}}(w_{i})$ tends to 1 then
$\frac{f_{s}(\$w_{i}\$)}{f_{s^{\prime}}(\$w_{i}\$)}$ is unbounded. However, if
there exists some $\gamma>0$ so that for all $w\in\Sigma^{*}$ we have
$\mathbb{P}_{\mathcal{A}}(w)\leq(1-\gamma)$ then
$(1-\mathbb{P}_{\mathcal{A}}(w))\geq\gamma$, and so
$\frac{f_{s}(\$w\$)}{f_{s^{\prime}}(\$w\$)}\leq\frac{1}{\gamma}$. ∎

######  Proposition 5.0.

The big-O problem reduces to the Value-1 problem.

###### Proof.

We take an instance of the big-O problem, assumed to be a labelled Markov
chain with states $s,s^{\prime}$ and construct probabilistic automaton
$\mathcal{A}^{\prime}$ as an instance of the Value-1 problem. This new
probabilistic automaton will have the property that $s$ is not big-O of
$s^{\prime}$ if and only if $\mathcal{A}^{\prime}$ is a positive instance of
the Value-1 problem. We start with the construction, followed by both
directions of the implication.

Figure 3. Reduction to Value-1. Only the effect of transitions on the $\$$
symbol are shown in black, with the possibility to transition to the
recoverable sink state $\mathit{sink}_{1}$ depicted in grey (on symbols in
$\Sigma$). All remaining transitions and $\mathit{sink}_{2}$ are omitted.

######  Construction 5.0.

Given a labelled Markov chain $\mathcal{M}=\langle Q,\Sigma,M,F\rangle$ and
$s,s^{\prime}\in Q$, construct a probabilistic automaton $\mathcal{A}=\langle
Q^{\prime},\Sigma^{\prime},M^{\prime},F^{\prime}\rangle$. Each state of $Q$
will be duplicated, once for $s$ and once for $s^{\prime}$; $Q_{s}=\\{q_{s}\
|\ q\in Q\\}$, $Q_{s^{\prime}}=\\{q_{s^{\prime}}\ |\ q\in Q\\}$. Let
$Q^{\prime}=Q_{s}\cup
Q_{s^{\prime}}\cup\\{q_{0},\mathit{acc},\mathit{rej},\mathit{sink}_{1},\mathit{sink}_{2}\\}$,
$\Sigma^{\prime}=\Sigma\cup\\{\$\\}$ and $F^{\prime}=\\{\mathit{acc}\\}$. The
reduction can be seen in Fig. 3.

Each transition of $\mathcal{M}$ will be simulated in each of the copies
according to the probability in $\mathcal{M}$. For every $q,q^{\prime}\in Q$
and $a\in\Sigma$, let $M^{\prime}(a)(q_{s},q_{s}^{\prime})=M(a)(q,q^{\prime})$
and
$M^{\prime}(a)(q_{s^{\prime}},q_{s^{\prime}}^{\prime})=M(a)(q,q^{\prime})$. A
probabilistic automaton should be stochastic for every $a\in\Sigma$, so there
is unused probability for each character, which will divert to a (recoverable)
sink. For every $q\in Q$ and $a\in\Sigma$, let

$M^{\prime}(a)(q_{s},\mathit{sink}_{1})=1-\sum_{q^{\prime}\in
Q}M(a)(q,q^{\prime})$

and

$M^{\prime}(a)(q_{s^{\prime}},\mathit{sink}_{1})=1-\sum_{q^{\prime}\in
Q}M(a)(q,q^{\prime}).$

There is an additional control character $\$$: from $q_{0}$ the machine will
pick either of the two machines with equal probability:
$M(\$)(q_{0},s_{s})=M(\$)(q_{0},{s^{\prime}}_{s^{\prime}})=\frac{1}{2}$. If in
the accepting, rejecting, or second (unrecoverable) sink state the system will
stay there forever:
$M^{\prime}(a)(\mathit{acc},\mathit{acc})=M^{\prime}(a)(\mathit{rej},\mathit{rej})=M^{\prime}(a)(\mathit{sink}_{2},\mathit{sink}_{2})=1$
for all $a\in\Sigma^{\prime}$ (including $\$$).

The behaviour on $\$$ will differ in the two copies of $\mathcal{M}$. If in an
accepting state reached from $s$, the system will accept. If in an accepting
state reached from $s^{\prime}$ the system will reject. Otherwise the system
will restart back to $q_{0}$.

Formally,

$M^{\prime}(\$)(q_{s},\mathit{acc})=1\text{ when }q_{s}\in F\text{ and
}M^{\prime}(\$)(q_{s},q_{0})=1\text{ when }q_{s}\not\in F$

and

$M^{\prime}(\$)(q_{s^{\prime}},\mathit{rej})=1\text{ when }q_{s^{\prime}}\in
F\text{ and }M^{\prime}(\$)(q_{s^{\prime}},q_{0})=1\text{ when
}q_{s^{\prime}}\not\in F.$

When in the recoverable sink state, the system restarts on $\$$,
$M^{\prime}(\$)(\mathit{sink}_{1},q_{0})=1$, and stays there for all
$a\in\Sigma$, $M^{\prime}(a)(\mathit{sink}_{1},\mathit{sink}_{1})=1$.

It is intended that all $a\in\Sigma$ are unreadable from $q_{0}$: the system
moves to the unrecoverable sink state $\mathit{sink}_{2}$,
$M^{\prime}(a)(q_{0},\mathit{sink}_{2})=1$.

The idea is that if $f_{s}(w)\gg f_{s^{\prime}}(w)$ then, by repeatedly
reading the word $w$, all of the probability mass will eventually move to
$\mathit{acc}$; otherwise a sufficiently large amount of mass will be lost to
$\mathit{rej}$.

Denote by $\mathbb{P}_{\mathcal{A}}(w)$ the probability of a word $w$ in the
probabilistic automaton $\mathcal{A}$, from state $q_{0}$. Here we use the
notation $f$ to refer to the probability in the original labelled Markov chain
$\mathcal{M}$. Further, the notation
$\mathbb{P}[q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{w}q^{\prime}]$
stands for $\left(M^{\prime}(w_{1})\times\dots\times
M^{\prime}(w_{|w|})\right)_{q,q^{\prime}}$, i.e., the probability of
transitioning from state $q$ to $q^{\prime}$ while reading $w$ in
$\mathcal{A}$.

######  Direction 1 (Not big-O implies Value-1).

The proof shows that for every $\delta>0$ there exists $C>0$ such that, for
all $w\in\Sigma^{*}$, the inequality $f_{s}(w)>Cf_{s^{\prime}}(w)$ implies
$\mathbb{P}_{\mathcal{A}}((\$w\$)^{i})>1-\delta$ for some appropriately chosen
$i\in\mathbb{N}$.

Hence given $\delta$, choose $C$ such that
$(1-\frac{\delta}{2})\frac{C}{C+1}>1-\delta$. Then by the not big-O property,
choose a word $w$ such that $f_{s}(w)=C^{\prime}f_{s^{\prime}}(w)$, with
$C^{\prime}>C$. Then
$(1-\frac{\delta}{2})\frac{C^{\prime}}{C^{\prime}+1}>(1-\frac{\delta}{2})\frac{C}{C+1}>1-\delta$.

The input word $\$w\$$ induces a (unary) Markov chain, represented by the
matrix $A$, representing states $q_{0},\mathit{acc}$ and $\mathit{rej}$ in the
three positions, respectively:

$A=\left[\begin{array}[]{ccccc}0.5(1-f_{s}(w))+0.5(1-f_{s^{\prime}}(w))&0.5f_{s}(w)&0.5f_{s^{\prime}}(w)\\\
0&1&0\\\ 0&0&1\end{array}\right]$

Then, for the word $(\$w\$)^{i}$, for $i\in\mathbb{N}$, starting from state
$q_{0}$, observe:

$A^{i}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
i\to\infty$}]{}\left[\begin{array}[]{ccccc}0&C^{\prime}x&x\\\ 0&1&0\\\
0&0&1\\\ \end{array}\right]\text{ with }C^{\prime}x+x=1.$

For each $i$, we have
$A^{i}(q_{0},\mathit{acc})+A^{i}(q_{0},\mathit{rej})+A^{i}(q_{0},q_{0})=1$.
Choose $i$ such that $A^{i}(q_{0},q_{0})\leq\frac{\delta}{2}$. Then
$A^{i}(q_{0},\mathit{acc})+A^{i}(q_{0},\mathit{rej})\geq 1-\frac{\delta}{2}$,
using the fact that
$A^{i}(q_{0},\mathit{acc})=C^{\prime}A^{i}(q_{0},\mathit{rej})$, obtaining
$A^{i}(q_{0},\mathit{acc})+\frac{A^{i}(q_{0},\mathit{acc})}{C^{\prime}}\geq
1-\frac{\delta}{2}$. Hence
$\mathbb{P}_{\mathcal{A}}((\$w\$)^{i})=A^{i}(q_{0},\mathit{acc})\geq(1-\frac{\delta}{2})\frac{C^{\prime}}{C^{\prime}+1}>1-\delta$,
as required.

######  Direction 2 (big-O implies Not Value-1).

We know that there exists $C>0$ such that, for all $w\in\Sigma^{*}$,
$f_{s}(w)\leq Cf_{s^{\prime}}(w)$, and should show that there exists
$\delta>0$ such that every $w\in(\Sigma\cup\\{\$\\})^{*}$ has
$\mathbb{P}_{\mathcal{A}}(w)\leq 1-\delta$.

To move probability from $q_{0}$ to $\mathit{acc}$ it is necessary to use
words of the form $(\$\Sigma^{*}\$)^{*}$ where $\Sigma$ is the alphabet of
$\mathcal{M}$. Hence any word $w$ can be decomposed into
$\$w_{m}\$\$w_{m-1}\$...\$w_{1}\$$.

Let us define
$x_{i}=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$...\$w_{1}\$}\mathit{acc}]$
and
$y_{i}=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$...\$w_{1}\$}\mathit{rej}]$,
and observe $x_{m}=\mathbb{P}_{\mathcal{A}}(w)$. We compute $x_{i},y_{i}$
inductively and show $x_{i}\leq Cy_{i}$ for all $1\leq i\leq m$.

Consider reading $w_{1}$, the probability is such that

$\displaystyle x_{1}$
$\displaystyle=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{1}\$}\mathit{acc}]=\frac{1}{2}f_{s}(w_{1})$
$\displaystyle y_{1}$
$\displaystyle=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{1}\$}\mathit{rej}]=\frac{1}{2}f_{s^{\prime}}(w_{1})$
$\displaystyle\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{1}\$}q_{0}]$
$\displaystyle=1-x_{1}-y_{1}.$

Since there exists $C>0$ such that, for all $w_{i}$, $f_{s}(w_{i})\leq
Cf_{s^{\prime}}(w_{i})$, we have $x_{1}\leq Cy_{1}$. Repeating this argument
inductively, we show that $x_{i}\leq Cy_{i}$ for all $i$. Indeed:

$\displaystyle x_{i}$
$\displaystyle=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$...\$w_{1}\$}\mathit{acc}]$
$\displaystyle=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}q_{0}]\cdot\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i-1}\$...\$w_{1}\$}\mathit{acc}]+\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{acc}]$
$\displaystyle=(1-\frac{1}{2}f_{s}(w_{i})-\frac{1}{2}f_{s^{\prime}}(w_{i}))\cdot
x_{i-1}+\frac{1}{2}f_{s}(w_{i})$ $\displaystyle y_{i}$
$\displaystyle=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$...\$w_{1}\$}\mathit{rej}]$
$\displaystyle=\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}q_{0}]\cdot\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i-1}\$...\$w_{1}\$}\mathit{rej}]+\mathbb{P}[q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{rej}]$
$\displaystyle=(1-\frac{1}{2}f_{s}(w_{i})-\frac{1}{2}f_{s^{\prime}}(w_{i}))\cdot
y_{i-1}+\frac{1}{2}f_{s^{\prime}}(w_{i}).$

Hence, assuming $f_{s}(w_{i})\leq Cf_{s^{\prime}}(w_{i})$ and $x_{i-1}\leq
Cy_{i-1}$ we have:

$\displaystyle x_{i}$
$\displaystyle=(1-\frac{1}{2}f_{s}(w_{i})-\frac{1}{2}f_{s^{\prime}}(w_{i}))\cdot
x_{i-1}+\frac{1}{2}f_{s}(w_{i})$
$\displaystyle\leq(1-\frac{1}{2}f_{s}(w_{i})-\frac{1}{2}f_{s^{\prime}}(w_{i}))\cdot
Cy_{i-1}+C\cdot\frac{1}{2}f_{s^{\prime}}(w_{i})$
$\displaystyle=C\cdot[(1-\frac{1}{2}f_{s}(w_{i})-\frac{1}{2}f_{s^{\prime}}(w_{i}))y_{i-1}+\frac{1}{2}f_{s^{\prime}}(w_{i})]$
$\displaystyle\leq Cy_{i}.$

We have $x_{m}\leq Cy_{m}\leq C(1-x_{m})=C-Cx_{m}$, so
$\mathbb{P}_{\mathcal{A}}(w)=x_{m}\leq\frac{C}{C+1}<1$, so the probability of
reaching $\mathit{acc}$ is bounded away from $1$ for every word.∎

###  5.2. What do decidable cases of the Value-1 problem tell us about the
big-O problem?

The Value-1 problem is undecidable in general, however it is decidable in the
unary case in $\coNP$ [CKV14] and for leaktight automata [FGO12]. Note,
however, that the construction of Section 5.1 combined with these decidability
results does not entail decidability results for the big-O problem. Firstly
note that the construction adds an additional character, and so a unary
instance of the big-O problem always has at least two characters when
translated to the Value-1 problem. Further, as we show in the remainder of
this section, the construction does not result in a leaktight automaton. The
following argument, does not, of course, preclude the existence of an
alternative construction which could, hypothetically, maintain these
properties.

Let us recall the definition of leaktight automata [FGO12].

######  Definition 5.0.

A finite word $u$ is _idempotent_ if reading once or twice the word $u$ does
not change qualitatively the transition probabilities. That is
$\mathbb{P}_{\mathcal{A}}[q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{u}q^{\prime}]>0\iff\mathbb{P}_{\mathcal{A}}[q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{uu}q^{\prime}]>0$.

Let $u_{n}$ be a sequence of idempotent words. Assume that the sequence of
matrices $\mathbb{P}_{\mathcal{A}}(u_{n})$ converges to a limit $M$, that this
limit is idempotent and denote $\mathcal{M}$ the associated Markov chain. The
sequence $u_{n}$ is a leak if there exist $r,q\in Q$ such that the following
three conditions hold:

  1. (1)

$r$ and $q$ are recurrent in $M$,

  2. (2)

$\lim_{n\to\infty}\mathbb{P}_{\mathcal{A}}[r\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{u_{n}}q]=0$,

  3. (3)

for all $n$,
$\mathbb{P}_{\mathcal{A}}[r\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{u_{n}}q]>0$.

An automaton is _leaktight_ if there is no leak.

If there were no leak in the probabilistic automata obtained from the
reduction of Section 5.1, then the decidability of the big-O problem for
labelled Markov chains would follow. However, this is not the case, i.e.,
Section 5.1 does not solve any cases of the big-O problem by reducing to known
decidable fragments of Value-1.

######  Proposition 5.0.

The resulting automaton from the reduction of the big-O problem to the Value-1
problem has a leak.

###### Proof.

Consider some infinite sequence of words $w_{i}$ growing in length, such that
$f_{s}(w_{i})>0$ for every $i$. Let $u_{i}=\$w_{i}\$$.

Observe that this word is idempotent. For each starting state, consider the
possible states with non-zero probability and from each of these the set of
reachable states. Observe that in all cases the set reachable after one
application is equal to the set reachable after two:

  * •

$\mathit{acc}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{acc}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{acc}$

  * •

$\mathit{rej}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{rej}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{rej}$

  * •

$q_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}q_{0},\mathit{acc},\mathit{rej}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}q_{0},\mathit{acc},\mathit{rej}$

  * •

For $q$ accepting in $Q_{s}$:
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{acc}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{acc}$

  * •

For $q$ rejecting in $Q_{s}$:
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}$

  * •

For $q$ accepting in $Q_{s^{\prime}}$:
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{rej}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{rej}$

  * •

For $q$ rejecting in $Q_{s^{\prime}}$:
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}$

  * •

$\mathit{sink}_{1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}$

  * •

$\mathit{sink}_{2}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\$w_{i}\$}\mathit{sink}_{2}$.

Assume that the original labelled Markov chain has a sink, that is, the
decision to terminate the word must be made by probability. Then for all
$\lambda>0$ there exists $n$ such that $f_{s}(\Sigma^{>n})<\lambda$ and
$f_{s^{\prime}}(\Sigma^{>n})<\lambda$ [Kie18, Lemma 12].

Suppose the sequence of matrices $\mathbb{P}_{\mathcal{A}}(u_{n})$ converges
to a limit $M$ (this is with no loss of generality, because each matrix in the
sequence belongs to a compact set, so a convergent subsequence must exist) and
let $r=q_{0}$ and $q=\mathit{acc}$.

By the observation above, for longer and longer words the probability of
reaching $\mathit{acc}$ from $q_{0}$ is diminishing. Thus
$\lim\mathbb{P}_{\mathcal{A}}[r\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{u_{n}}q]=0$,
and in $M$ we have $r$ and $q$ in different SCCs. The state $\mathit{acc}$ is
recurrent as it is deterministically looping on every character. Since the
probability of reaching a final state is diminishing for longer and longer
words, whenever $\$$ is read the state returns to $r$, hence all words return
to $r$ with probability 1 in the limit. By the choice of words in the
sequence, for every word $f_{s}(w_{n})>0$, we have
$\mathbb{P}_{\mathcal{A}}[r\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{u_{n}}q]>0$
for all $n$.

Hence a leak has been defined, even in the case where $\mathcal{M}$ is unary.
∎

##  6\. The Language Containment condition

Towards decidability results, we identify a simple necessary (but
insufficient) condition for $s$ being big-O of $s^{\prime}$.

######  Definition 6.0 (LC condition).

A weighted automaton $\mathcal{W}=\langle Q,\Sigma,M,F\rangle$ and
$s,s^{\prime}\in Q$ satisfy the _language containment condition_ (LC) if for
all words $w$ with $f_{s}(w)>0$ we also have $f_{s^{\prime}}(w)>0$.
Equivalently,
$\mathcal{L}_{s}(\mathcal{W})\subseteq\mathcal{L}_{s^{\prime}}(\mathcal{W})$.

The condition can be verified by constructing NFA
$\mathcal{N}_{s}(\mathcal{W}),\mathcal{N}_{s^{\prime}}(\mathcal{W})$ that
accept $\mathcal{L}_{s}(\mathcal{W})$ and
$\mathcal{L}_{s^{\prime}}(\mathcal{W})$ respectively and verifying
$\mathcal{L}(\mathcal{N}_{s}(\mathcal{W}))\subseteq\mathcal{L}(\mathcal{N}_{s^{\prime}}(\mathcal{W}))$.

Figure 4. Unbounded ratio but language equivalent.

######  Remark 6.0.

Recall that NFA language containment is $\NL$-complete if the automata are in
fact deterministic, in $\P$ if they are unambiguous [Col15, Theorem 3],
$\coNP$-complete if they are unary [SM73] and $\PSPACE$-complete in general
[MS72]. In all cases this complexity level will match, or be lower than that
for our respective algorithm for the big-O problem.

We observe that, if $s$ is big-O of $s^{\prime}$, the LC condition must hold
and so the LC condition is the first step in each of our verification
routines. Section 6 shows that the condition alone is not sufficient to solve
the big-O problem, because two states can admit the same set of words with
non-zero weight, yet the weight ratios become unbounded.

######  Example 6.0.

Consider the unary automaton $\mathcal{W}$ in Fig. 4. We have
$\mathcal{L}_{s}(\mathcal{W})=\mathcal{L}_{s^{\prime}}(\mathcal{W})=\\{a^{n}\
|\ n\geq 1\\}$, but
$\frac{f_{s}(a^{n})}{f_{s^{\prime}}(a^{n})}=\frac{(0.75)^{n-1}\cdot
0.25}{(0.5)^{n-1}\cdot 0.5}=0.5\cdot
1.5^{n-1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
n\to\infty$}]{}\infty.$

###  6.1. The Eventually Big-O Problem

Recall from Section 3.3 that the eventually big-O problem asks whether there
exists $C>0,k>0$ such that forall $w\in\Sigma^{\geq k}$ we have $f_{s}(w)\leq
C\cdot f_{s^{\prime}}(w)$. We now justify our focus on the Big-O problem by
showing the close relationship between the two problems.

The big-O problem reduces to its eventual variant by checking both the LC
condition and the eventually big-O condition. Thus our undecidability (and
hardness) results transfer to the eventually big-O problem. The eventually
big-O problem can be solved via the big-O problem by “fixing” the LC condition
through the addition of a branch from $s^{\prime}$ that accepts all
appropriate words with very low probability.

Let $\mathcal{W}=\langle Q,\Sigma,M,\\{t\\}\rangle$ be a weighted automaton,
$s,s^{\prime}\in Q$, and $s\neq s^{\prime}$. Below, whenever we write $f_{s}$
(resp. $f_{s^{\prime}}$), this will refer to word weights from $s$ (resp.
$s^{\prime}$) in $\mathcal{W}$. We assume without loss of generality that the
state $s^{\prime}$ has no incoming transitions (if this is not the case, a
fresh copy of $s^{\prime}$ can be made).

Choose $\delta$ to be a real number such that $0<\delta<1$ and $\delta$ is
smaller than any positive weight in $\mathcal{W}$. Construct
$\mathcal{W}^{\prime}$ by adding the following transitions for all
$x\in\Sigma$:

$s^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
x$}]{\delta}t\qquad
s^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
x$}]{\delta}\bullet\qquad\bullet\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
x$}]{\delta}\bullet\qquad\bullet\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
x$}]{\delta}t,$

where $\bullet$ is a new state. Consequently, for any $w\in\Sigma^{+}$, we
get:

  1. (1)

the weight of $w$ in $\mathcal{W}^{\prime}$ from $s^{\prime}$ is
$f_{s^{\prime}}(w)+\delta^{|w|}$,

  2. (2)

if $f_{s^{\prime}}(w)>0$ then $f_{s^{\prime}}(w)>\delta^{|w|}$.

######  Proposition 6.0.

$s$ is eventually big-O of $s^{\prime}$ in $\mathcal{W}$ if and only if
$\mathcal{L}_{s}(\mathcal{W})\setminus\mathcal{L}_{s^{\prime}}(\mathcal{W})$
is finite and $s$ is big-O of $s^{\prime}$ in $\mathcal{W}^{\prime}$.

###### Proof.

######  Direction 1 ($\Rightarrow$).

Suppose $s$ is eventually big-O of $s^{\prime}$ in $\mathcal{W}$, i.e. there
exist $C,k$ such that, for all $w\in\Sigma^{\geq k}$, $f_{s}(w)\leq
Cf_{s^{\prime}}(w)$. Note that, for $w\in\Sigma^{\geq k}$, this implies that,
whenever $f_{s}(w)>0$, we must also have $f_{s^{\prime}}(w)>0$. Consequently,
$\mathcal{L}_{s}(\mathcal{W})\setminus\mathcal{L}_{s^{\prime}}(\mathcal{W})\subseteq\Sigma^{<k}$,
i.e.
$\mathcal{L}_{s}(\mathcal{W})\setminus\mathcal{L}_{s^{\prime}}(\mathcal{W})$
must be finite.

Let $w\in\Sigma^{\ast}$, $m=\max_{w\in\Sigma^{<k}}f_{s}(w)$ and
$C^{\prime}=\frac{m}{\delta^{k}}$.

  * •

If $w\in\Sigma^{\geq k}$, we have $f_{s}(w)\leq Cf_{s^{\prime}}(w)\leq
C(f_{s^{\prime}}(w)+\delta^{|w|})$.

  * •

If $w\in\Sigma^{<k}$, then $f_{s}(w)\leq
m=\frac{m}{\delta^{k}}\delta^{k}=C^{\prime}\delta^{k}\leq
C^{\prime}\delta^{|w|}\leq C^{\prime}(f_{s^{\prime}}(w)+\delta^{|w|})$. Note
that $\delta^{k}\leq\delta^{|w|}$ follows from $w\in\Sigma^{<k}$ and
$0<\delta<1$.

Taking $\max(C,C^{\prime})$ as the relevant constant, we can conclude that $s$
is big-O of $s^{\prime}$ in $\mathcal{W}^{\prime}$.

######  Direction 2 ($\Leftarrow$).

Suppose
$\mathcal{L}_{s}(\mathcal{W})\setminus\mathcal{L}_{s^{\prime}}(\mathcal{W})$
is finite and $s$ is big-O of $s^{\prime}$ in $\mathcal{W}^{\prime}$. Because
$\mathcal{L}_{s}(\mathcal{W})\setminus\mathcal{L}_{s^{\prime}}(\mathcal{W})$
is finite, there exists $k$ such that, for all $w\in\Sigma^{\geq k}$,
$f_{s}(w)>0$ implies $f_{s^{\prime}}(w)>0$. Because $s$ is big-O of
$s^{\prime}$ in $\mathcal{W}^{\prime}$, there exists $C$ such that
$f_{s}(w)\leq C(f_{s^{\prime}}(w)+\delta^{|w|})$ for any $w\in\Sigma^{\ast}$.

Let $w\in\Sigma^{\geq k}$. From $s$ being big-O of $s^{\prime}$, we get
$f_{s}(w)\leq C(f_{s^{\prime}}(w)+\delta^{|w|})$.

  * •

If $f_{s}(w)>0$ then $f_{s^{\prime}}(w)>0$. By construction of
$\mathcal{W}^{\prime}$, we get $f_{s^{\prime}}(w)>\delta^{|w|}$, so

$f_{s}(w)\leq
C(f_{s^{\prime}}(w)+\delta^{|w|})<C(f_{s^{\prime}}(w)+f_{s^{\prime}}(w))=2Cf_{s^{\prime}}(w).$

  * •

If $f_{s}(w)=0$ then we also have $f_{s}(w)=0\leq 2Cf_{s^{\prime}}(w)$.

Consequently, for any $w\in\Sigma^{\geq k}$, $f_{s}(w)\leq
2Cf_{s^{\prime}}(w)$, i.e. $s$ is eventually big-O of $s^{\prime}$ in
$\mathcal{W}$.∎

The above argument relied on completing the automaton so that any word is
accepted with some weight. To transfer our decidability results for bounded
languages, it will be necessary to complete the automaton with respect to a
bound, i.e. the extra weights are added only for words from $a_{1}^{+}\cdots
a_{m}^{+}$, $a_{1}^{\ast}\cdots a_{m}^{\ast}$, $w_{1}^{\ast}\cdots
w_{k}^{\ast}$ respectively. This can be done easily by introducing the extra
transitions according to DFA for the bounding language.

##  7\. The big-O problem for unary weighted automata is $\coNP$-complete

In this section we show $\coNP$-completeness in the unary case.

######  Theorem 7.0.

The big-O problem for unary weighted automata is $\coNP$-complete. It is
$\coNP$-hard even for unary labelled Markov chains.

For the upper bound, our analysis will refine the analysis of the growth of
powers of non-negative matrices of Friedland and Schneider [FS80, Sch86] which
gives the asymptotic order of growth of
$A^{n}_{s,t}+A^{n+1}_{s,t}+\dots+A^{n+q}_{s,t}\approx\rho^{n}n^{k}$ for some
$\rho,k$ and $q$, which smooths over the periodic behaviour (see Section 7.1).
Our results require a non-smoothed analysis, valid for each $n$. This is not
provided in [FS80, Sch86], where the smoothing forces the existence of a
single limit—which we don’t require. Our big-$\Theta$ lemma (Section 7.2) will
accurately characterise the asymptotic behaviour of $A^{n}_{s,t}$ by
exhibiting the correct value of $\rho$ and $k$ for every word.

We show that these asymptotic behaviours can be captured using suitably
defined finite automata. We then reduce the big-O problem to language
containment problems on these automata. We start by introducing several
definitions, and the result of Friedland and Schneider in Section 7.1, before
implementing the proof of the upper bound in Section 7.2. We show
$\coNP$-hardness in Section 7.3 to complete the proof of Section 7.

###  7.1. Preliminaries

Let $\mathcal{W}$ be a unary non-negative weighted automaton with states $Q$,
transition matrix $A$ and a unique final state $t$. When we refer to a path in
$\mathcal{W}$, we mean a path in the NFA of $\mathcal{W}$, i.e. paths only use
transitions with non-zero weights and states on a path may repeat.

######  Definition 7.0.

  * •

A state $q$ can reach $q^{\prime}$ if there is a path from $q$ to
$q^{\prime}$. In particular, any state $q$ can always reach itself.

  * •

A strongly connected component (SCC) $\varphi\subseteq Q$ is a maximal set of
states such that for each $q,q^{\prime}\in\varphi$, $q$ can reach
$q^{\prime}$. We denote by $SCC(q)$ the SCC of state $q$ and by $A^{\varphi}$
the $|\varphi|\times|\varphi|$ transition matrix of $\varphi$. Note every
state is in a SCC, even if it is a singleton.

  * •

The DAG of $\mathcal{W}$ is the directed acyclic graph of strongly connected
components. Components $\varphi,\varphi^{\prime}$ are connected by an edge if
there exist $q\in\varphi$ and $q^{\prime}\in\varphi^{\prime}$ with
$A(q,q^{\prime})>0$.

  * •

The spectral radius of an $m\times m$ matrix $A$ is the largest absolute value
of its eigenvalues. Recall the eigenvalues of $A$ are
$\\{\lambda\in\mathbb{C}\mid\text{ exists vector
}\vec{x}\in\mathbb{C}^{m},\vec{x}\neq 0\text{ with
}A\vec{x}=\lambda\vec{x}\\}$. The spectral radius of $\varphi$, denoted by
$\rho_{\varphi}$, is the spectral radius of $A^{\varphi}$. By $\rho(q)$ we
denote the spectral radius of the SCC in which $q$ is a member.

  * •

We denote by $T^{\varphi}$ the period of the SCC $\varphi$: the greatest
common divisor of return times for some state $s\in\varphi$, i.e.
$\operatorname*{gcd}\\{t\in\mathbb{N}\ |\ A^{t}(s,s)>0\\}$. It is known that
any choice of state in the SCC gives the same value (see e.g., [Ser13, Theorem
1.20]). If $A^{\varphi}=[0]$ then $T^{\varphi}=0$.

  * •

Let $\mathscr{P}(s,s^{\prime})$ be the set of paths from the SCC of $s$ to the
SCC of $s^{\prime}$ in the DAG of $\mathcal{W}$. Thus a path
$\pi\in\mathscr{P}(s,s^{\prime})$ is a sequence of SCCs
$\varphi_{1},\dots,\varphi_{m}$.

  * •

$T(s,s^{\prime})$, called the local period between $s$ and $s^{\prime}$, is
defined by
$T(s,s^{\prime})=\operatorname*{lcm}\limits_{\pi\in\mathscr{P}(s,s^{\prime})}\operatorname*{gcd}\limits_{\varphi\in\pi}\quad
T^{\varphi}$.

  * •

The spectral radius between states $s$ and $s^{\prime}$, written
$\rho(s,s^{\prime})$, is the largest spectral radius of any SCC seen on a path
from $s$ to $s^{\prime}$:
$\rho(s,s^{\prime})=\max_{\pi\in\mathscr{P}(s,s^{\prime})}\rho(\pi)$, where
$\rho(\pi)=\max_{\varphi\in\pi}\rho_{\varphi}$ for
$\pi\in\mathscr{P}(s,s^{\prime})$.

  * •

The following function captures the number of SCCs which attain the largest
spectral radius on the path that has the most SCCs of maximal spectral radius.
Let $k(s,s^{\prime})=\max_{\pi\in\mathscr{P}(s,s^{\prime})}k(\pi)-1$, where,
for $\pi\in\mathscr{P}(s,s^{\prime})$, $k(\pi)=|\\{\varphi\in\pi\ |\
\rho_{\varphi}=\rho(s,s^{\prime})\\}|$.

######  Lemma 7.0.

Given $A^{\varphi}$, a representation of the value $\rho_{\varphi}$ can be
found in polynomial time. This representation will admit polynomial time
testing of $\rho_{\varphi}>\rho_{\varphi^{\prime}}$ and
$\rho_{\varphi}=\rho_{\varphi^{\prime}}$ and can be embedded into the first
order theory of the reals.

###### Proof.

An algebraic number $z$ can be represented as a tuple
$(p_{z},a,b,r)\in\mathbb{Q}[x]\times\mathbb{Q}^{3}$. Here $p_{z}$ is a
polynomial over $x$ and $a,b,r$ form an approximation such that $z$ is the
only root of $p_{z}(x)$ with $|z-(a+bi)|\leq r$.

Given a polynomial, one can find the representation of each of its roots in
polynomial time using the root separation bound due to Mignotte [Mig82].
Operations such as addition and multiplication of two algebraic numbers,
finding $|x|$, testing if $x>0$ can be done in polynomial time in the size of
the representation $(p,a,b,r)$, yielding the same representation [BPR05,
Coh13, Pan96]; see, e.g., [OW14, Section 3] for a summary.

Any coefficient of the characteristic polynomial of an integer matrix can be
found in $\GapL$ [HT03]. $\GapL$ is the difference of two $\\#\L$ calls, each
of which can be found in $\NC^{2}\subseteq\P$. Here the matrix will be
rational; but it can be normalised to an integer matrix by a scalar, the least
common multiple of the denominator of each rational. Whilst this number could
be exponential, it is representable in polynomial space. The final eigenvalues
can be renormalised by this constant.

The characteristic polynomial of an $n\times n$ matrix has degree at most $n$,
since each coefficient can be found in polynomial time, the whole
characteristic polynomial can be found in this time. Thus by enumerating its
roots (at most $n$), taking the modulus of each, and sorting them ($a>b\iff
a+(-1)\times b>0$) we can find the spectral radius in this form
$(p_{z},a,b,r)$.

Note that the spectral radius is a real number, so that given the spectral
radius in the form $(p_{z},a,b,r)$ we actually have $b=0$. Then the number can
be encoded exactly in the first order theory of the reals using $\exists
x:p_{z}(x)=0\wedge x-a\leq r\wedge a-x\leq r$. ∎

The asymptotic behaviours of weighted automata will be characterised using
$(\rho,k)$-pairs:

######  Definition 7.0.

A $(\rho,k)$-pair is an element of $\mathbb{R}\times\mathbb{N}$. The ordering
on $\mathbb{R}\times\mathbb{N}$ is lexicographic, i.e.
$(\rho_{1},k_{1})\leq(\rho_{2},k_{2})\iff\rho_{1}<\rho_{2}\vee(\rho_{1}=\rho_{2}\wedge
k_{1}\leq k_{2}).$

Friedland and Schneider [FS80, Sch86] essentially use $(\rho,k)$-pairs to show
the asymptotic behaviour of the powers of non-negative matrices. In particular
they find the asymptotic behaviour of the sum of several
$A_{s,s^{\prime}}^{n}$, smoothing the periodic behaviour of the matrix.

######  Theorem 7.0 (Friedland and Schneider [FS80, Sch86]).

Let $A$ be an $m\times m$ non-negative matrix, inducing a unary weighted
automaton $\mathcal{W}$ with states $Q=\\{1,\dots,m\\}$. Given $s,t\in Q$, let
$B_{s,t}^{n}=A_{s,t}^{n}+A_{s,t}^{n+1}+\dots+A_{s,t}^{n+T(s,t)-1}$. Then
$\lim_{n\to\infty}\frac{B_{s,t}^{n}}{\rho(s,t)^{n}n^{k(s,t)}}=c,\quad
0<c<\infty$.

In the case where the local period is $1$ ($T(s,t)=T(s^{\prime},t)=1$),
Section 7.1 can already be used to solve the big-O problem (in particular if
the matrix $A$ is aperiodic). In this case
$A_{s,t}^{n}=B_{s,t}^{n}=\Theta(\rho(s,t)^{n}n^{k(s,t)})$. Then to establish
that $s$ is big-O of $s^{\prime}$ we check that the language containment
condition holds and that
$(\rho(s,t),k(s,t))\leq(\rho(s^{\prime},t),k(s^{\prime},t))$. However, this is
not sufficient if the local period is not $1$.

######  Example 7.0.

Figure 5. Different rates for different phases.

Consider the chains shown in Fig. 5 with local period $2$. The behaviour for
$n\geq 3$ is $A_{s,t}^{n}=\Theta(0.5^{n}n)$ and
$A_{s^{\prime},t}^{n}=\Theta(0.25^{n})$ when $n$ is odd and
$A_{s^{\prime},t}^{n}=\Theta(0.5^{n}n)$ when $n$ is even. However, Section 7.1
tells us $B_{s,t}^{n}=\Theta(0.5^{n}n)$ and
$B_{s^{\prime},t}^{n}=\Theta(0.5^{n}n)$ suggesting the ratio is bounded, but
in fact $s$ is not big-O $s^{\prime}$ (although $s^{\prime}$ is big-O of $s$)
because
$\frac{A_{s,t}^{2n+1}}{A_{s^{\prime},t}^{2n+1}}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
n\to\infty$}]{}\infty$.

###  7.2. Upper bound: The unary big-O problem is in $\coNP$

Let $\mathcal{W}$ be a unary weighted automaton and suppose we are asked
whether $s$ is big-O of $s^{\prime}$. We assume w.l.o.g. (a) that there is a
unique final state $t$ with no outgoing transitions, and (b) that
$s,s^{\prime}$ do not appear on any cycle (if this is not the case, copies of
$s,s^{\prime}$ and their transitions can be taken).

Next we define a “degree function”, which captures the asymptotic behaviour of
each word $a^{n}$ by a ($\rho,k$)-pair, capturing the exponential and
polynomial behaviours respectively.

######  Definition 7.0.

Given a unary weighted automaton $\mathcal{W}$, let
$d_{s,t}:\mathbb{N}\to\mathbb{R}\times\mathbb{N}$ be defined by
$d_{s,t}(n)=(\rho,k)$, where:

  * •

$\rho$ is the largest spectral radius of any vertex visited on any path of
length $n$ from $s$ to $t$;

  * •

the path from $s$ to $t$ that visits the most SCCs of spectral radius $\rho$
visits $k+1$ such SCCs;

  * •

if there is no length-$n$ path from $s$ to $t$, then $(\rho,k){=}(0,0)$.

The set of admissible $(\rho,k)$-pairs is the image of $d_{s,t}$. Observe that
this set is finite and of size at most $|Q|^{2}$: there can be no more than
$|Q|$ values of $\rho$ (if at worst each state were its own SCC) and the value
of $k$ is also bounded by the number of SCCs and thus $|Q|$.

To prepare for the proof of our key big-$\Theta$ lemma (stated below), we next
define the $(\rho,k)$-annotated version of the weighted automaton
$\mathcal{W}$. Namely, in each state we record the relevant value of
$(\rho,k)$ corresponding to the current run to the state.

######  Definition 7.0 (The weighted automaton $\mathcal{W}^{\dagger}$).

Given $\mathcal{W}=\langle Q,\Sigma,A,\\{t\\}\rangle$ and $s\in Q$, the
weighted automaton $\mathcal{W}^{\dagger}$ has states of the form $(q,\rho,k)$
for all $q\in Q$ and all admissible $(\rho,k)$-pairs, the same $\Sigma$ and no
final states. For every transition
$q\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{p}q^{\prime}$ from
$\mathcal{W}$ denoting $A(q,q^{\prime})=p$, include the following transition
in $\mathcal{W}^{\dagger}$ for each admissible $(\rho,k)$:

  * •

$(q,\rho,k)\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{p}(q^{\prime},\rho,k)$
if $\mathit{SCC}(q){=}\mathit{SCC}(q^{\prime})$,

  * •

$(q,\rho,k)\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{p}(q^{\prime},\rho,k+1)$
if $\mathit{SCC}(q){\neq}\mathit{SCC}(q^{\prime})\text{ and
}\rho=\rho(q^{\prime})$,

  * •

$(q,\rho,k)\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{p}(q^{\prime},\rho,k)$
if $\mathit{SCC}(q){\neq}\mathit{SCC}(q^{\prime})\text{ and
}\rho>\rho(q^{\prime})$,

  * •

$(q,\rho,k)\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{p}(q^{\prime},\rho(q^{\prime}),0)$
if $\mathit{SCC}(q){\neq}\mathit{SCC}(q^{\prime})\text{ and
}\rho(q^{\prime})>\rho$.

Observe that the automaton $\mathcal{W}^{\dagger}$ is constructable in
polynomial time given $\mathcal{W}$. Indeed, the spectral radii of all SCCs
can be computed and compared to each other in time polynomial in the size of
$\mathcal{W}$ (see Section 7.1).

Let $s,t\in Q$ be fixed. We are now ready to state and prove the key technical
lemma of this subsection (cf. Section 7.1, Friedland and Schneider [FS80,
Sch86]), where we assume the functions $\rho(n),k(n)$, defined by
$d_{s,t}(n)=(\rho(n),k(n))$.

######  Lemma 7.0 (The big-$\Theta$ lemma).

There exist $c,C>0$ such that, for every $n>|Q|$,

$c\cdot\rho(n)^{n}n^{k(n)}\leq A^{n}_{s,t}\leq C\cdot\rho(n)^{n}n^{k(n)}.$

###### Proof.

######  Direction 1 (lower bound).

Let us fix $(\rho^{\prime},k^{\prime})$ and show the bound for the elements of
$\\{n\in\mathbb{N}\mid d_{s,t}(n)=(\rho^{\prime},k^{\prime})\\}$.

A witnessing path in $\mathcal{W}$ is a length-$n$ path from $s$ to $t$ that
visits $k^{\prime}+1$ SCCs of spectral radius $\rho^{\prime}$ and no SCC with
a larger spectral radius. Let
$\pi=\varphi_{1}\dots\varphi_{k}\in\mathscr{P}(s,t)$ be the corresponding
sequence of SCCs visited by some witnessing path and let $s_{i},e_{i}$ ($1\leq
i\leq k$) be the entry and exit points (respectively into and out of
$\varphi_{i}$) on that path, i.e. $s=s_{1}$,
$\mathit{SCC}(s_{i})=\mathit{SCC}(e_{i})=\varphi_{i}$ ($1\leq i\leq k$), there
is a transition (of positive weight) from $e_{i}$ to $s_{i+1}$ and $e_{k}=t$.
We write $\vec{s_{i},e_{i}}$ to represent the particular sequence of
entry/exit points.

Let us define a new unary weighted automaton $\mathcal{W}^{\vec{s_{i},e_{i}}}$
to be a restriction of $\mathcal{W}$ so that the only transitions between its
SCCs are from $e_{i}$ to $s_{i+1}$, for $1\leq i<k$, i.e., the weight is
reduced to zero for any violating transition. There are finitely many such
$\vec{s_{i},e_{i}}$, so that if $n\in\\{n\in\mathbb{N}\mid
d_{s,t}(n)=(\rho^{\prime},k^{\prime})\\}$ then there exists some
$\mathcal{W}^{\vec{s_{i},e_{i}}}$ with transition matrix $D$ such that
$D_{s,t}^{n}>0$.

Let us restrict to a single choice of $\vec{s_{i},e_{i}}$, and fix $D$ be the
transition matrix of $\mathcal{W}^{\vec{s_{i},e_{i}}}$. Clearly
$A_{s,t}^{n}\geq D_{s,t}^{n}$ for all $n$, since
$\mathcal{W}^{\vec{s_{i},e_{i}}}$ is a restriction of $\mathcal{W}$. We now
show that $D_{s,t}^{n}\geq
c_{\vec{s_{i},e_{i}}}(\rho^{\prime})^{n}n^{k^{\prime}}$ for some
$c_{\vec{s_{i},e_{i}}}>0$ whenever $D_{s,t}^{n}>0$. Hence, this will imply
that $A_{s,t}^{n}\geq c_{\vec{s_{i},e_{i}}}(\rho^{\prime})^{n}n^{k^{\prime}}$.

Note that, in $\mathcal{W}^{\vec{s_{i},e_{i}}}$, $\rho(s,t)=\rho^{\prime}$ and
$k(s,t)=k^{\prime}$, because all paths from $s$ to $t$ must visit
$k^{\prime}+1$ SCC’s with spectral radius $\rho^{\prime}$. Therefore, by
Section 7.1 there exists $c^{\prime}>0$ be such that

$\lim_{m\to\infty}\frac{D_{s,t}^{m}+D_{s,t}^{m+1}+\dots+D_{s,t}^{m+T-1}}{(\rho^{\prime})^{m}m^{k^{\prime}}}=c^{\prime},$

where $T$ is the local period from $s$ to $t$ in
$\mathcal{W}^{\vec{s_{i},e_{i}}}$. By the definition of limit, for all
$\varepsilon>0$ the ratio is at least $c^{\prime}-\varepsilon$ if $m$ is big
enough. Pick $\varepsilon=c^{\prime}/2$, then the inequality
$D_{s,t}^{m}+D_{s,t}^{m+1}+\dots+D_{s,t}^{m+T-1}\geq(c^{\prime}/2)\cdot(\rho^{\prime})^{m}m^{k^{\prime}}$
holds for all $m\geq N$ where $N$ is a constant dependent only on
$\vec{s_{i},e_{i}}$.

Next we shall show that whenever $D_{s,t}^{n}>0$, that is the length $n$ word
has a positive path from $s$ to $t$ in $\mathcal{W}^{\vec{s_{i},e_{i}}}$, we
have $D_{s,t}^{n+1}+\dots+D_{s,t}^{n+T-1}=0$. This will imply
$D_{s,t}^{n}\geq(c^{\prime}/2)(\rho^{\prime})^{n}n^{k^{\prime}}$ (if $n>N$)
and, hence, $A_{s,t}^{n}\geq(c^{\prime}/2)(\rho^{\prime})^{n}n^{k^{\prime}}$.
Let $L$ be the length of the shortest path from $s$ to $t$ in
$\mathcal{W}^{\vec{s_{i},e_{i}}}$. Observe that paths from $s$ to $t$ in
$\mathcal{W}^{\vec{s_{i},e_{i}}}$ can only have lengths from
$\\{L+\ell_{1}\cdot T^{\mathit{SCC}(s_{1})}+\dots+\ell_{k}\cdot
T^{\mathit{SCC}(s_{k})}\ |\ \ell_{1},\dots,\ell_{k}\in\mathbb{N}\\}$ and,
thus,
$\\{L+\ell\cdot\gcd\\{T^{\mathit{SCC}(s_{1})},\dots,T^{\mathit{SCC}(s_{k})}\\}\
|\ \ell\in\mathbb{N}\\}$. As $\mathscr{P}(s,t)=\\{\pi\\}$ in
$\mathcal{W}^{\vec{s_{i},e_{i}}}$,
$T=\gcd\\{T^{\mathit{SCC}(s_{1})},\dots,T^{\mathit{SCC}(s_{k})}\\}$.
Consequently, all paths from $s$ to $t$ in $\mathcal{W}^{\vec{s_{i},e_{i}}}$
have length in $\\{L+\ell T\mid\ell\in\mathbb{N}\\}$. Hence, whenever
$D_{s,t}^{n}$ is positive, there are no paths which can contribute positive
value to $D_{s,t}^{n+1}+\dots+D_{s,t}^{n+T-1}$.

For small $n\leq N$, we can always take $c_{\vec{s_{i},e_{i}}}$ small enough
so that $D_{s,t}^{n}\geq
c_{\vec{s_{i},e_{i}}}(\rho^{\prime})^{n}n^{k^{\prime}}$ when $D_{s,t}^{n}>0$.
Take $c^{\prime\prime}=\min D^{m}_{s,t}/(\rho^{\prime})^{m}m^{k^{\prime}}$
where the minimum is over all $m\leq N$ for which $D^{m}_{s,t}>0$. Then
$D^{m}_{s,t}/(\rho^{\prime})^{m}m^{k^{\prime}}\geq c^{\prime\prime}$ for all
such $m$.

This means we can choose
$c_{\vec{s_{i},e_{i}}}=\min(c^{\prime}/2,c^{\prime\prime})>0$, regardless of
whether $n$ is big or small: this constant depends on $\vec{s_{i},e_{i}}$ but
not on $n$.

As $c_{\vec{s_{i},e_{i}}}$ depends only on $\vec{s_{i},e_{i}}$, to finish the
proof it suffices to take $c$ to be the smallest among the finitely many
$c_{\vec{s_{i},e_{i}}}$.

######  Direction 2 (upper bound).

Let $N_{(\rho^{\prime},k^{\prime})}=\\{n\ |\
d_{s,t}(n)=(\rho^{\prime},k^{\prime})\\}$. This gives a finite partition of
$\mathbb{N}$ as $\bigcup_{(\rho,k)}N_{(\rho,k)}$. For each
$(\rho^{\prime},k^{\prime})$, we shall find a value
$C_{(\rho^{\prime},k^{\prime})}$ so that, for $n\in
N_{(\rho^{\prime},k^{\prime})}$, we have $A_{s,t}^{n}\leq
C_{(\rho^{\prime},k^{\prime})}(\rho^{\prime})^{n}n^{k^{\prime}}$. Then, to
have $A_{s,t}^{n}\leq C\rho(n)^{n}n^{k(n)}$ for all $n\in\mathbb{N}$, it will
suffice to take $C$ to be the maximum over all
$C_{(\rho^{\prime},k^{\prime})}$.

Let us fix $(\rho^{\prime},k^{\prime})$. Consider $\mathcal{W}^{\bullet}$ to
be $\mathcal{W}^{\dagger}$ in which, for every
$(\rho,k)\leq(\rho^{\prime},k^{\prime})$, we merge the states $(t,\rho,k)$
into a single final state $t^{\prime}$. Let us rename the state $(s,0,0)$ to
$s^{\prime}$. (This merger and renaming are justified by assumptions (a) and
(b) made at the beginning of this subsection, see p. 7.2.) Let $E$ be the
corresponding transition matrix of $\mathcal{W}^{\bullet}$. Note that all
paths from $s^{\prime}$ to $t^{\prime}$ in $\mathcal{W}^{\bullet}$ go through
at most $k^{\prime}+1$ SCCs with spectral radius $\rho^{\prime}$.

######  Claim 7.0.

For all $n\in N_{(\rho^{\prime},k^{\prime})}$, we have
$A_{s,t}^{n}=E_{s^{\prime},t^{\prime}}^{n}$.

###### Proof.

Consider any path $s\to q_{1}\to\dots\to q_{m}\to t$ in $\mathcal{W}$. There
is a corresponding path in $\mathcal{W}^{\bullet}$, however the states $q_{i}$
are annotated as $(q_{i},\rho,k)$, where $\rho$ is the largest spectral radius
seen so far, and $k+1$ is the number of SCC’s of that radius number seen so
far. The only paths removed are those terminating at $(t,\rho,k)$ with
$(\rho,k)>(\rho^{\prime},k^{\prime})$. Since
$d_{s,t}(n)=(\rho^{\prime},k^{\prime})$, we know that no path visits more than
$k^{\prime}+1$ SCCs of spectral radius $\rho^{\prime}$, or an SCC of spectral
radius greater than $\rho^{\prime}$. Consequently, no such path is disallowed
in $\mathcal{W}^{\bullet}$. No paths were added either. Because every SCC in
$\mathcal{W}$ remains a strongly connected component in
$\mathcal{W}^{\bullet}$ (duplicated with various $(\rho,k)$) and its
transition probability matrix (and hence the spectral radius) remains the
same, we can conclude that $A_{s,t}^{n}=E_{s^{\prime},t^{\prime}}^{n}$. This
completes the proof of Claim 2. ∎

######  Claim 7.0.

There exists $C_{(\rho^{\prime},k^{\prime})}$ such that $A_{s,t}^{n}\leq
C_{(\rho^{\prime},k^{\prime})}(\rho^{\prime})^{n}n^{k^{\prime}}$.

###### Proof.

We have $A_{s,t}^{n}=E_{s^{\prime},t^{\prime}}^{n}\leq
E_{s^{\prime},t^{\prime}}^{n}+E_{s^{\prime},t^{\prime}}^{n+1}+\dots+E_{s^{\prime},t^{\prime}}^{n+T(s^{\prime},t^{\prime})-1}$,
where $T(s^{\prime},t^{\prime})$ is the local period between states
$s^{\prime}$ and $t^{\prime}$ in $\mathcal{W}^{\bullet}$. By Section 7.1,
there exists $C_{(\rho^{\prime},k^{\prime})}$ such that this quantity is
bounded by $C_{(\rho^{\prime},k^{\prime})}(\rho^{\prime})^{n}n^{k^{\prime}}$.
Thus, for $n\in N_{(\rho^{\prime},k^{\prime})}$, we have $A_{s,t}^{n}\leq
C_{(\rho^{\prime},k^{\prime})}(\rho^{\prime})^{n}n^{k^{\prime}}$. This
concludes the proof of Claim 2. ∎

By the argument above, the upper bound of Claim 2 completes the proof of Lemma
7.2.∎

######  Remark 7.0.

When $n\leq|Q|$ it is possible that $A^{n}_{s,t}>0$ but every path may never
take any loops. In which case our degree function allocates
$d_{s,t}(n)=(0,0)$, and so Lemma 7.2 would not hold as $A^{n}_{s,t}\not\leq
0^{n}n^{0}$. The behaviour on short words will be handled by the language
containment condition.

We will now see how the big-$\Theta$ lemma (Lemma 7.2) enables us to
characterise the big-O relation on states of weighted automata. For the
following lemma, recall the language containment (LC) condition from Section 6
and the ordering on $(\rho,k)$-pairs from Section 7.1.

######  Lemma 7.0.

A state $s$ is big-O of $s^{\prime}$ if and only if the LC condition holds
and, for all but finitely many $n\in\mathbb{N}$, we have $d_{s,t}(n)\leq
d_{s^{\prime},t}(n)$.

###### Proof.

Let us start off by giving a short summary of the proof. The idea is that,
whenever $d_{s,t}(n)\leq d_{s^{\prime},t}(n)$, by Section 7.2, we have
$f_{s}(a^{n})\leq(\frac{C}{c}(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}})\cdot
f_{s^{\prime}}(a^{n})$, in which case either $d_{s,t}(n)=d_{s^{\prime},t}(n)$
and $(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}}=1$ or
$\lim_{n\to\infty}(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}}=0$ and so
$(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}}\leq 1$ for all but finitely
many $n$. At the same time, whenever $d_{s,t}(n)>d_{s^{\prime},t}(n)$, Section
7.2 yields
$f_{s}(a^{n})\geq(\frac{c}{C}(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}})\cdot
f_{s^{\prime}}(a^{n})$ but then
$\lim_{n\to\infty}(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}}=\infty$.

We now show how to fill in the details in this summary. First we note some
consequences of $d_{s,t}(n)\leq d_{s^{\prime},t}(n)$. Suppose
$d_{s,t}(n)=(\rho,k)$ and $d_{s^{\prime},t}(n)=(\rho^{\prime},k^{\prime})$.
Thanks to Lemma 7.2, we have
$f_{s}(a^{n})\leq(\frac{C}{c}(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}})\cdot
f_{s^{\prime}}(a^{n})$. If $d_{s,t}(n)\leq d_{s^{\prime},t}(n)$ we can
distinguish two cases: either $(\rho,k)=(\rho^{\prime},k^{\prime})$ or
$(\rho,k)<(\rho^{\prime},k^{\prime})$.

  * •

In the former case, $(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}}=1$ and,
thus, ${f_{s}(a^{n})}\leq(\frac{C}{c})\cdot{f_{s^{\prime}}(a^{n})}$.

  * •

In the latter case, we have
$\lim_{m\to\infty}(\frac{\rho}{\rho^{\prime}})^{m}m^{k-k^{\prime}}=0$ and,
thus, $(\frac{\rho}{\rho^{\prime}})^{m}m^{k-k^{\prime}}<1$ for all but
finitely many $m$. Consequently, for all but finitely many $n$, we can
conclude ${f_{s}(a^{n})}\leq(\frac{C}{c})\cdot{f_{s^{\prime}}(a^{n})}$.

Thanks to the above analysis, if $d_{s,t}(n)\leq d_{s^{\prime},t}(n)$ holds
for all but finitely many $n$, it follows that
${f_{s}(a^{n})}\leq(\frac{C}{c})\cdot{f_{s^{\prime}}(a^{n})}$ for all but
finitely many $n$. Moreover, the language containment condition implies that
$f_{s}(a^{n})\leq C^{\prime}\cdot{f_{s^{\prime}}(a^{n})}$ for some
$C^{\prime}$ in the remaining (finitely many) cases. Hence, $s$ is big-O of
$s^{\prime}$, which shows the right-to-left implication.

For the converse, recall that we have already established that “$s$ is big-O
of $s^{\prime}$” implies the language containment condition. For the remaining
part, we reason by contrapositive and suppose that there are infinitely many
$n$ with $d_{s,t}(n)>d_{s^{\prime},t}(n)$. As there are finitely many values
in the range of $d_{s,t}$ and $d_{s^{\prime},t}$, there exist $(\rho,k)$ and
$(\rho^{\prime},k^{\prime})$ such that $(\rho,k)>(\rho^{\prime},k^{\prime})$
and, for infinitely many $n$, $d_{s,t}=(\rho,k)$ and
$d_{s^{\prime},t}=(\rho^{\prime},k^{\prime})$. Note that
$(\rho^{\prime},k^{\prime})\neq(0,0)$, as otherwise $f_{s^{\prime}}(a^{n})=0$
and, by the language containment condition, $f_{s}(a^{n})=0$ and
$(\rho,k)=(0,0)$, a contradiction. Therefore, $f_{s^{\prime}}(a^{n})>0$ for
all such $n$, and moreover Lemma 7.2 yields
$f_{s}(a^{n})\geq(\frac{c}{C}(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}})\cdot
f_{s^{\prime}}(a^{n})$. But $(\rho,k)>(\rho^{\prime},k^{\prime})$ implies

$\lim_{m\to\infty}\left(\frac{\rho}{\rho^{\prime}}\right)^{m}m^{k-k^{\prime}}=\infty,$

i.e. $(\frac{\rho}{\rho^{\prime}})^{n}n^{k-k^{\prime}}$ is unbounded. Thus,
$s$ cannot be big-O of $s^{\prime}$. ∎

We are going to use the characterisation from Section 7.2 to prove Section 7.
As already discussed, the LC condition can be checked via NFA inclusion
testing. To tackle the “for all but finitely many …” condition, we introduce
the concept of eventual inclusion.

######  Definition 7.0.

Given sets $A,B$, we say $A$ is eventually included in $B$, written
$A\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}B$,
if and only if the set difference $A\setminus B$ is finite.

This relation has appeared under the name of “almost inclusion” in, e.g.,
[Sén93, FT10, IMNN14]. Minimisation of finite-state automata up to finitely
many errors has been studied under the name of “hyper-minimization” (see,
e.g., [BGS09, Mal11]).

The next three lemmas relate deciding the big-O problem using the
characterisation of Section 7.2 to eventual inclusion.

######  Lemma 7.0.

Given unary NFAs $\mathcal{N}_{1},\mathcal{N}_{2}$, the problem
$\mathcal{L}(\mathcal{N}_{1})\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}\mathcal{L}(\mathcal{N}_{2})$
is in $\coNP$.

###### Proof of Section 7.2.

Let $M$ be a DFA accepting
$\mathcal{L}(\mathcal{N}_{1})\cap\overline{\mathcal{L}({\mathcal{N}_{2}})}$
obtained through standard automata constructions, i.e. $|M|\leq
2^{|\mathcal{N}_{1}|+|\mathcal{N}_{2}|}$. Note that
$\mathcal{L}(\mathcal{N}_{1})\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}\mathcal{L}(\mathcal{N}_{2})$
if and only if $\mathcal{L}(M)$ is finite. Observe that $\mathcal{L}(M)$ is
infinite if and only if there exists $w\in\mathcal{L}(M)$ with $|M|\leq|w|\leq
2|M|$.

Consequently, violation of eventual inclusion can be detected by guessing
$n\in\mathbb{N}$ such that $|M|\leq n\leq 2|M|$ and verifying
$a^{n}\in\mathcal{L}(M)$.

Even though $M$ is of exponential size, it is possible to verify
$a^{n}\in\mathcal{L}(M)$ in polynomial time, given $n$ in binary. To this end,
we use $\mathcal{N}_{1},\mathcal{N}_{2}$ instead of $M$ and view their
transition functions as matrices. Then one can verify the condition using fast
matrix exponentiation (by repeated squaring). Because the bit size of $n$ must
be polynomial in $|\mathcal{N}_{1}|+|\mathcal{N}_{2}|$, the lemma follows. ∎

######  Lemma 7.0.

Suppose $d_{1},d_{2}:\mathbb{N}\to X$, with $(X,\leq)$ a finite total order.
Then $d_{1}(n)\leq d_{2}(n)$ for all but finitely many $n$ if and only if
$\\{n\,|\,d_{1}(n)\geq
x\\}\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}\\{n\,|\,d_{2}(n)\geq
x\\}$ for all $x\in X$.

###### Proof.

The left-to-right implication is clear. For the opposite direction, observe
that, because the order on $X$ is total, $d_{1}(n)>d_{2}(n)$ implies the
existence of $x\in X$ such that $d_{1}(n)\geq x$ and $d_{2}(n)<x$ (it suffices
to take $x=d_{1}(n)$). Because $X$ is finite, $d_{1}(n)>d_{2}(n)$ for
infinitely many $n$ implies failure of $\\{n\,|\,d_{1}(n)\geq
x\\}\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}\\{n\,|\,d_{2}(n)\geq
x\\}$ for some $x$. ∎

######  Lemma 7.0.

Given a unary weighted automaton $\mathcal{W}$, the associated problem whether
$d_{s,t}(n)\leq d_{s^{\prime},t}(n)$ for all but finitely many
$n\in\mathbb{N}$ is in $\coNP$.

###### Proof.

Given an admissible pair $x=(\rho,k)$, we construct an NFA $\mathcal{N}_{s,x}$
accepting $\\{a^{n}\ |\ d_{s,t}(n)\geq x\\}$ (similarly
$\mathcal{N}_{s^{\prime},x}$ for $s^{\prime}$), by taking the NFA
$\mathcal{N}_{s}(\mathcal{W}^{\dagger})$ (Definitions 2, 7.2) with a suitable
choice of accepting states. Recall that states in $\mathcal{W}^{\dagger}$ are
of the form $(q,\rho^{\prime},k^{\prime})$, where $q$ is a state from
$\mathcal{W}$ and $(\rho^{\prime},k^{\prime})$ is admissible. If we designate
states $(t,\rho^{\prime},k^{\prime})$ with $(\rho^{\prime},k^{\prime})\geq x$
as accepting, it will accept $\\{a^{n}\ |\ d_{s,t}(n)\geq x\\}$. This is a
polynomial-time construction.

Then, by Lemma 7.2, the problem whether $d_{s,t}(n)\leq d_{s^{\prime},t}(n)$
for all but finitely many $n\in\mathbb{N}$ is equivalent to
$\mathcal{L}(\mathcal{N}_{s,x})\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}\mathcal{L}(\mathcal{N}_{s^{\prime},x})$
for all admissible $x$. As there are at most $|Q|^{2}$ values of $x$ and each
can be verified co-nondeterministically in $\coNP$, it suffices to show that
deciding
$\mathcal{L}(\mathcal{N}_{s,x})\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}\mathcal{L}(\mathcal{N}_{s^{\prime},x})$
is in $\coNP$ for each $x$. This is the case by Lemma 7.2. ∎

Section 7.2, Section 6, and Section 7.2 together complete the upper bound
result for Section 7.

######  Remark 7.0.

Section 7.2 may appear simpler using
$\\{n\,|\,d_{1}(n)=x\\}\mathrel{{\ooalign{\hss\raisebox{-2.58334pt}{\small$\sim$}\hss\cr\raisebox{1.72218pt}{$\subset$}}}}\\{n\,|\,d_{2}(n)\geq
x\\}$. However, it does not seem possible to construct an NFA for $\\{a^{n}\
|\ d_{s,t}(n)=x\\}$ in polynomial time. Taking just $(t,\rho,k)$, for
$x=(\rho,k)$, as accepting would not be correct, as there could be paths of
the same length ending in $(t,\rho^{\prime},k^{\prime})$ with
$(\rho^{\prime},k^{\prime})>(\rho,k)$. Using $d_{1}(n)\geq x$ instead of
$d_{1}(n)=x$ avoids this problem.

######  Remark 7.0.

An alternative approach for obtaining an upper bound could be to compute the
Jordan normal form of the transition matrix and consider its powers. Instead
of the interplay of strongly connected components in the transition graph, we
would need to consider linear combinations of the $n$th powers of complex
numbers (such as roots of unity). It is not clear this algebraic approach
leads to a representation more convenient for our purposes.

###  7.3. $\coNP$-hardness for unary LMC

Given a unary NFA $\mathcal{N}$, the NFA universality problem asks if
$\mathcal{L}(\mathcal{N})=\\{a^{n}\ |\ n\in\mathbb{N}\\}$. This problem is
$\coNP$-complete [SM73]. We exhibit a polynomial-time reduction from (a
variant of) the unary universality problem to the big-O problem on unary
Markov chains.

######  Theorem 7.0.

The big-O problem is $\coNP$-hard on unary Markov chains.

Let us first consider a particular form of unary NFAs.

######  Definition 7.0.

A unary NFA $\mathcal{N}=\langle Q,\to,q_{s},F\rangle$ is in Chrobak normal
form [Chr86] if

  * •

$Q=S\uplus C^{1}\uplus\dots\uplus C^{m}$ and $q_{s}\in S$;

  * •

$S=\\{s_{1},\cdots,s_{k}\\}$, $q_{s}=s_{1}\in S$ and transitions between
states from $S$ form a path
$s_{1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}s_{2}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}\dots\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}s_{k}$;

  * •

$C^{i}=\\{c^{i}_{0},\cdots,c^{i}_{|C^{i}|-1}\\}$ ($1\leq i\leq m$) and
transitions between states from $C^{i}$ form a cycle
$c^{i}_{0}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}c^{i}_{1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}\dots\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}{c^{i}_{|C^{i}|-1}}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}c^{i}_{0}$;

  * •

the remaining transitions connect the end of the path to each cycle:
$s_{k}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{a}c^{i}_{0}$
for all $1\leq i\leq m$.

Any unary NFA can be translated to this representation with at most quadratic
blow-up in the size of the machine [Chr86], and such representation can be
found in polynomial time [To09, Mar02]. In addition, to simplify our
arguments, we introduce a restricted Chrobak normal form, which requires that
there is exactly one accepting state in each cycle. This restricted form can
be found with at most a further quadratic blow-up over Chrobak normal form, by
creating copies of cycles—one for each accepting state in the cycle.

Observe that $S\subseteq F$ is a necessary condition for the universality of a
unary NFA in Chrobak normal form. Consequently, the universality problem for
unary NFA in restricted Chrobak normal form such that $k=1$ is already
$\coNP$-hard. This is the problem we are going to reduce from in the
following.

###### Proof of Section 7.3.

Let $\mathcal{N}=\langle
Q,\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{},q_{s},F\rangle$
be a unary NFA in restricted Chrobak normal form with $k=1$. We will construct
a unary Markov chain $\mathcal{M}$, depicted in Fig. 6, with states
$Q^{\prime}=Q\cup\\{s,u,v,t\\}$, where $t$ is final.

Figure 6. Reduction from NFA (left) to LMC (right)

The branch starting from $s$, defined below, guarantees
$f_{s}(a^{n})=\Theta\left((\frac{1}{2})^{n}\right)$.

$s\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{1}u\quad\quad
u\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\frac{1}{2}}u\quad\quad
u\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\frac{1}{2}}t$

We take $s^{\prime}=q_{s}$ and create a similar branch from $s^{\prime}$,
albeit with a smaller weight, to create paths of weight
$\Theta\left((\frac{1}{4})^{n}\right)$ when reading $a^{n}$.

$s^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\frac{1}{m+1}}v\quad\quad
v\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\frac{1}{4}}v\quad\quad
v\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\frac{3}{4}}t$

Moreover, we add weights to the original NFA transitions from $\mathcal{N}$ as
follows:

$\begin{array}[]{lll}s^{\prime}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{\frac{1}{m+1}}c^{i}_{0}\quad(1\leq
i\leq m)&&c^{i}_{j\ominus
1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{(\frac{1}{2})^{|C^{i}|}}c^{i}_{j}\quad(c^{i}_{j}\in
F)\\\\[8.53581pt] c^{i}_{j\ominus
1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{1-(\frac{1}{2})^{|C^{i}|}}t\quad(c^{i}_{j}\in
F)&&c^{i}_{j\ominus
1}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle$}]{1}c^{i}_{j}\quad(c^{i}_{j}\not\in
F)\end{array}$

where $j\ominus 1=(|C^{i}|+j-1)\bmod|C^{i}|$. Note that the weights have been
selected as if each letter were read with weight $\frac{1}{2}$ except for a
bounded number of transitions, where the bound is $\max|C^{i}|$. Consequently,
whenever there are accepting paths for $a^{n}$ in $\mathcal{N}$, their overall
weight in $\mathcal{M}$ will be $\Theta\left((\frac{1}{2})^{n}\right)$.

It it easy to check that the reduction produces an LMC and can be carried out
in polynomial time. It remains to argue that the reduction is correct.

If $\mathcal{N}$ is not universal, there exists $n$ such that $a^{n}\not\in
F$. Because of the cyclic structure of Chrobak normal form, $a^{n_{k}}\not\in
F$ for $n_{k}=n+kq$, where $q=\operatorname*{lcm}\\{|C^{1}|,\dots,|C^{m}|\\}$
and $k\in\mathbb{N}$. Then, by the earlier observations about growth, there
exists $C>0$ such that
$\sup_{k}\frac{f_{s}(a^{n_{k}})}{f_{s^{\prime}}(a^{n_{k}})}=\sup_{k}C\,\frac{(1/2)^{n_{k}}}{(1/4)^{n_{k}}}=\sup_{k}C\,2^{n_{k}}=\infty$,
i.e. $s$ is not big-O of $s^{\prime}$.

If $\mathcal{N}$ is universal then, starting from $s^{\prime}$ in
$\mathcal{M}$, every word $a^{n}$ will have a path weighted
$\Theta\left((\frac{1}{4})^{n}\right)$ as well as paths weighted
$\Theta\left((\frac{1}{2})^{n}\right)$. Hence, there exists $C>0$ such that

$\sup_{n}\left(\frac{f_{s}(a^{n})}{f_{s^{\prime}}(a^{n})}\right)\leq\sup_{n}\left(C\,\frac{(\frac{1}{2})^{n}}{(\frac{1}{4})^{n}+(\frac{1}{2})^{n}}\right)\leq
C,$

i.e. $s$ is big-O of $s^{\prime}$. ∎

######  Remark 7.0.

We note that the $\frac{1}{4}$ branch via state $v$ is not strictly necessary,
but it demonstrates that the problem is hard even if the LC condition is
satisfied (i.e., “it can be the numbers that make the hardness”).

##  8\. Decidability for weighted automata with bounded languages

In this section we consider the big-O problem for a weighted automaton
$\mathcal{W}$ and states $s,s^{\prime}$ such that
$\mathcal{L}_{s}(\mathcal{W})$, $\mathcal{L}_{s^{\prime}}(\mathcal{W})$ are
bounded. Throughout the section, we assume that the LC condition has already
been checked, i.e.
$\mathcal{L}_{s}(\mathcal{W})\subseteq\mathcal{L}_{s^{\prime}}(\mathcal{W})$.
We will show that the problem is conditionally decidable, subject to
Schanuel’s conjecture. We give a quick introduction to this conjecture in
Section 8.1.

######  Theorem 8.0.

Given a weighted automaton $\mathcal{W}=\langle Q,\Sigma,M,F\rangle$,
$s,s^{\prime}\in Q$, with $\mathcal{L}_{s}(\mathcal{W})$ and
$\mathcal{L}_{s^{\prime}}(\mathcal{W})$ bounded, it is decidable whether $s$
is big-O of $s^{\prime}$, subject to Schanuel’s conjecture.

Before delving into proof details, we illustrate the arising challenges using
a simple representative example in Section 8.2. After that, the proof of
Section 8 is spread over Sections 8.3, 8.4 and 8.5. First, a version of
Section 8 restricted to plus-letter-bounded languages is shown (Section 8.3 in
Section 8.3). Subsequently, letter-bounded languages are also captured by
reduction to this case (Section 8.4 in Section 8.4). Finally, the case of
bounded languages is reduced to the case of letter-bounded languages (Section
8.5) in Section 8.5.

###  8.1. Logical theories of arithmetic and Schanuel’s conjecture

In _first-order logical theories of arithmetic,_ variables denote numbers
(from $\mathbb{Z}$ or $\mathbb{R}$, as appropriate), and atomic predicates are
equalities and inequalities between terms built from variables and function
symbols. Nullary function symbols are constants, always from $\mathbb{Z}$. If
binary addition and multiplication are available, then:

  * •

for $\mathbb{R}$ we obtain the first-order theory of the reals, where the
truth value of sentences is decidable due to the celebrated Tarski–Seidenberg
theorem [BPR06, Chapter 11 and Theorem 2.77];

  * •

for $\mathbb{Z}$, the first-order theory of the integers is, in contrast,
undecidable (see, e.g, [Poo03]).

In the case of $\mathbb{R}$, adding the unary symbol for the exponential
function $x\mapsto e^{x}$ leads to _the first-order theory of the real numbers
with exponential function_ ($\mathrm{Th}(\mathbb{R}_{\mathsf{exp}})$).
Logarithms base 2, for example, are easily expressible in
$\mathrm{Th}(\mathbb{R}_{\mathsf{exp}})$. The decidability of
$\mathrm{Th}(\mathbb{R}_{\mathsf{exp}})$ is an open problem and hinges upon
Schanuel’s conjecture [MW96].

_Schanuel’s conjecture_ [Lan66] is a unifying conjecture of transcendental
number theory, saying that for all $z_{1},\dots,z_{n}\in\mathbb{C}$ linearly
independent over $\mathbb{Q}$ the field extension
$\mathbb{Q}(z_{1},\dots,z_{n},e^{z_{1}},\dots,e^{z_{n}})$ has transcendence
degree at least $n$ over $\mathbb{Q}$, meaning that for some
$S\subseteq\\{z_{1},\dots,z_{n},e^{z_{1}},\dots,e^{z_{n}}\\}$ of cardinality
$n$, say $S=\\{s_{1},\ldots,s_{n}\\}$, the only polynomial $p$ over
$\mathbb{Q}$ satisfying $p(s_{1},\ldots,s_{n})=0$ is $p\equiv 0$. See, e.g.,
Waldschmidt’s book [Wal00, Section 1.4] for further context. If indeed true,
this conjecture would generalise several known results, including the
Lindemann–Weierstrass theorem and Baker’s theorem, and would entail the
decidability of $\mathrm{Th}(\mathbb{R}_{\mathsf{exp}})$. A recent exciting
line of research reduces problems from verification [DJL+21, MSS20], linear
dynamical systems [ACOW18, COW16], and symbolic computation [HLXL18] to the
decision problem for $\mathrm{Th}(\mathbb{R}_{\mathsf{exp}})$.

###  8.2. Difference to the unary case

In the unary case, it was sufficient to consider the relative order between
spectral radii, with careful handling of the periodic behaviour. This approach
is insufficient in the bounded case. Section 8.2 highlights that the actual
values of the spectral radii have to be examined.

######  Example 8.0 (Relative orderings are insufficient).

Figure 7. Relative orderings are the same, but the big-O relations are
different.

Consider the LMC in Fig. 7, with $0.61\leq p\leq 0.62$. We have
$f_{s}(a^{m}b^{n})=\Theta(0.6^{m}0.4^{n})$ and
$f_{s^{\prime}}(a^{m}b^{n})=\Theta(p^{m}0.39^{n}+0.59^{m}0.41^{n})$. Note that
neither $0.59^{m}0.41^{n}$ nor $p^{m}0.39^{n}$ dominate, nor are dominated by,
$0.6^{m}0.4^{n}$ for any value of $0.61\leq p\leq 0.62$. That is, there are
values of $m,n$ where $0.59^{m}0.41^{n}\gg 0.6^{m}0.4^{n}$ (in particular
large $n$) and values of $m,n$ where $0.59^{m}0.41^{n}\ll 0.6^{m}0.4^{n}$ (in
particular large $m$); similarly for $p^{m}0.39^{n}$ vs $0.6^{m}0.4^{n}$ (but
the cases in which $n$ or $m$ needs to be large are swapped). However, the
big-O status can be different for different values of $p\in[0.61,0.62]$,
despite the same relative ordering between spectral radii. When $p=0.62$, the
ratio turns out to be bounded:

$\frac{f_{s}(aa^{m}ab^{n}b)}{f_{s^{\prime}}(aa^{m}ab^{n}b)}=\frac{1\cdot
0.6^{m}\cdot 0.4\cdot 0.4^{n}\cdot 0.6}{0.5\cdot 0.59^{m}\cdot 0.41\cdot
0.41^{n}\cdot 0.59+0.5\cdot 0.62^{m}\cdot 0.38\cdot 0.39^{n}\cdot
0.61}\leq\frac{1600}{1579}$

for all $m,n$ (in particular, maximal at $m=n=0$,
$\frac{f_{s}(aab)}{f_{s^{\prime}}(aab)}=\frac{1600}{1579}$, for all larger
$m,n$ the ratio is smaller).

In contrast, when $p=0.61$, we have
$\frac{f_{s}(a^{m}b^{0.66m})}{f_{s^{\prime}}(a^{m}b^{0.66m})}\xrightarrow[\raisebox{5.59721pt}[0.0pt]{$\scriptstyle
m\to\infty$}]{}\infty$. To see that, observe there is an $x\in\mathbb{Q}$ such
that $0.61\cdot 0.39^{x}<0.6\cdot 0.4^{x}$ and $0.59\cdot 0.41^{x}<0.6\cdot
0.4^{x}$, e.g., $x=0.66$. We can take $m=xn$ such that $m,n\in\mathbb{N}$ and
$m,n\to\infty$. Whilst useful for illustration in this example, this effect is
not limited to a linear relation between the characters, and so heavier
machinery is required.

We first prove Section 8 for the plus-letter-bounded case, which is the most
technically involved; the other bounded cases will be reduced to it. In the
plus-letter-bounded case, we will characterise the behaviour of such automata,
generalising $(\rho,k)$-pairs of the unary case. We will need to rely upon the
first-order theory of the reals with exponentials to compare these behaviours.

###  8.3. The plus-letter-bounded case

We assume $\mathcal{L}_{s^{\prime}}(\mathcal{W})\subseteq a_{1}^{+}\cdots
a_{m}^{+}$, where $a_{1},\cdots,a_{n}\in\Sigma$ and, because the LC condition
holds, we also have $\mathcal{L}_{s}(\mathcal{W})\subseteq a_{1}^{+}\cdots
a_{m}^{+}$. In the plus-letter-bounded cases, without loss of generality, we
assume $a_{i}\neq a_{j}$ for $i\neq j$. Then any word $w=a_{1}^{n_{1}}\dots
a_{m}^{n_{m}}$ is uniquely specified by a vector
$(n_{1},\dots,n_{m})\in\mathbb{N}^{m}_{>0}$, where $n_{i}$ is the number of
$a_{i}$’s in $w$.

######  Proposition 8.0.

In the plus-letter-bounded cases, without loss of generality, we may assume
$a_{i}\neq a_{j}$ for $i\neq j$.

###### Proof.

We show how to reduce the big-O problem in the plus-letter-bounded case to the
version of the same problem where $a_{i}\neq a_{j}$ (for $i\neq j$). Suppose,
as above, $\mathcal{L}_{s^{\prime}}(\mathcal{W})\subseteq a_{1}^{+}\cdots
a_{m}^{+}$. We can assume $a_{i}\neq a_{i+1}$ ($1\leq i<m$) because
$a^{+}a^{+}$ can be replaced with $a^{+}$ (even though this results in a less
restrictive “bounding” expression). If $\mathcal{W}$ had an $a$-labelled
transition that can be used in two different blocks $a_{i}^{+}$ and
$a_{j}^{+}$ ($j\geq i+2$) within $a_{1}^{+}\cdots a_{m}^{+}$, then
$a=a_{i}=a_{j}$ and this transition could be used to “skip” the block
$a_{i+1}^{+}$, i.e., there would exist a word
$w\in\mathcal{L}_{s^{\prime}}(\mathcal{W})$ that does not use the
$a_{i+1}^{+}$ block, contradicting
$\mathcal{L}_{s^{\prime}}(\mathcal{W})\subseteq a_{1}^{+}\cdots a_{m}^{+}$.
Therefore, every transition can be associated with exactly one block. So we
can define a fresh alphabet $\Sigma^{\prime}=\\{b_{1},\ldots,b_{m}\\}$ and
relabel each transition associated with the $i$th block by $b_{i}$. ∎

Our proof plan, for the plus-letter-bounded case (i.e., in the present Section
8.3), will pass the following milestones:

  1. (1)

Generalise the degree function $d$ from Section 7.2 to non-unary words.
(Section 8.3 and Section 8.3 below.)

  2. (2)

Generalise the big-$\Theta$ lemma (Section 7.2), to lower- and upper-bound the
values $f_{s}(a_{1}^{n_{1}}a_{2}^{n_{2}}\nobreak\dots a_{m}^{n_{m}})$ by more
convenient expressions, sometimes called “exponential polynomials”. (Section
8.3.)

  3. (3)

Characterise the negative instances of the big-O problem. (Section 8.3.)

  4. (4)

Show that this characterisation is effective, assuming Schanuel’s conjecture.
(Section 8.3.)

A comment on the third milestone is in order. In the unary case, an effective
characterisation of positive vis-a-vis negative instances of the big-O problem
(Section 7.2) can be obtained by “mimicking” the behaviour of the original
automaton, once the big-$\Theta$ lemma is in place. As it turns out, the non-
unary case creates a more subtle, multivariate situation. Our new
characterisation (Section 8.3) will involve, in particular, the existence of a
sequence of vectors with some properties. Accordingly, new arguments will be
required (involving further automata and logic) to show algorithmic
decidability.

We will now carry out the plan above.

Like in Section 7.2, we define a degree function $d$, which will be used to
study the asymptotic behaviour of words. This time we will associate a
separate $(\rho,k)$ pair to each of the $m$ characters and, consequently,
words will induce sequences of the form
$(\rho_{1},k_{1})\cdots(\rho_{m},k_{m})$.

Further, as there may be multiple, incomparable behaviours, words will induce
sets of such sequences, i.e.
$d\colon\mathbb{N}^{m}\to\mathcal{P}((\mathbb{R}\times\mathbb{N})^{m})$. For
the sake of comparisons, it will be convenient to focus on maximal elements
with respect to the pointwise order on $(\mathbb{R}\times\mathbb{N})^{m}$,
written $\leq$, where the lexicographic order (recall Section 7.1) is used to
compare elements of $\mathbb{R}\times\mathbb{N}$.

Recall from the discussion in Section 7.2, that our big-$\Theta$ lemma
(Section 7.2) does not capture the asymptotics when $n\leq|Q|$ because it
cannot distinguish between short paths with no loops and non-paths. In the
unary case this is inconsequential as small words are covered by the finitely
many exceptions and the LC condition. However, here, a small number of one
character may be used to enable access to a particular part of the automaton
in another character. For this case, we introduce a new number
$\delta=\frac{1}{2}\min_{\varphi{}:\rho_{\varphi}{}>0}\rho_{\varphi}{}$ which
is strictly smaller than the spectral radius of every non-zero SCC (so will
not dominate with the partial order), but non-zero. This allows us to
distinguish between no-path using the $(0,0)$-pair and a short non-looping
path using the $(\delta,0)$-pair.

######  Definition 8.0.

Let
$\hat{\rho}=(\rho_{1},k_{1}),\cdots,(\rho_{m},k_{m})\in(\mathbb{R}\times\mathbb{N})^{m}$.
An $a_{1}^{n_{1}}a_{2}^{n_{2}}\dots a_{m}^{n_{m}}$-labelled path from $s$ (to
the final state) is _compatible with_ $\hat{\rho}$ if, for each $i=1,\dots,m$,
it visits $k_{i}+1$ SCCs with spectral radius $\rho_{i}$ while reading
$a_{i}$, unless the path visits only singletons with no loops, in which case
$(\rho_{i},k_{i})=(\delta,0)$. The notation $(\rho,k)\in\hat{\rho}$ is used
for “$(\rho,k)$ is an element of $\hat{\rho}$”.

######  Definition 8.0.

Let $d_{s}:\mathbb{N}^{m}\to\mathcal{P}((\mathbb{R}\times\mathbb{N})^{m})$ be
s.t.: $\hat{\rho}\in d_{s}(n_{1},\dots,n_{m})$ if and only if

  1. (1)

there exists an $a_{1}^{n_{1}}a_{2}^{n_{2}}\dots a_{m}^{n_{m}}$-labelled path
from $s$ to the final state compatible with $\hat{\rho}$, and

  2. (2)

for every $a_{1}^{n_{1}}a_{2}^{n_{2}}\dots a_{m}^{n_{m}}$-labelled path from
$s$ compatible with $\hat{\sigma}$ s.t. $\hat{\rho}\leq\hat{\sigma}$, we have
$\hat{\rho}=\hat{\sigma}$.

Observe that $\hat{\rho}$ may range over at most $|Q|^{2m}$ possible values.
Let $\mathcal{D}$ be the set of all of them, so that
$d_{s}:\mathbb{N}^{m}\to\mathcal{P}(\mathcal{D})$. In this extended setting,
the big-$\Theta$ lemma (Section 7.2) may be generalised as follows.

######  Lemma 8.0.

Denote $z(n_{1},\cdots,n_{m})=\sum_{\hat{\rho}\in
d_{s}(n_{1},\dots,n_{m})}\;\prod_{(\rho_{i},k_{i})\in\hat{\rho}}\
\rho_{i}^{n_{i}}\cdot n_{i}^{k_{i}}.$
There exist $c,C>0$ such that for all $n_{1}\dots,n_{m}\in\mathbb{N}$:

$c\cdot z(n_{1},\cdots,n_{m})\leq f_{s}(a_{1}^{n_{1}}a_{2}^{n_{2}}\dots
a_{m}^{n_{m}})\leq C\cdot z(n_{1},\cdots,n_{m}).$

###### Proof.

$\displaystyle f_{s}(a_{1}^{n_{1}}a_{2}^{n_{2}}\dots a_{m}^{n_{m}})$
$\displaystyle=(M(a_{1})^{n_{1}}\times M(a_{2})^{n_{2}}\times\dots\times
M(a_{m})^{n_{m}})_{s,t}$ $\displaystyle=\sum_{q_{1}\in
Q}M(a_{1})^{n_{1}}_{s,q_{1}}(\times M(a_{2})^{n_{2}}\times\dots\times