Decidability of cutpoint isolation for probabilistic
finite automata on letter-bounded inputs
Paul C. Bell
Department of Computer Science, James Parsons Building, Byrom Street, Liverpool John Moores
University, Liverpool, L3 3AF, UK
p.c.bell@ljmu.ac.uk

Pavel Semukhin
Department of Computer Science, University of Oxford, Wolfson Building, Parks Road, Oxford,
OX1 3QD, UK
pavel.semukhin@cs.ox.ac.uk

Abstract
We show the surprising result that the cutpoint isolation problem is decidable for probabilistic finite
automata where input words are taken from a letter-bounded context-free language. A context-freelanguage L is letter-bounded when L ⊆ a∗1 a∗2 · · · a∗` for some finite ` > 0 where each letter is distinct.
A cutpoint is isolated when it cannot be approached arbitrarily closely. The decidability of thisproblem is in marked contrast to the situation for the (strict) emptiness problem for PFA which isundecidable under the even more severe restrictions of PFA with polynomial ambiguity, commutative
matrices and input over a letter-bounded language as well as to the injectivity problem which isundecidable for PFA over letter-bounded languages. We provide a constructive nondeterministic
algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentiallyambiguous. We also show that the problem is at least NP-hard and use our decision procedure tosolve several related problems.
2012 ACM Subject Classification Theory of computation → Formal languages and automata theory;
Theory of computation → Computability; Theory of computation → Probabilistic computation
Keywords and phrases Probabilistic finite automata, cutpoint isolation problem, letter-bounded
context-free languages
Digital Object Identifier 10.4230/LIPIcs.CONCUR.2020.20
Related Version A full version of the paper is available at https://arxiv.org/abs/2002.07660.

1

Introduction

Probabilistic finite automata (PFA) are an extension of classical nondeterministic finite
automata (NFA) where transitions, for each state and letter, are represented as probability
distributions. The PFA model was first introduced by Rabin [23].
There are a variety of classical problems for PFA. Let P denote a PFA, Σ an alphabetand λ ∈ [0, 1] a probability. The acceptance probability of P on a word w ∈ Σ∗ is denotedfP (w). A central question is (strict) emptiness of cutpoint languages: does there exist a finite
input word w for which fP (w) ≥ λ (or fP (w) > λ for strict emptiness). Another important
problem is that of cutpoint isolation — to determine if λ can be approached arbitrarilyclosely, i.e., for each  > 0, does there exist a word w ∈ Σ such that |fP (w) − λ| <  (or theconverse, does there exist δ > 0 such that |fP (w) − λ| ≥ δ for all w ∈ Σ∗ )? The value-1
problem is a special case of the cutpoint isolation when λ = 1 [13]. In the injectivity problem
we must determine if fP (w) is injective (i.e. do there exist two distinct words with thesame acceptance probability?) In the λ-probability problem we must determine if there exists
w ∈ Σ∗ such that fP (w) = λ.
The emptiness problem is undecidable for rational matrices [22], even over a binary© Paul C. Bell and Pavel Semukhin;licensed under Creative Commons License CC-BY
31st International Conference on Concurrency Theory (CONCUR 2020).
Editors: Igor Konnov and Laura Kovács; Article No. 20; pp. 20:1–20:16
Leibniz International Proceedings in Informatics
Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

20:2

Decidability of cutpoint isolation for PFA on letter-bounded inputs

alphabet when the PFA has dimension 46 [6], later improved to dimension 25 [18]. The
injectivity problem for PFA is undecidable [3], even for polynomially ambiguous PFA [2].
The main focus of this paper is the cutpoint isolation problem. The authors of [5] showthat the problem of determining if a given cutpoint is isolated (resp. if a PFA has any
isolated cutpoint) is undecidable and this was shown to hold even for PFA with 420 (resp.
2354) states over a binary alphabet [6]. The cutpoint isolation problem, in the special casewhere λ = 1 (the value-1 problem), is also known to be undecidable [13]. The problem is
especially interesting given the seminal result of Rabin that if a cutpoint λ is isolated, thenthe cutpoint language associated with λ is necessarily regular [23].
Most problems are undecidable for PFA and there exist very few algorithmic solutions [13].
Various classes of restrictions on PFA are possible, related to the number of states, thealphabet size and whether one defines the PFA over the algebraic reals or the rationals.
Recent work has studied PFA with finite, polynomial or exponential ambiguity (in termsof the underlying NFA) [10], PFA defined for restricted input words (e.g. those comingfrom bounded or letter-bounded languages) [3, 4], commutative PFA, where all transition
matrices commute, for which cutpoint languages and non-free languages generated by suchautomata become commutative [2] or other structural restrictions on the PFA such as#-acyclic automata, for which some problems become decidable [13], including the value-1
problem. Such #-acyclic automata impose a restriction on the structure of the PFA (as weshall see, we only restrict the input words).
A natural restriction on PFA was studied in [4], where input words of the PFA are
restricted to be from a letter-bounded language (also known as a letter-monotonic language)of the form L = a∗1 a∗2 · · · a∗` with distinct letters ai ∈ Σ. This is analogous to a 1.5-way PFA,
whose read head may “stay put” on an input letter but never moves left. This may model asituation where we have some finite number of probabilistic events and we know that there
is a fixed order and number of transitions between them, but with each event being applied
an arbitrary number of times. The model is also related to “promise problems” whereby werestrict the decision question to a subset of possible inputs [16]. Letter-bounded languages
allow a natural and substantial extension to decision questions on a unary alphabet.
The emptiness and λ-probability problems for PFA on letter-bounded languages wereshown to be undecidable for high (finite) dimensional matrices via an encoding of Hilbert’stenth problem on the solvability of Diophantine equations and Turakainen’s method totransform weighted integer automata to probabilistic automata [25]. These undecidability
results also hold for polynomially ambiguous PFA with commutative matrices [2].
The authors of [10] studied decision problems for PFA of various degrees of ambiguity.
The degree of ambiguity (finite, polynomial or exponential) of a PFA is a structural property,
giving an indication of the number of accepting runs for a given input word. The degree of
ambiguity of automata is a well-known and well-studied property in automata theory [26].
The authors of [10] show that the emptiness problem for PFA remains undecidable even forpolynomially ambiguous automata (quadratic ambiguity), show PSPACE-hardness results
for finitely ambiguous PFA and that emptiness is in NP for the class of k-ambiguous PFA
for every k > 0. The emptiness problem for PFA was later shown to be undecidable forlinearly ambiguous automata [9].

1.1

Our Contributions

It is natural to consider the decidability of the cutpoint isolation problem for polynomiallyambiguous PFA on letter-bounded or commutative languages, given that the (strict) emptinessproblems for such automata are undecidable [2]. In the present paper we prove the surprisingP. C. Bell and P. Semukhin

20:3

result that the cutpoint isolation problem is in fact decidable, even if the PFA is exponentiallyambiguous, matrices are non-commutative, and the input language is not just the letterbounded language a∗1 · · · a∗` but instead a more general letter-bounded context-free language.
The results are shown in Table 1.

Problem

Polynomial ambiguity

Letter-bounded

Polynomial ambiguity;

CFL input;

letter-bounded input;

Exponential ambiguity

commutative matrices(Strict) Emptiness

Undecidable [9, 10, 22]⇐=⇐=

Undecidable [2]Cutpoint isolation

Undecidable [5, 10]

Decidable=⇒

Table 1 The decidability of problems under different restrictions on the PFA. The main result of
this paper is shown in boldface. Symbol =⇒ denotes that decidability is implied by the decidabilityof the more general model; ⇐= denotes that undecidability is implied by the more restricted model.

The result is surprising since in order to solve the cutpoint isolation problem, we mustsolve two subproblems. Either the cutpoint λ can be reached exactly (the λ-probability
problem), or else it can only be approximated arbitrarily closely and is only reached exactly
in some limit. As mentioned, the emptiness problem for cutpoint languages is undecidable
for polynomially ambiguous PFA on letter-bounded languages, even when all matrices
commute [2]. The proof of this result shows a construction of a PFA for which determining
if a given λ ∈ [0, 1] is ever reached (i.e., the λ-probability problem) is undecidable. This may
at first seem to contradict the results of this paper, since the λ-probability problem is one of
the two subproblems to be solved for cutpoint isolation. Why is there no contradiction then?
It comes from the fact that as the powers of matrices used in the PFA constructed in [2]increase, the PFA valuation tends towards the limit value λ. Therefore, this λ is always
non-isolated and hence the cutpoint isolation problem for such constructed PFA and λ isdecidable. However, determining if the PFA ever exactly reaches λ is undecidable. So, there
is no contradiction with the results of this paper. Our main result is stated as follows.
I Theorem 1. The cutpoint isolation problem for probabilistic finite automata where inputs
are constrained to a given letter-bounded context-free language is decidable. Moreover, if the
cutpoint is isolated, then a separation bound  > 0 can be computed such that no input word’s
acceptance probability lies within  of the cutpoint.
The proof of Theorem 1 is found in Section 3. Our proof technique for showing thedecidability of cutpoint isolation for PFA on letter-bounded languages uses the following
crucial facts. If a PFA over a letter-bounded context-free language can approach somegiven cutpoint λ arbitrarily closely, then the PFA can reach λ exactly if we allow a subsetof the matrices to be taken to one of their ‘limiting powers’. We use the property thateach limiting power (of which there may be finitely many) of a stochastic matrix can becomputed in polynomial time (see Lemma 6), as well as a crucial property from linear algebrathat dominant eigenvalues (those of strictly largest magnitude) of a stochastic matrix arenecessarily of magnitude 1, roots of unity and they have equal geometric and algebraic
multiplicities (see Lemma 5). Since the input words of the PFA come from a letter-bounded
CFL, we also use the fact that a letter-bounded language is context-free if and only if its
Parikh image is a stratified semilinear set (see Proposition 3).
The combination of these ideas allows us to derive Algorithm 1, which works as follows.

CONCUR 2020

20:4

Decidability of cutpoint isolation for PFA on letter-bounded inputs

We initially set all variables as free (rather than fixed), and compute the Parikh image p(L)of the given letter-bounded CFL L. Using the fact that p(L) is a semilinear set, we computewhich letters can be taken to arbitrarily high powers and which letters have fixed finite values.
We then use the technical Proposition 7 which states that if we can reach λ then we caneither do so by setting all free variables to an infinite power (which we denote by ω), or else
we can compute an integer C such that the value of one of free variables must be less than C.
We then either set all free variables as ω in the first case, or nondeterministically choose oneof the free variables and assign it a value less than C in the latter case. In the second case wealso update the semilinear set and repeat the above procedure until no free variables remain.
Finally, we verify that the PFA has exactly the value λ for the chosen values of the variables.
The crucial Proposition 7 is somewhat technical, but relies on splitting a product ofstochastic matrices into a summation involving dominant and subdominant eigenvalues (asubdominant eigenvalue being one with magnitude strictly less than 1) and then applying thespectral decomposition or Jordan normal form of each stochastic matrix in order to derive
the constant C which bounds the value of one of free variables.
Combining our proof technique with a result of Rabin [23], we derive the following result.
I Corollary 9. The emptiness problem is decidable for probabilistic finite automata on
letter-bounded context-free languages when the cutpoint is isolated.
The undecidability of the emptiness problem for PFA over letter-bounded inputs shown in [2]therefore only applies when the cutpoint is non-isolated.
The provided algorithm is nondeterministic in nature although we do not have an upperbound on its complexity. We can however provide the following lower bound via an adaptationof a proof technique from [2] which proved the NP-hardness of the injectivity problem forlinearly ambiguous three-state probabilistic finite automata over letter-bounded languages.
I Theorem 12. Cutpoint isolation is NP-hard for 3-state PFA on letter-bounded inputs.
Our procedure also allows us to answer some equivalent problems (in Section 5), forexample: given a PFA, λ ∈ [0, 1] and a maximum number k ∈ N of alternations between
input letters, determine if λ is isolated. We also prove the value-1 problem is decidable overletter-bounded context-free language inputs.

2Preliminaries

2.1

Probabilistic Finite Automata on Letter-Bounded Inputs

We denote by Fn×n the set of all n × n matrices over some field F. We will primarily beinterested in rational matrices. We use a nonstandard form of Dirac bra-ket notation in several
calculations, to simplify the notation in some complex formulae. If u = (u1 , . . . , un )> ∈ Cn
is a column vector, then we write |ui = u and hu| = u> where u> denotes the transpose ofu, i.e., hu| = (u1 , . . . , un ). Note that Dirac bra-ket notation ordinarily defines that hu| = u∗where u∗ denotes the conjugate transpose of u, however we will not use this notion at any
point. Note that |ui hv| is just a rank 1 matrix u> v. We use hei | and |ei i to denote the i’thbasis row/column vector respectively.
A PFA P with n states over an alphabet Σ is defined as A = (hu| , {Ma |a ∈ Σ}, |vi) wherehu| ∈ Rn is the initial probability distribution; |vi ∈ {0, 1}n is the final state vector and eachMa ∈ Rn×n is a (row) stochastic matrix. For a word w = w1 w2 · · · wk ∈ Σ∗ , we define theacceptance probability fP : Σ∗ → R of P as:fP (w) = hu| Mw1 Mw2 · · · Mwk |vi ,P. C. Bell and P. Semukhin

20:5

which denotes the acceptance probability of w.1
For any λ ∈ [0, 1] and PFA P over alphabet Σ, we define a cutpoint language to be:L≥λ (P) = {w ∈ Σ∗ |fP (w) ≥ λ}, and a strict cutpoint language L>λ (P) by replacing ≥ with>. The (strict) emptiness problem for a cutpoint language is to determine if L≥λ (P) = ∅(resp. L>λ (P) = ∅). Our main focus is on the cutpoint isolation problem, now defined.
I Problem 2 (Cutpoint isolation). Given a PFA P and cutpoint λ ∈ [0, 1], determine if foreach  > 0 there exists some w ∈ Σ∗ such that |fP (w) − λ| < .
Let Σ = {a1 , a2 , . . . , a` } be an alphabet with ` > 0 distinct letters. A language L is called
letter-bounded if L ⊆ a∗1 a∗2 · · · a∗` . If L is letter-bounded and also a context-free language, thenit is called a letter-bounded context-free language. We are interested in cutpoint isolation for
PFA whose inputs come from a given letter-bounded context-free language.
For a letter-bounded language L ⊆ a∗1 a∗2 · · · a∗` , define its Parikh image 2 asp(L) = { (k1 , . . . , k` ) : ak11 ak22 · · · ak` ` ∈ L }.
Recall that a subset Q ⊆ N` is called linear if there are vectors q0 , q1 , . . . , qr ∈ N` such thatQ = { q0 + t1 q1 + · · · + tr qr : t1 , . . . , tr ∈ N }.
We say that a linear set Q is stratified if for each i ≥ 1 the vector qi has at most two nonzero
coordinates, and for any i, j ≥ 1 if both qi and qj have two nonzero coordinates, i1 < i2 andj1 < j2 , respectively, then their order is not i1 < j1 < i2 < j2 , i.e., they are not interlaced.
A finite union of linear sets is called a semilinear set, and a finite union of stratified linear
sets is called a stratified semilinear set.
We will need the following classical fact about context-free languages.
I Proposition 3. If L is a context-free language, then its Parikh image p(L) is a semilinear
set that can be effectively constructed from the definition of L [21].
I Remark 4. There is a nice characterization of the letter-bounded context-free languages.
Namely, a letter-bounded language L ⊆ a∗1 a∗2 · · · a∗` is context-free if and only if p(L) is a
stratified semilinear set [14, 15].
Let A1 , . . . , A` ∈ Qn×n be row stochastic matrices. Let u ∈ Qn be a stochastic vector(the initial vector) and v ∈ {0, 1}n (the final state vector). Let L ⊆ a∗1 a∗2 · · · a∗` be a letterbounded context-free language, and let λ ∈ [0, 1] be a cutpoint for which we want to decide
if it is isolated or not, that is, whether λ belongs to the closure of { hu| Ak11 Ak22 · · · Ak` ` |vi :ak11 ak22 · · · ak` ` ∈ L }.
If λ is not isolated, then there are two scenarios: either there exists k1 , k2 , . . . , k` ∈ N suchthat hu| Ak11 Ak22 · · · Ak` ` |vi = λ, or else λ is never reached but only approached arbitrarilyclosely. In the second case there is a sequence of tuples {(k1m , k2m , . . . , k`m )}∞m=1 such that
km

km

km

λ = lim hu| A11 A22 · · · A` ` |vim→∞and, furthermore, for every t ∈ {1, . . . , `}, either ktm = kt1 for all m ≥ 1, i.e. ktm is fixed, orkm
ktm is strictly increasing and At t converges to a limit as m → ∞.
1

Some authors interchange the order of u and v and use column stochastic matrices, although the two
definitions are trivially isomorphic.
2
In general, the Parikh image of L ⊆ Σ∗ is defined as p(L) = { (|w|a1 , . . . , |w|a` ) : w ∈ L } where |w|ai
denotes the number of occurrences of letter ai in word w.

CONCUR 2020

20:6

Decidability of cutpoint isolation for PFA on letter-bounded inputs

We will use the notation Aω to denote the set of all limits of the sequence {Ak }∞k=1 (seeLemma 6 below for a detailed explanation). It follows that if λ is not isolated, then there
exists a choice of variables k1 , k2 , . . . , k` ∈ N ∪ {ω} such thatλ ∈ hu| Ak11 Ak22 · · · Ak` ` |vi .
ωNote that if kt = ω, then Aω
t is a finite set. In this case we substitute all limits of At in thek`
k1 k2
above formula, and so hu| A1 A2 · · · A` |vi also becomes a finite set.3

2.2

Algebraic numbers

A complex number α is algebraic if it is a root of a polynomial p ∈ Z[x]. The defining
polynomial pα ∈ Z[x] for α is the unique polynomial of least degree with positive leading
coefficient such that the coefficients of pα do not have a common factor and pα (α) = 0. The
degree and height of α are defined to be that of pα .
In order to do computations with algebraic numbers we use their standard representations.
Namely, an algebraic number can be represented by its defining polynomial and a sufficiently
good complex rational approximation. More precisely, α will be represented by a tuple(pα , a, b, r), where pα ∈ Z[x] is the defining polynomial for α and a, b, r ∈ Q are such that
α is the unique root of pα inside the circle in C with centre√ a + bi and radius r. As shown6
in [19], if α 6= β are roots of p ∈ Z[x], then |α − β| > (d+1)/2 d−1 , where d and H are thedHdegree and height of p, respectively. So, if we require r to be smaller than half of this bound,the above representation is well-defined.
Let ||α|| be the size of the standard representation of α, that is, the total bit size of a, b, r
and the coefficients of pα . It is well-known fact that for given algebraic numbers α and β,
one can compute 1/α, ᾱ and |α| in time polynomial in ||α||, and one can compute α + β
and αβ and decide whether α = β in time polynomial in ||α|| + ||β||. Moreover, for a real
algebraic α, deciding whether α > 0 can be done in time polynomial in ||α||. Finally, there isa polynomial time algorithm that for a given p ∈ Z[x] computes the standard representationsof all roots of p. For more information on efficient algorithmic computations with algebraic
numbers the reader is referred to [1, 8, 17, 20].

2.3

Spectral decomposition and Jordan normal forms

We define the spectrum (set of eigenvalues) of A ∈ Rn×n as σ(A) = {λ1 , . . . , λn } arranged
in monotonically nonincreasing order, i.e. |λi | ≥ |λj | for all 1 ≤ i < j ≤ n and we defineσ̂(A) ⊆ σ(A) as the set of eigenvalues of A of absolute value 1. We call eigenvalues σ̂(A)dominant eigenvalues and eigenvalues σ(A) \ σ̂(A) subdominant eigenvalues.
Given A = (aij ) ∈ Fm×m and B ∈ Fn×n , we define the direct sum A ⊕ B of A and B by:


A
0m,n
A⊕B =
, where 0n,m is the n × m zero matrix.
0n,m BWe will use both the spectral decomposition theorem and the Jordan normal form ofstochastic matrices in later proofs. For background, see [11].
Let Ai ∈ Qn×n be a matrix (we use notation Ai since it will prove useful in the proofof Proposition 7), and let {λi,1 , . . . , λi,ni } be the eigenvalues of Ai listed according to
3

0
ω
0
0
If {Ak }∞k=1 has a unique limit A , then we will identify the set A = {A } with the matrix A and write
k1 k2
ω
0
A = A . Also, if all kt ’s are finite or if all limits are unique, we identify the number hu| A1 A2 · · · Ak` ` |vi
with the one element set {hu| Ak1 1 Ak2 2 · · · Ak` ` |vi}.

P. C. Bell and P. Semukhin

20:7

their geometric multiplicities4 . Then Ai can be written in Jordan normal form Ai =Si−1 (J`i,1 (λi,1 ) ⊕ · · · ⊕ J`i,ni (λi,ni ))Si , where Si is an invertible matrix (det(Si ) 6= 0) andJ`i,j (λi,j ) is a `i,j × `i,j Jordan block for 1 ≤ j ≤ ni ≤ n, with ni the number of Jordan
blocks of Ai and `i,j the size of the Jordan block corresponding to eigenvalue λi,j , such that`i,1 + · · · + `i,ni = n. Jordan block J`i,j (λi,j ) corresponds to the j th eigenvalue λi,j of Ai andhas the form:


λi,j
1
0
···
0
 0
λi,j
1
···
0 


 0
0
λi,j · · ·0 J`i,j (λi,j ) =  ∈ C`i,j ×`i,j
 .

.
.
.
.
..
..
..
.. 
 ..
0

0

···

0

λi,j


The matrix Si contains the generalised eigenvectors of Ai . Noting that xy = 0 if y > x, we
now see that k ki −1
 ki −2
 k −(` −1) 
ki
ki
λi,ji
· · · `i,jki−1 λi,ji i,j
1 λi,j2 λi,j ki −1
 k −(` −2) ki 0λki,ji· · · `i,jki−2 λi,ji i,j 
1 λi,j k −(` −3) J`i,j (λi,j )ki =  00λki,ji· · · `i,jki−3 λi,ji i,j  ∈ C`i,j ×`i,j


..
..
..
 ..

..
 .

.
.
.
.
ki
0
0
0
···
λi,j




X
X
ki 
λki,ji −m|ep i hem+p |(1)=m
0≤m≤`i,j −11≤p≤`i,j −m

The spectral decomposition of a matrix is a special case of the Jordan normal form.
Namely, any diagonalizable matrix Ai ∈ Qn×n can be written as
Ai = Si−1 (λi,1 ⊕ · · · ⊕ λi,n )Si =nXλi,j |vi,j i hui,j | ,

(2)

j=1

where σ(M ) = {λi,1 , . . . , λi,n } is the set of eigenvalues of Ai , |vi,j i is the j’th column of Si−1
Pn
and hui,j | is the j’th row of Si . Thus we have Aki = j=1 λki,j |vi,j i hui,j |.
We will also require the following technical lemma concerning the dominant eigenvaluesof stochastic matrices.
I Lemma 5 ( [11, Theorem 6.5.3]). Let λ be a dominant eigenvalue of a stochastic matrix
A ∈ Rn×n . Then λ is a root of unity of order no more than n. Moreover, the geometricmultiplicity of λ is equal to its algebraic multiplicity. In other words, the Jordan blocks that
correspond to λ have size 1 × 1.
We also require the following lemma.
I Lemma 6. For any stochastic matrix A, the sequence {Ak }∞k=1 has a finite number oflimits. Namely, there exist a computable constant d such that, for each r = 0, . . . , d − 1, thesubsequence {Adm+r }∞m=1 converges to a limit, and this limit can be computed in polynomial
time given d and r.
4

Note that ni is the number of linearly independent eigenvectors of Ai or the number of Jordan blocks
in the Jordan normal form of Ai . The matrix Ai is diagonalizable if and only if ni = n. Jordan normal
forms are unique up to permutations of the Jordan blocks.

CONCUR 2020

20:8

Decidability of cutpoint isolation for PFA on letter-bounded inputs

Proof. Let A be a stochastic matrix. As shown in [7], we can compute in polynomial time the
Jordan normal form of A and a transformation matrix S such that A = S −1 JS. Note that A
may have complex eigenvalues, so all computations are done using standard representationsof algebraic numbers as explained in Section 2.2.
By Lemma 5, all dominant eigenvalues of A are roots of unity of orders no more than n,
and their Jordan blocks have size 1 × 1. If λ is a root of unity of order p, then {λk }∞k=1 is aperiodic sequence with period p. On the other hand, if J` (λ) is a Jordan block corresponding
to an eigenvalue λ such that |λ| < 1, then limk→∞ J` (λ)k is equal to the zero matrix.
Let d be the least common multiple of the orders of the roots of unity among the
eigenvalues of A. Now if λ is a dominant eigenvalue of A, then the values of λdm+r = λr do
not depend on m, where r = 0, . . . , d − 1. Hence J dm+r converges to a limit when m → ∞.
This limit is equal to a matrix J 0 obtained from J by replacing all dominant λ with λr
and all Jordan blocks corresponding to subdominant eigenvalues with zero matrices. So,
limm→∞ Adm+r = S −1 J 0 S.
This shows that {Ak }∞k=1 has at most d limits. Finally, we note that d may be exponential
in the dimension of A. However, if {Ak }∞k=1 has a single limit, then this limit can be computedin polynomial time.
J

3

Decidability of Cutpoint Isolation

In this section we will give a proof of Theorem 1 which is our main result. The crucial
ingredient of our proof is the following technical proposition which will be proven in Section 4.
I Proposition 7. Let J = {1, 2, . . . , `} be indices, λ ∈ [0, 1] a cutpoint, and let JF ⊆ J besuch that kt is a free variable, for t ∈ JF , and kt is assigned a fixed finite value, for t ∈ J \ JF .
Theneither λ ∈ hu| Ak11 Ak22 · · · Ak` ` |vi, where kt = ω for all t ∈ JF ,or else there exists a constant C > 0 such that λ ∈ hu| Ak11 Ak22 · · · Ak` ` |vi implies kt < C
for at least one t ∈ JF .
Moreover, we can decide whether the first case holds and compute the constant C in thesecond case.
Below we give a high-level description of the main algorithm (Algorithm 1), which gives
a formal proof of Theorem 1, and explain how Proposition 7 is used there.
Let L ⊆ a∗1 a∗2 · · · a∗` be a given letter-bounded CFL. We start by considering all indicesJ = {1, . . . , `} as free (i.e. their value is not fixed and they will later be given a fixedvalue from N ∪ {ω}) and iteratively fix them until no free indices remain. We first use
Parikh and Ginsburg’s results (Proposition 3) to compute the Parikh image p(L). Then we
nondeterministically choose a linear subset Q and use it to determine the indices which canbe taken to arbitrary high values while staying within Q. These indices will correspond to
the “free variables” in the algorithm.
Let JF be a set of such indices (which will be called R in Algorithm 1). We then set kt
for t ∈ J \ JF to appropriate finite values, while kt with t ∈ JF remain free variables. We
wish to determine if there is a choice of kt ∈ N ∪ {ω} for t ∈ JF such thatλ ∈ hu| Ak11 Ak22 · · · Ak` ` |vi ,that is, whether λ can be reached by setting each free variable kt either to some finite value orelse to ω, an “infinite” power. Proposition 7 then tells us that either all free variables should
be set at ω in order to reach λ (and this is decidable), or else there exists a computableP. C. Bell and P. Semukhin

20:9

constant C such that if we can reach λ by some choice of these free variables, then some
kt < C for an index t ∈ JF .
In the first case, we set all free variables to ω. In the second case, we nondeterministicallychoose some free variable, fix its value in the range [0, C) and then update our linear set Q tosatisfy a new constraint. The procedure repeats iteratively until all free variables have been
assigned a fixed value. The algorithm then verifies if this choice of variables gives a solution.
Stage one (Nondeterministic iterative fixing of free variables):Let T = J = {1, 2, . . . , `}.
Compute the Parikh image p(L) and nondeterministically choose one of its finitely
many linear subsets Q = { q0 + t1 q1 + · · · + tr qr : t1 , . . . , tr ∈ N } ⊆ p(L).awhile T 6= ∅ do
Let R be the set of indices j ∈ T such that at least one qi with i ≥ 1 has a nonzero
jth coordinate.b
For each j ∈ T \ R, the jth coordinate of all vectors from Q is equal to the jthcoordinate of q0 .c So, we set kj for j ∈ T \ R to be the jth coordinate of q0 .
Then, for j ∈ R, compute the limits Aωj with indices respecting set Q(see Remark 8 below for details).
Check whether λ ∈ hu| Ak11 Ak22 · · · Ak` ` |vi, where kj = ω for all j ∈ R.
If yes, return True and stop.
Otherwise, assuming all indices kj for j ∈ J \ R are fixed and R is the set of freevariables, use Proposition 7 to compute the constant C > 0 such thatλ ∈ hu| Ak11 Ak22 · · · Ak` ` |vi implies kj < C for at least one j ∈ R.
Then nondeterministically choose j ∈ R, fix kj ∈ [0, C) and set T ← R \ {j}.
Next, for the chosen index j, find those indices i in {1, . . . , r} for which qi has anonzero jth coordinate. Without loss of generality, suppose {1, . . . , s} are these
indices.
Fixing kj ∈ [0, C), restricts the parameters t1 , . . . , ts in Q to a finite set of possible
values since the vector q0 + t1 q1 + · · · + ts qs must have kj in its jth coordinate.
Nondeterministically choose one of these values for t1 , . . . , ts or return False andstop, if such a choice is impossible.
Let Q ← { (q0 + t1 q1 + · · · + ts qs ) + ts+1 qs+1 + · · · + tr qr : ts+1 , . . . , tr ∈ N }.d
Stage two (Verifying the computation):
At this stage we have fixed all variables k1 , k2 , . . . , k` to some finite values.
Compute hu| Ak11 Ak22 · · · Ak` ` |vi for the obtained values of k1 , . . . , k` ∈ N.
Return True if λ = hu| Ak11 Ak22 · · · Ak` ` |vi or False, otherwise.
End.
Algorithm 1 Nondeterministic algorithm deciding whether a given cutpoint is isolated.
aHere we use the fact that if λ can be approached arbitrarily closely within p(L), then λ can be approachedby staying within one of the finitely many linear subsets of p(L).
bThus R is the subset of indices from T that can be taken to arbitrarily large powers simultaneously.
cThis is because for j ∈ T \ R all qi with i ≥ 1 have zero jth coordinate.
dThus (q0 + t1 q1 + · · · + ts qs ) becomes the new value of q0 in Q.

I Remark 8. To compute the limits Aωj with indices respecting set Q, note that the projectionof Q on the jth coordinate is equal to { q0,j + t1 q1,j + · · · + tr qr,j : t1 , . . . , tr ∈ N }, where qi,jis the jth coordinate of qi . The set hq1,j , . . . , qr,j i = {t1 q1,j + · · · + tr qr,j : t1 , . . . , tr ∈ N }is a finitely generated subsemigroups of (N, +). Let d = gcd(q1,j , . . . , qr,j ), then there is anumber s > 0 such that for any t ≥ s, we have t ∈ hq1,j , . . . , qr,j i if and only if d divides t.

CONCUR 2020

20:10

Decidability of cutpoint isolation for PFA on letter-bounded inputs

This is a well-known property of the subsemigroups of (N, +) [24]. Thus the limits Aωj withq0,jd ωd ωindices respecting Q are equal to Aω
=
A
(A
)
,
where
the
limits(A)
arecomputedjjjjusing Lemma 6.
It remains to prove that we can compute a separation bound  > 0 between λ and theclosest acceptance probability of P for any input word w ∈ L. Algorithm 1 has two stopping
conditions, either by returning True in Stage one (which we discount since it implies the
cutpoint is not isolated), or else after Stage two.
Algorithm 1 has two sources of nondeterminism in Stage one: in the choice of linear
subset Q and then during the while loop in the choice of j ∈ R and kj ∈ [0, C). We will
evaluate every choice of linear subset Q and every choice of j and kj to cover all possible
cases, updating a global variable  at the end of every nondeterministic branch. Initially,
we set  ← ∞, and let 1 , 2 be additional global variables that are set 1 ← 2 ← ∞ at the
beginning of every nondeterministic branch.
During the execution of Stage one we use Proposition 7 to compute C such that if all
free variables are above C then we are at least some 0 > 0 away from λ. Note that 0 isless than half of the distance between λ and some limit values. For each iteration of thewhile loop, we set 1 ← min{1 , 0 } to keep track of the minimal value. During Stage two,
all variables have a fixed finite value, and we set 2 ← | hu| Ak11 Ak22 · · · Ak` ` |vi − λ| which isgreater than zero assuming λ is isolated. Finally, we set  ← min{, 1 , 2 } > 0.
After inspecting all possible nondeterministic runs of the algorithm, the obtained valueof  gives us the separation bound. Indeed, during the execution of the above procedure, is updated to the minimum of 1 and 2 , where 1 is less than half of the distance between
λ and some limit values and 2 keeps track of the distance between λ and the values
hu| Ak11 Ak22 · · · Ak` ` |vi when each index kj is less than the corresponding constant C.

4

Proof of Proposition 7

We begin with a proof sketch. Since each Ai is stochastic, σ̂(Ai ) contains at least one
eigenvalue 1 and all other eigenvalues in σ̂(Ai ) are roots of unity by Lemma 5. All eigenvaluesin σ(Ai ) \ σ̂(Ai ) have absolute value strictly smaller than 1. Our approach is to rewrite theexpression
hu| Ak11 Ak22 · · · Ak` ` |vi(3)

into the sum of two terms (which will be denoted by S0 and S1 ) such that S0 determines thelimit behaviour as all free variables tend towards infinity, since they control only dominanteigenvalues, while S1 is vanishing, since at least one free variable controls a subdominanteigenvalue. We can then reason that if all free variables simultaneously become larger, then
Eqn (3) tends towards a set of computable limits with some vanishing terms. Therefore wecan determine either that we can reach λ when all free variables are ω, or else we can provethat Eqn (3) is within any  > 0 of a limit value once all free variables are sufficiently large,
which proves the proposition (by setting  as less than the smallest difference from a limit
value and λ). We now proceed with the formal details.
First, we consider the simpler case when all matrices are diagonalizable and then show
how to extend this argument to the general case.
Diagonalizable matrices. Let us first assume that all matrices are diagonalizable. By thespectral decomposition theorem (see Eqn (2)), we may write a matrix Aki i as:
Aki i

=

n
X
j=1

λki,ji |vi,j i hui,j | ,(4)

P. C. Bell and P. Semukhin

20:11

where {λi,1 , . . . , λi,n } are the eigenvalues of Ai repeated according to their multiplicities, andthe vectors |vi,j i and hui,j |, for 1 ≤ j ≤ n, are related to the eigenvectors of Ai . Now, we
can write:
 

`
n
Y
X
hu| Ak11 Ak22 · · · Ak` ` |vi = hu|  
λki,ji |vi,j i hui,j | |vi
i=1

=

X

j=1

1
λk1,j
λk2 · · · λk`,j` ` hu|v1,j1 i hu1,j1 |v2,j2 i hu2,j2 | · · · |v`,j` i hu`,j` |vi
1 2,j2

j1 ,...,j` ∈[1,n]Let us thus define Θj1 ,...,j` = hu|v1,j1 i hu1,j1 |v2,j2 i hu2,j2 | · · · |v`,j` i hu`,j` |vi. The above sum
can be split in two: the first summand containing terms where only dominant eigenvalues areto the power of free variables, and the second containing terms with at least one subdominanteigenvalue to the power of a free variable (these two terms are labelled S0 and S1 below).
This is a useful decomposition since any term which contains a subdominant eigenvalue
taken to the power of a free variable will tend towards zero as the values of all free variables(simultaneously) increase. Thus we can write hu| Ak11 Ak22 · · · Ak` ` |vi = S0 + S1 , where
S0 =

X

1
λk1,j
λk2 · · · λk`,j` ` Θj1 ,...,j` ,1 2,j2

j1 ,...,j` ∈[1,n]∀t∈JF : |λt,jt |=1

S1 =

X

1
λk1,j
λk2 · · · λk`,j` ` Θj1 ,...,j` .
1 2,j2

j1 ,...,j` ∈[1,n]∃t∈JF : |λt,jt |<1

By Lemma 5 the dominant eigenvalues are roots of unity, and so S0 assumes only finitely
many different values as kt with t ∈ JF vary, while kt with t ∈ J \ JF are fixed.
Suppose S1 in not an empty sum since otherwise S1 = 0. Then there exists t ∈ JF andjt ∈ [1, n] such that |λt,jt | < 1. Let ρ be the maximum among such values, that is,ρ = max{ |λt,j | : t ∈ JF , j ∈ [1, n] and |λt,j | < 1 }.
Suppose kt ≥ C for t ∈ JF , where C is some constant to be chosen later. Then S1 can be
estimated as follows: since for every choice of j1 , . . . , j` in the summation S1 there is t ∈ JF
with |λt,jt | ≤ ρ < 1 and |λi,j | ≤ 1 for all other λi,j , we have
|S1 | ≤ C1 ρC ,where C1 =X|Θj1 ,...,j` |.

j1 ,...,j` ∈[1,n]∃t∈JF : |λt,jt |<1

Notice that for any rational  > 0, we can compute C ∈ N such that |S1 | ≤ C1 ρC < . Now,
S0 gives a finite number of limit values for hu| Ak11 Ak22 · · · Ak` ` |vi. If λ is not equal to anyof them, then choose  > 0 to be less than half the minimal distance between λ and thoselimit values. Using this , we compute C as above. By definition of C, if all kt ≥ C fort ∈ JF , then the distance between hu| Ak11 Ak22 · · · Ak` ` |vi and one of the limit values of S0
is less than . Thus hu| Ak11 Ak22 · · · Ak` ` |vi cannot be equal to λ when all kt ≥ C for t ∈ JF .
Hence if λ = hu| Ak11 Ak22 · · · A`k` |vi, then there is t ∈ JF such that kt < C.
The general case. We now show how to extend the proof to the case when some matrices
are non-diagonalizable.
Pj−1
Let ai,j = s=1 `i,s be the sum of the sizes of the first j − 1 Jordan blocks of matrix
Ai , so that ai,1 = 0, ai,2 = `i,1 , ai,3 = `i,1 + `i,2 etc. Then we see that by using Eqn (1),

CONCUR 2020

20:12

Decidability of cutpoint isolation for PFA on letter-bounded inputs

Aki i = Si−1 (J`i,1 (λi,1 )ki ⊕ · · · ⊕ J`i,ni (λi,ni )ki )Si has the form



 
X
X
X
k
i

Si−1 
λki,ji −m|eai,j +p i heai,j +m+p | Sim1≤j≤ni 0≤m≤`i,j −11≤p≤`i,j −m




X
X
X
k
i

=
λki,ji −m
Si−1 |eai,j +p i heai,j +m+p | Si m1≤j≤ni 0≤m≤`i,j −11≤p≤`i,j −m




X
X
X
k
i

=
λki,ji −m|vi,ai,j +p i hui,ai,j +m+p | ,m1≤j≤ni 0≤m≤`i,j −11≤p≤`i,j −mPnPnwhere Si = q=1 |eq i hui,q | and Si−1 = q=1 |vi,q i heq |, with eq the q th basis vector. Here
we used the property that hei |ej i = 0 for any i 6= j. We may now compute that:=hu| Ak11 Ak22 · · · Ak` ` |vi

`
Y
X
X

hu|
1≤j≤ni 0≤m≤`i,j −1

i=1

=

=

λki,ji −m


 
ki 
m


X

|vi,ai,j +p i hui,ai,j +m+p | |vi1≤p≤`i,j −m


 
X
X
k
i
k
−m

hu|
λi,ji
Ψi,j,m  |vim
i=1 1≤j≤ni 0≤m≤`i,j −1


 
X
Y
kt 
1 ,...,m`t
λkt,jt −m
hu| Ψmj1 ,...,j` |vi ,
t
mt
`
Y



j1 ,...,j` | jq ∈[1,nq ]m1 ,...,m` | mq ∈[0,`q,jq −1]

where Ψi,j,m =

P

1≤t≤`

|vi,ai,j +p i hui,ai,j +m+p | and1≤p≤`i,j −m
1 ,...,m`Ψm= Ψ1,j1 ,m1 Ψ2,j2 ,m2 · · · Ψ`,j` ,m` .
j1 ,...,j`We may split the above summation, as before, into two parts corresponding to products
containing only dominant eigenvalues to powers of free variables and those containing atleast one subdominant eigenvalue to the power of a free variables. By Lemma 5, Jordan
blocks corresponding to dominant eigenvalues have size 1 × 1, that is, if |λt,jt | = 1 for t ∈ JF ,then `t,jt = 1 and hence mt = 0. So, we can writehu| Ak11 Ak22 · · · Ak` ` |vi = S0 + S1 ,
where
!
X

Y

j1 ,...,j` | jq ∈[1,nq ]m1 ,...,m` | mq ∈[0,`q,jq −1]∀t∈JF : |λt,jt |=1

t∈JF

X

Y

j1 ,...,j` | jq ∈[1,nq ]m1 ,...,m` | mq ∈[0,`q,jq −1]∃t∈JF : |λt,jt |<1

t∈JF

S0 =

S1 =

1 ,...,m`Θm=j1 ,...,j`Y
t∈J\JFtλkt,jt −m
t



kt
mt

λkt,jt t

1 ,...,m`Θmj1 ,...,j` ,tλkt,jt −m
t

!



kt
mt

!
1 ,...,m`Θmj1 ,...,j`

1 ,...,m`hu| Ψmj1 ,...,j` |vi .

and

(5)

P. C. Bell and P. Semukhin

20:13

1 ,...,m`Note that kt ’s in the formula for Θm
are fixed since t ∈/ JF and so At is not a freej1 ,...,j`
1 ,...,m`matrix. In other words, Θmdoes
notdependonfreevariables
ki for t ∈ JF . This also
j1 ,...,j`
implies that S0 assumes only finitely many different values as kt with t ∈ JF vary since byLemma 5 the dominant eigenvalues are roots of unity.
Again using the fact that Jordan blocks corresponding to the dominant eigenvalues havesize 1×1, we can rewrite the product inside the formula for S1 from Eqn (5) as follows
 
 
Y
Y
Y
kt −mt kt
kt
kt −mt kt=.
λt,jt
λt,jt ·
λt,jt
mt
mt

t∈JF

t∈JF
|λt,jt |=1t∈JF|λt,jt |<1

Suppose S1 in not an empty sum since otherwise S1 = 0. Then there exists t ∈ JF andjt ∈ [1, nt ] such that |λt,jt | < 1. Let ρ be the maximum among such values, that is,ρ = max{ |λt,j | : t ∈ JF , j ∈ [1, nt ] and |λt,j | < 1 }.
Notice that every summand in S1 has at least one |λt,jt | ≤ ρ < 1 with t ∈ JF , and |λi,j | ≤ 1
kt
for all other λi,j . Also, m≤ ktmt ≤ ktn since mt ≤ n. So every summand in S1 can betestimated by the expression
YC1 ·ρkt ktn ,where C1 is a computable constant.
t∈JF|λt,jt |<1

We have ρk k n → 0 when k → ∞, and for any rational δ > 0 we can compute C such thatρ k < δ for k ≥ C. If in addition we assume that 0 < δ < 1 and that kt ≥ C for all t ∈ JF ,then |S1 | ≤ C1 n2` δ.
Now, S0 gives a finite number of limit values for hu| Ak11 Ak22 · · · Ak` ` |vi. If λ is not equal
to any of them, then choose a rational 0 < δ < 1 such that  = C1 n2` δ is less than half theminimal distance between λ and those limit values. Using this δ, we compute C as before.
By definition of C, if all kt ≥ C for t ∈ JF , then the distance between hu| Ak11 Ak22 · · · Ak` ` |vi
and one of the limit values of S0 is less than . Thus hu| Ak11 Ak22 · · · Ak` ` |vi cannot be equalto λ when all kt ≥ C for t ∈ JF . Hence if λ = hu| Ak11 Ak22 · · · Ak` ` |vi, then there is t ∈ JF
such that kt < C.
k n

5

Other decidability results and NP-hardness

In this section we utilise Theorem 1 to obtain some related decidability results. The firstof these combines Theorem 1 with a seminal result of Rabin and allows us to use ourdecidability result for cutpoint isolation to solve the emptiness problem for PFA on letterbounded context-free languages when the cutpoint is isolated. We again highlight here thatthe emptiness problem is undecidable in general on letter-bounded languages, even when all
matrices commute and the PFA is polynomially ambiguous [2].
I Corollary 9. The emptiness problem is decidable for probabilistic finite automata on
letter-bounded context-free languages when the cutpoint is isolated.
Proof. A seminal result of Rabin [23] showed that given a n-state PFA P acting on analphabet Σ and isolated cutpoint λ ∈ [0, 1] such that λ is isolated by  > 0 (i.e. |P(w)−λ| > 
for all w ∈ Σ∗ ), then there exists a DFA D such that L<λ (P) = L(D), where L(D) denotes
the language accepted by the DFA D. Moreover, Rabin showed that the number of states ofn−1
D is no more than 1 + |F |where F is the set of final states of P.

CONCUR 2020

20:14

Decidability of cutpoint isolation for PFA on letter-bounded inputs

We note that the proof of Theorem 1 not only determines if a cutpoint is isolated but
also determines an ‘isolation bound’  > 0 if it is isolated. In this case we can use Rabin’s
result to construct an equivalent DFA D< recognising L<λ (P). By inverting final and nonfinal states of D< , we can construct D≥ which recognises L≥λ (P). Finally we note that if λis isolated then L<λ (P) = L≤λ (P) and thus D< and D≥ recognise the same languages asL≤λ (P) and L>λ (P), respectively. Hence the emptiness problem is decidable.
J
We now show that the value-1 problem for PFA on letter-bounded CFL inputs is decidable.
This problem is undecidable for standard PFA but decidable for #-cyclic automata [13].
I Corollary 10. The value-1 is decidable for probabilistic finite automata on letter-bounded
context-free languages.
Proof. This is trivial since the value-1 problem is equivalent to the isolation of the cutpoint 1
for a PFA [13].
J
Finally we note that Theorem 1 trivially allows us to determine if a given cutpoint isisolated for a PFA which is allowed a fixed maximum number of alternations between input
letters (in any order), where each letter may be taken to an arbitrarily high power.
I Corollary 11. Given a probabilistic finite automaton P on alphabet Σ = {a1 , . . . , a` },cutpoint λ ∈ [0, 1] and maximum number k > 0 of alternations between input letters, thendetermining if the cutpoint is isolated is decidable.
Proof. We may apply Algorithm 1 on P and λ with each language from the following (finite)
set of letter-bounded languages Λ = {w1∗ w2∗ . . . wk∗ |wi ∈ Σ}.
This defines the set of inputs where we alternate between the input letters a maximumof k times (analogous to how counter automata models are often studied with a maximum
number of alternations between increasing and decreasing the counters). If any L ∈ Λ on
Algorithm 1 returns that the cutpoint is not isolated then λ is not isolated for P with amaximum number of alternations k, otherwise the cutpoint is isolated.
J
In the remainder of this section, we give a lower bound on the complexity of the cutpoint
isolation problem for 3-state PFA on letter-bounded inputs (noting that the encoded PFA
are polynomially rather than exponentially ambiguous).
I Theorem 12. Cutpoint isolation is NP-hard for 3-state PFA on letter-bounded inputs.
Proof. We use a reduction from the subset sum problem, defined thus: given a set of positive
integers S = {x1 , x2 , . . . , xk } ⊆ N and a natural number T ∈ N, does there exist a subsetP
S 0 ⊆ S such that `∈S 0 ` = T ? This problem is well known to be NP-complete [12]. We
define the set of matrices M = {Ai , Bi |1 ≤ i ≤ k} ⊆ Q3×3 in the following way:




1 xi
0
1 0
xi
1 
1 
Ai =
0 1
xi  , Bi =0 1
xi 
xi + 1xi + 10 0 xi + 1
0 0 xi + 1
Note that Ai and Bi are thus row stochastic. Let u = (1, 0, 0)> be the initial probability
distribution, v = (0, 1, 0)> be the final state vector and let P = (hu| , {Ai , Bi }, |vi) be our
Pk
PFA. We define the cutpoint λ = Ty , where y =j=1 (xj + 1). Define letter-boundedlanguage L = (a1 |b1 )(a2 |b2 ) · · · (ak |bk ) ⊆ a∗1 b∗1 a∗2 b∗2 · · · a∗k b∗k (thus L is letter monotonic) anddefine a morphism ϕ : {ai , bi |1 ≤ i ≤ k}∗ → {Ai , Bi |1 ≤ i ≤ k}∗ in the natural way (e.g. themorphism induced by ϕ(ai ) = Ai and ϕ(bi ) = Bi ). Now, for a word w = w1 w2 · · · wk ∈ L,

P. C. Bell and P. Semukhin

20:15

note that wj ∈ {aj , bj } for 1 ≤ j ≤ k. Define that v(ai ) = xi and v(bi ) = 0 and inductively
extend to v : Σ∗ → N by defining v(w1 w2 · · · wk ) = v(w1 ) + v(w2 · · · wk ) with v(ε) = 0. In
this case, we see that (due to the structure of Ai and Bi ):hu| ϕ(w1 w2 · · · wk ) |vi = Qkv(w)j=1 (xj + 1)

Note of course that the factor Qk

1is the same for any w ∈ L.
(xj +1)j=1

Assume that there exists a solution to the subset sum problem, i.e., there exists S 0 ⊆ S
Psuch that `∈S 0 ` = T . Then consider word w = w1 w2 · · · wk such that wj = aj if xj ∈ S 0
Pk
and wj = bj otherwise. In this case, i∈S 0 xi = v(w) and thus hu| ϕ(w1 w2 · · · wk ) |vi =T
y = λ. If no solution exists, then for any word w = w1 w2 · · · wk , |v(w) − T | ≥ 1, and so|hu| ϕ(w1 w2 · · · wk ) |vi − λ| > Qk 1
and thus λ cannot be arbitrarily approximated.
j=1(xj +1)

Clearly the representation size of the PFA P and λ are polynomial in the representation
size of the subset sum problem instance and therefore we are done.
J

6

Conclusion

In this work we showed that the cutpoint isolation problem is decidable for PFA when the
input words are constrained to come from a letter-bounded context-free language, even for
exponentially ambiguous PFA. This is in contrast to the situation for the (strict) emptinessproblem and the injectivity problem, which are undecidable even over more restricted PFA
for which all matrices commute, the PFA is polynomially ambiguous and the input words
are over a simple letter-bounded language a∗1 · · · a∗` . We show that if the cutpoint is isolated
for words over the input language, then the emptiness problem becomes decidable. We also
show that the value-1 problem is decidable for these restricted input words.
It would be interesting to determine the complexity of the cutpoint isolation problem
more precisely. We show an NP-hard lower bound in Theorem 12. The algorithm we provide
may belong to NP, however there are some issues with showing this upper bound, namelythat the number of limits of a stochastic matrix may be exponential in its dimension and thevalue of constant C from Proposition 7 may be exponential in terms of the bit size of thematrices, making the verification stage of an NP algorithm difficult to achieve. Extending
the results to more general bounded languages would also be an interesting future work.
Acknowledgements. We thank the referees for their careful reading of this manuscriptand helpful comments.
References
1
2

3
4
5

S. Basu, R. Pollack, and M.-F. Roy. Algorithms in real algebraic geometry, volume 10 ofAlgorithms and Computation in Mathematics. Springer-Verlag, Berlin, second edition, 2006.
P. C. Bell. Polynomially ambiguous probabilistic automata on restricted languages. In
International Colloquium on Automata, Languages, and Programming (ICALP’19), number
105, pages 1–14, 2019.
P. C. Bell, S. Chen, and L. M. Jackson. Freeness properties of weighted and probabilistic
automata over bounded languages. Information and Computation, 269, 2019.
P. C. Bell, V. Halava, and M. Hirvensalo. Decision problems for probabilistic finite automata
on bounded languages. Fundamenta Informaticae, 123(1):1–14, 2012.
A. Bertoni, G. Mauri, and M. Torelli. Some recursively unsolvable problems relating to isolated
cutpoints in probabilistic automata. In Automata, Languages and Programming, volume 52,
pages 87–94, 1977.

CONCUR 2020

20:16

Decidability of cutpoint isolation for PFA on letter-bounded inputs

6
7
8
9

10
11
12
13

14
15
16
17
18

19
20
21
22
23
24
25
26

V. Blondel and V. Canterini. Undecidable problems for probabilistic automata of fixed
dimension. Theory of Computing Systems, 36:231–245, 2003.
J. Cai. Computing Jordan normal forms exactly for commuting matrices in polynomial time.
Int. J. Found. Comput. Sci., 5(3/4):293–302, 1994.
H. Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts
in Mathematics. Springer-Verlag, Berlin, 1993.
L. Daviaud, M. Jurdzinski, R. Lazic, F. Mazowiecki, G. A. Pérez, and J. Worrell. When iscontainment decidable for probabilistic automata? In International Colloquium on Automata,
Languages, and Programming (ICALP’18), number 121, pages 1–14, 2018.
N. Fijalkow, C. Riveros, and J. Worrell. Probabilistic automata of bounded ambiguity. In
28th International Conference on Concurrency Theory (CONCUR), pages 19:1–19:14, 2017.
S. Friedland. Matrices: Algebra, Analysis and Applications. World Scientific Publishing
Company Pte Limited, 2015.
M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of
NP-Completeness. W. H. Freeman and Co. New York, NY, USA, 1979.
H. Gimbert and Y. Oualhadj. Probabilistic automata on finite words: decidable and undecidable
problems. In International Colloquium on Automata, Languages and Programming (ICALP’10),
volume 2, pages 527–538, 2010.
S. Ginsburg. The Mathematical Theory of Context Free Languages. McGraw-Hill, 1966.
S. Ginsburg and E. Spanier. Semigroups, Presburger formulas, and languages. Pacific journalof Mathematics, 16(2):285–296, 1966.
O. Goldreich. On promise problems: a survey. In Essays in Memory of Shimon Even, volume3895 of Lecture Notes in Computer Science, pages 254–290. Springer-Verlag, 2006.
V. Halava, T. Harju, M. Hirvensalo, and J. Karhumäki. Skolem’s problem — on the border
between decidability and undecidability. In TUCS Technical Report Number 683, 2005.
M. Hirvensalo. Improved undecidability results on the emptiness problem of probabilistic andquantum cut-point languages. SOFSEM 2007: Theory and Practice of Computer Science,
Lecture Notes in Computer Science, 4362:309–319, 2007.
M. Mignotte. Some useful bounds. In Computer algebra, pages 259–263. Springer, Vienna,
1983.
V. Y. Pan. Optimal and nearly optimal algorithms for approximating polynomial zeros.
Comput. Math. Appl., 31(12):97–138, 1996.
R. J. Parikh. On context-free languages. Journal of the ACM (JACM), 13(4):570–581, 1966.
A. Paz. Introduction to Probabilistic Automata. Academic Press, 1971.
M. O. Rabin. Probabilistic automata. Information and Control, 6:230–245, 1963.
J. C. Rosales and P. A. García-Sánchez. Numerical semigroups, volume 20 of Developments in
Mathematics. Springer, New York, 2009.
P. Turakainen. Generalized automata and stochastic languages. Proceedings of the American
Mathematical Society, 21:303–309, 1969.
A. Weber and H. Seidl. On the degree of ambiguity of finite automata. Theoretical Computer
Science, 88(2):325–349, 1991.