Parikh Images of Regular Languages: Complexity and Applications

arXiv:1002.1464v2 [cs.LO] 12 Feb 2010

Anthony Widjaja To
LFCS, School of Informatics, University of Edinburgh

Abstract

different representations are also equally important. Theseissues are the main subject of this paper, where nondeterministic finite automata (NFA) and context-free grammars(CFG) are adopted as representations of regular languages
and context-free languages (respectively). [As we shall see,our results also hold for other standard representations ofregular and context-free languages.]
There is a trivial polynomial-time translation from agiven semilinear set S (where numbers are given in unary)to an NFA or a CFG whose Parikh image represents S. On
the other hand, the reverse (more important) direction is not
yet fully understood. All known translations from NFA and
CFG to semilinear sets (e.g. see [10, 18, 23, 26] and thereferences therein) yield at least exponentially many linear
sets. It was not clear whether (and perhaps, to what extent)such an exponential blow-up can be avoided.
Some partial answers are available. Chrobak-Martinez
Theorem1 [6, 20] shows that, given an NFA with n statesover a unary alphabet (i.e. with one letter), one could compute in poly-time a union of O(n2 ) many arithmetic progressions {a + tb : t ∈ N} such that a = O(n2 ) andb = O(n). This theorem has been applied to derive optimal algorithms for other problems in automata theory (e.g.
see [14, 20]) and, recently, in the verification of one-countersystems (e.g. see [13]). Note that arithmetic progressions
are simply linear sets with exactly one generator. ChrobakMartinez Theorem is in stark constrast with the known general translations from NFA (e.g. [10, 18, 23, 26, 32] and thereferences therein), which produce a union of exponentiallymany linear sets with unbounded number of generators evenover unary alphabet. On the other hand, it was shown in[24] that a CFG G over unary alphabet {a} could be usedn
to encode the language {a2 }, where n is roughly the sizeof G. Therefore, at least without allowing binary representation in the output, the size of the semilinear sets could be
exponential in the size of G.
Chrobak-Martinez Theorem suggests one obvious generalization: given an NFA with n states over an alphabet ofany fixed size k ≥ 1, one could construct in poly-time aunion of polynomially many linear sets with at most k gen-

We show that the Parikh image of the language of an NFA
with n states over an alphabet of size k can be described asa finite union of linear sets with at most k generators and2
total size 2O(k log n) , i.e., polynomial for all fixed k ≥ 1.
Previously, it was not known whether the number of generators could be made independent of n, and best upperbounds on the total size were exponential in n. Furthermore, we give an algorithm for performing such a transla2
tion in time 2O(k log(kn)) . Our proof exploits a previously
unknown connection to the theory of convex sets, and establishes a normal form theorem for semilinear sets, which isof independent interests. To complement these results, weshow that our upper bounds are tight and that the resultscannot be extended to context-free languages. We give four
applications: (1) a new polynomial fragment of integer programming, (2) precise complexity of membership for Parikh
images of NFAs, (3) an answer to an open question about
polynomial PAC-learnability of semilinear sets, and (4) an
optimal algorithm for LTL model checking over discretetimed reversal-bounded counter systems.

1 Introduction
A semilinear set is any subset of Nk that can be described as a finite union of linear sets over Nk of the formk{v0 + Σmi=1 ai vi : a1 , . . . , am ∈ N} for some offset v0 ∈ N
and generators v1 , . . . , vm ∈ Nk . The well-known Parikh’s
Theorem states that semilinear sets are effectively equivalent with the sets of letter-counts (a.k.a. Parikh images) ofregular languages and those of context-free languages [23].
This theorem is well-known to be a fundamental result in
automata theory with a plethora of applications. These include verification [7, 13, 16, 30], automata and logics overunranked trees with counting [26], equational horn clauses[32], and word-automata theory itself [5, 14, 20], among
many others. Most practically-motivated applications (e.g.
[7, 13, 14, 16, 20, 26, 30, 32]), however, require more thanthe effective equivalence of such representations. The issues of succinctness and complexity of translations among

1 Unfortunately, their proofs contain a subtle error, which were only
recently fixed in [29]1

erators whose offsets and generators contain only numbersof size (in unary) polynomial in n. Such a generalization
would be interesting for two reasons. First, the size of thealphabet is often much smaller than the number of statesin the NFA. Second, Lenstra [19] has given a poly-time algorithm for integer programming over any fixed number ofvariables. As we shall see, this would yield better complexity in applications requiring the use of Parikh’s Theorem.
One immediate hurdle in proving this general versionof Chrobak-Martinez Theorem is that it was not known
whether for every fixed k ≥ 1 there exists a poly-time algorithm, which given a semilinear set in Nk (in unary), outputs an equivalent finite union of linear sets with at most k
generators and total size polynomial in the given semilinear
set. For k = 1, this is simply a corollary of solutions to the
Frobenius problem [25]. For k = 2, this has been proved by
Abe [1]. However, his proof makes use of geometric facts inR2 that are not available in higher dimensions. In general,
it was not known whether the weaker statement requiring
only existence actually hold for all fixed k ≥ 1.

(3) an answer to an open question posed by Abe [1] about
polynomial PAC-learnability of semilinear sets, and (4) an
optimal algorithm for LTL model checking over discretetimed reversal-bounded counter systems,
Finally, since there is a poly-time translation from regular expressions to NFAs (e.g. see [27]), our upper boundresult for NFAs transfer directly to regular expressions. Although NFAs are more succinct than regular expressions[11] and deterministic automata, our lower bound result alsotransfers to regular expressions and deterministic automata.
Furthermore, since CFGs and pushdown automata are polytime equivalent (e.g. see [27]), our result for CFGs directlytransfer to pushdown automata.
Related work It is of course well-known that semilinear
sets also coincide with subsets of Nk expressible in Presburger arithmetic [12] (i.e., first-order logic over (N, +)).
Such an alternative representation has indeed been fruitfully exploited. In fact, using a technique developed by
Esparza [10], Verma et al. [32] has given a linear translation from context-free grammars (equivalently, pushdown
automata) to the NP-complete existential fragment of Presburger arithmetic expressing their Parikh images. Such atranslation has been used to derive optimal algorithms forequational horn clauses [32]. This linear translation to existential Presburger formulas is orthogonal to our result. On
the one hand, our algorithm works only on NFAs and has
exponential time complexity when the alphabet size is not
fixed and therefore does not immediately yield an NP algorithm. On the other hand, existential Presburger formulas
are exponentially more succinct than the classical representation of semilinear sets (as a union of linear sets) and it iseasy to check that the translation in [32] does not produce
output formulas in any known polynomial-time fragmentof existential Presburger arithmetic even when the input isan NFA (or its equivalent CFG) over some fixed alphabet
size. We will simply remark that many scenarios (including [13, 14, 16, 20, 26, 30] and the ones we consider inthis paper) require the use of the classical representation ofsemilinear sets to derive optimal algorithms.
Vector generalizations of the Frobenius problems (e.g.
see [25] and references therein) have also been proposed.
Such generalizations are orthogonal to our results for semilinear sets. For one, they mainly attempt to extend the notions of “conductors” from the original Frobenius problem,
but neither attempt to reduce the number of generators nor
obtain an efficient algorithm for doing so.

Contributions We prove the general version of ChrobakMartinez Theorem: given an NFA with n states over an al2phabet of size k, we can compute in time 2O(k log(kn)) a
finite union of linear sets with at most k generators and total
2
size 2O(k log n) (even when unary representations of numbers are imposed). To this end, we establish a normal form
theorem for semilinear sets: any semilinear set in Nk of sizen (under unary representation of numbers) could be converted into an equivalent union of 2O(k log(kn)) linear sets
{v0 + Σki=1 ai vi : ai ∈ N}, where numbers in v0 (resp.
{vi }ki=1 ) cannot exceed 2O(k log(kn)) (resp. O(n)). Furthermore, we show that this conversion can be performed in
2time 2O(k log(kn)) . In fact, a similar result is shown to holdfor semilinear sets over Z (i.e. where offsets and generators
are in Zk ). The proof of the normal form theorem makes
use of the well-known Caratheodory’s theorem [33] fromconvex geometry. Our normal form theorem for semilinear sets are of independent interests and have applications
beyond the computation of Parikh images of NFAs.
To complement our upper bounds, we show that for every fixed k ≥ 1 there exist infinitely many NFAs {An }over an alphabet of size k such that An has n states and
its Parikh image contains Ω(nk−1 ) linear sets. This implies
that we cannot remove k from the exponent of the running
time of translations from NFA to semilinear sets. Furthermore, we give infinitely many CFG over a unary alphabet
whose Parikh images contain at least 2n linear sets, where
n is roughly the size of the CFG, and thus strenghthening
the initial lower bound from [24].
We give a few applications of our main results: (1) anew polynomial fragment of integer programming, (2) precise complexity of membership for Parikh images of NFAs,

Organization We fix our notations in Section 2. We
prove a normal form theorem for semilinear sets in Section
3, which is applied in Section 4 to prove a general versionof Chrobak-Martinez Theorem. Lower bounds are given in
Section 5, and applications are given in Section 6.
2

we tacitly assume that there is a linear ordering ≤ on Σ,i.e., Σ = {α1 , . . . , αk } with αi ≤ αj iff i ≤ j. In this case,given a word w ∈ Σ∗ , we define the Parikh image P(w)of w to be the tuple (|w|α1 , . . . , |w|αk ) ∈ Nk . In addition,
given a set L ⊆ Σ∗ , we define the Parikh image P(L) of L
to be the set {P(w) : w ∈ L} ⊆ Nk . We shall also write
P(π) for a path π in an NFA to denote P(L(π)).

Acknowledgment The author thanks Shunichi Amano,
Floris Geerts, Stefan Göller, Filip Murlak, Benjamin Rubinstein, and Tony Tan for their helpful comments. The author
is supported by EPSRC grant E005039.

2 Preliminary
General notations Let N denote the set of nonnegative
integers. We assume familiarity with basic notions fromlinear algebra: vector space, basis, linear independence,
rank, etc. In the sequel, we use only the standard real vector space Rk . We use 0 to denote the vector of Rk withall-zero entries. We denote by {ei }ki=1 the standard basis for Rk , where ei denotes the vector with all-zero entries except for the ith. We shall also require one notation from the theory of convex sets [33]. Given a finite set
V = {v1 , . . . , vm } of vectors in Rk , let cone(V ) be the set{Σm
i=1 λi vi : λi ∈ R≥0 }.

Matrix notations Given two n-by-n 0-1 matrices M =[mi,j ]n×n and M ′ = [m′i,j ]n×n , we write M • M ′ to deWnnote the matrix M ′′ = [m′′i,j ]n×n with m′′i,j = k=1 (mi,k ∧m′k,j ). The operator • is often referred to as boolean matrix multiplication, which can easily be evaluated in O(n3 ).
We also write M ∨ M ′ to denote the application of theboolean operation ∨ component-wise, i.e., resulting in amatrix M ′′ = [m′′i,j ]n×n with m′′i,j = mi,j ∨ m′i,j . In thesequel, we shall also write M [i, j] for the (i, j)-component
mi,j of M .
Semilinear sets For every vector v ∈ Zk and every finite
set S = {u1 , . . . , um } of vectors in Zk , we write P (v; S) to
denote the Z-linear set {v + Σm
i=1 ai ui : a1 , . . . , am ∈ N}.
The pair B := hv; Si is said to be a linear basis for
P (v; S). Notice that there exist non-unique linear bases
for a Z-linear set. The vector v is said to be the offset ofB, and the vectors S the generators of B. For v = 0,
we also use coneN (S) to denote P (v; S). A Z-semilinear
set S is simply a finite (possibly empty) union of Z-linear
sets P (v1 ; S1 ), . . . , P (vs ; Ss ). In this case, we say that
B = {hvi ; Si i}si=1 is a semilinear basis for P (B) := S.
Likewise, semilinear bases for S are not unique. A Zsemilinear set S ⊆ Zk is said to be N-semilinear (or simply
semilinear) if it has a semilinear basis with vectors from Nk
only. The notion of N-linear (or simply linear) sets is also
defined similarly.
Since Z-(semi)linear bases B are simply a sequence of
vectors from Zk , we could talk about their size kBk whenrepresented on the tapes of Turing machines. We shall use
both unary and binary representations of numbers, and be
explicit about this when necessary. In the sequel, we shallnot distinguish (semi)linear sets and their bases, when it isclear from the context. Thus, we shall use such a phrase
as “compute a (semi)linear set” to mean that we compute aparticular (semi)linear basis for it.

Partial orders Recall that a partial order  on a set S
is well-founded if there does not exist a strictly decreasing
infinite sequence s1 ≻ s2 ≻ . . . of elements from S. An
element s of S is said to be -minimal, if all s′ ∈ S withs′  s satisfies s = s′ .
In the sequel, we shall reserve  for the component-wisepartial order on Nk , i.e., (a1 , . . . , ak )  (b1 , . . . , bk ) iff
ai ≤ bi for all i ∈ {1, . . . , k}. Dickson’s lemma [8] statesthat  is well-founded.
Automata An alphabet Σ is simply a finite set of letters.
An NFA A is a tuple (Σ, Q, δ, q0 , qF ), where Q is a finite
set of states, q0 ∈ Q is an initial state, qF ∈ Q is the final state, and δ ⊆ Q × Σ × Q is a transition relation. A
path π in A from q ∈ Q to q ′ ∈ Q is simply an alternating sequence p0 β1 p1 . . . βm pm ∈ (QΣ)∗ Q of states andletters such that p0 = q and pm = q ′ . In this case, wewrite L(π) to denote the path labels β1 . . . βm ∈ Σ∗ , andsay that π is a path on β1 . . . βm . For convenience, we shallsometimes omit the path labels from π, and simply refer toit as a path π = p0 . . . pm on word w = β1 . . . βm . In
this case, the length |π| (resp. |w|) of the path π (resp.
word w) is m. Given i, j ∈ {0, . . . , |π|} with i ≤ j, we
also write π[i, j] as the path segment pi pi+1 . . . pj of π.
Given two paths π = p0 β1 . . . pm and π ′ = pm βm+1 . . . pn
(with m ≤ n), we let π ⊙ π ′ denote the concatenated path
p0 β1 . . . pm βm+1 . . . pn . The NFA A is said to accept theword w ∈ Σ∗ if there exists a path π in A from q0 to qF
such that L(π) = w. In this case, π is said to be an accepting path. The language L(A) of A is the set of words
accepted by A.
Given a word w ∈ Σ∗ and α ∈ Σ, we write |w|α todenote the number of occurences of α in w. In the sequel,kArithmetic on 2Z Given two sets S1 , S2 ⊆ Zk , we define an operation ‘+’ on them as follows: S1 + S2 :={v1 + S
v2 : v1 ∈ S1 , v2 ∈ SS2 }. Suppose now thattr
S1 = i=1 P (vi ; Vi ) and S2 = j=1 P (wj ; Wj ). Then,
Sr St
observe that S1 + S2 = i=1 j=1 P (vi + wj ; Vi ∪ Wj ).
For s1 ∈ S1 , we shall also write s1 + S2 to mean {s1 } + S2 .
Thus, we have P (v; S) = v + coneN (S).
3

3 Normal form for semilinear sets

the inclusion is strict in general. It turns out that an equality
can be achieved by first making a “few” duplicates of each
coneN (Si ) and then shifting them appropriately by some“small” integer vectors.
We now prove Theorem 3.1. First invoke Lemma 3.2 on
V and obtain linearly independent d-subsets S1 , . . . , Sr ofkVS,r where d = rank(V ) and r ≤ m , satisfying cone(Vk) =cone(Sj ). Then, it follows that cone(V ) ∩ Z =

Sj=1
r
k
To compute the integer vector
j=1 cone(Sj ) ∩ Z .
“shifts”, we shall need to define the notions of canonicaland minimal vectors.

In this section, we shall prove a normal form theorem for semilinear sets: given a semilinear basis B in
Nk represented in unary, we can compute in time polynomial in kBk and exponential in k another semilinear basis′
B ′ = {hwi ; Si i}m
i=1 in unary such that P (B) = P (B )and |Si | ≤ k for each i ∈ {1, . . . , m}. For simplicity, we shall state only a general theorem for Z-linear setsof the form coneN (V ), where V is a finite subset of Zk ;this can easily be used to derive the desired normal form
theorem for semilinear sets (among others). [Recall that
P (v; V ) = v + coneN (V ).]Characterization via canonical and minimal vectorskTheorem 3.1 Let V := {v1 , . . . , vm } ⊆ Z \ {0} with
m > 0. Let a ∈ N be the maximum absolute value of
numbers appearing in vectors of V . Then, it is possible2
to compute in time 2O(k log(m)+k log(ka)) a sequence of Zlinear bases hw1 ; S1 i, . . . , hws ; Ss i such that
coneN (V ) =s[

Suppose now that v ∈ cone(Sj ) ∩ Zk and Sj{u1 , . . . , ud }. We make several simple observations:(O1) There exists a unique vector [v] ∈ {−ka, . . . , ka}k ∩cone(Sj ) and unique non-negative integers a1 , . . . , adsuch that: 1) v = [v] + Σdi=1 ai ui , and 2) [v] =Σdi=1 bi ui for some (unique) 0 ≤ b1 , . . . , bd < 1. To
see this, observe that by linear independence of Sj
there exist some unique λ1 , . . . , λd ∈ R≥0 such thatv = Σdi=1 λi ui . Simply let ai := ⌊λi ⌋, bi := λi − ai ,and [v] := Σdi=1 bi ui . Uniqueness is immediate fromuniqueness of λ1 , . . . , λd .

P (wi ; Si )i=1

where the maximum absolute value of entries of each wi isO(m(k 2 a)2k+3 ), each Si is a subset of V with |Si | ≤ k,2
and s = O(m2k (k 2 a)2k +3k ). Furthermore, if V ⊆ Nk ,we have {w1 , . . . , ws } ⊆ Nk .

(O2) Given v′ ∈ cone(Sj ) ∩ Zk , we write v ∼ v′ iff[v] = [v′ ]. It is easy to see that ∼ is an equivalence
relation of finite index (there are at most (2ka + 1)kequivalence classes). If [v] = v, the vector v is said tobe a canonical representative of the equivalence class{u ∈ cone(Sj ) ∩ Zk : [u] = v}. In this case, we will
also call v an Sj -canonical vector, or simply canonicalvector when Sj is understood.

Observe that this theorem causes only an exponential blowup in the dimension k. Moreover, each set Si contains at most k generators. To prove this theorem, westart with a slight strengthening of the conical version of
Caratheodory’s theorem from the theory of convex sets [33,
Proposition 1.15]. Proof is given in the appendix.
Lemma 3.2 Let V := {v1 , . . . , vm } ⊆ Zk \ {0} with m >0. Let a ∈ N be the maximum absolute value of numbers
appearing in vectors of V . Then, it is possible to computein time 2O(k log m+log a) , a sequence S1 , . . . , Sr of distinct
linearly independent d-subsets of V , where d ∈ {1, . . . , k}is the rank of V , andcone(V ) =r[=(O3) If v is in coneN (V ) ∩ cone(Sj ), then v + Σdi=1 ci ui ∈coneN (V ) ∩ cone(Sj ) for every c1 , . . . , cd ∈ N.
We shall now use these observations to define a natural
well-founded partial order j on coneN (V ) ∩ cone(Sj );note that coneN (V ) ∩ cone(Sj ) 6= ∅. Given v, w ∈coneN (V ) ∩ cone(Sj ), we write v j w iff, for some
(unique) Sj -canonical vector v0 and some (unique) coefficients a1 , . . . , ad ∈ N and b1 , . . . , bd ∈ N, it is the casethat: 1) v = v0 + Σdi=1 ai ui , 2) w = v0 + Σdi=1 bi ui , and 3)(a1 , . . . , ad )  (b1 , . . . , bd ). The following simple lemma(proof in the appendix) shows that j is a well-founded partial order, and characterizes j -minimal elements.

cone(Si ).

i=1

Let us first explain the idea behind the rest of the proof of
Theorem 3.1. Intuitively, Lemma 3.2 says that cone(V ) ⊆Rk can be subdivided into smaller subcones with exactlyd ∈ {1, . . . , k} generators where d is the rank of V . Thislemma immediately gives an upper bound for coneN (V ) as
the union of the integer points in cone(Si ); in general, thelatter contains much S
more points than coneN (V ). On therother hand, we have i=1 coneN (Si ) ⊆ coneN (V ), where

Lemma 3.3 The relation j is a well-founded partial order on coneN (V ) ∩ cone(Sj ). Furthermore, a vector v ∈coneN (V ) ∩ cone(Sj ) is j -minimal iff none of the vectors(v − u1 ), . . . , (v − ud ) are in coneN (V ) ∩ cone(Sj ).
4straightforward adaptation of the proof of [21, Theorem p.
767], yields an upper bound for B.

Lemma 3.3 and Observation (O3) immediately implies that
coneN (V ) is a union of linear sets P (v; Sj ) taken over all
j = 1, . . . , r and j -minimal vectors v.

Lemma 3.6 Let A be a k × n integer matrix and b a kvector, both with entries in [−t, t] ∩ Z, where t ∈ N. Then,every -minimal solution x ∈ Nn to Ax = b (x  0) is in{0, 1, . . . , n(kt)2k+1 }n .

SSLemma 3.4 coneN (V ) = rj=1 v P (v; Sj ), where v istaken over all j -minimal vectors.
Proof. (⊇) Obvious.
(⊆) If v ∈ coneN (V ), then v ∈ cone(Sj ) ∩ Zk for somej ∈ {1, . . . , r}. By Lemma 3.3, there exists a j -minimal
vector v′ satisfying v′ j v. Observation (O3) implies thatv ∈ P (v′ ; Sj ).
⊓⊔Notice that the maximum absolute value of numbers appearing in our integer programs cannot exceed t := ak (which
could appear on the right hand side of the equation). If
M := (m + k)(kt)2k+1 , it follows that B ≤ akM + ak ≤N := (m + k)(k 2 a)2k+2 + ak. This completes the proof ofexistence for Theorem 3.1 and gives us the desired bounds
for the parameter s and the maximum absolute value of entries of each wi in Theorem 3.1. It remains to show how tomake this algorithmic.

Note also that if V ⊆ Nk , then all j -minimal vectors (1 ≤j ≤ r) are also nonnegative.
A roadmap for rest of the proof is as follows. We shallshow that each j -minimal vectors cannot be too large andcan be efficiently enumerated. This will immediately giveus the desired sequence of linear bases. The proof of thiswill require connections to integer programming, and theuse of dynamic programming.

Computing canonical and minimal vectors
We first show how to compute all the canonical vectors.
Since Gaussian-elimination over rational numbers can be
implemented to run in time polynomial in the total numberof bits in the input matrix [9] and that each Sj is linearly
independent, we could easily compute all Sj -canonical vectors (for all j ∈ {1, . . . , r}) in time 2O(k log(ka)+k log m) bygoing through all candidate vectors v ∈ {−ka, . . . , ka}kand checking whether there exist 0 ≤ b1 , . . . , bd < 1 suchthat Σdi=1 bi ui = v. [Transform into row-reduced echelon form to compute the unique solution, if exists. Since
Sj ∪ {v} ⊆ Zk , the coefficients b1 , . . . , bd will be rational.]
For each fixed j ∈ {1, . . . , r} and each fixed Sj canonical vector v0 , we now show how to compute the setof all j -minimal vectors v such that [v] = v0 by dynamic
2
programming in time 2O(k log m+k log(ka)) . Observe thatsince there are at most r(2ak + 1)k = 2O(k log(kam)) possible v0 , doing this for all canonical vectors would take time2
2O(k log m+k log(ka)) , which is also the total complexity of
the algorithm. To this end, we first fill out in stages a table
T1 which keeps track of all vectors v ∈ {0, 1, . . . , N }k ∩coneN (V ). At stage h = 1, 2, . . . , m, we collect all vectors
v that can be written as Σhi=1 ci vi , where 0 ≤ ci ≤ M . Since
the size of the table is at most N k (k log N ) — k log N
bits are used to identify each element in the table withan associated k-tuple — this could be carried out in time2
O(m(N k (k log N ))2 ) = 2O(k log m+k log(ka)) . We thenfill out in stages another table T2 , which keeps track of allvectors v ∈ {0, 1, . . . , N }k ∩P (v0 ; Sj ). This could be donein d stages, similar to the computation of T1 , and could
be implemented to run in time O(k(N k (k log N ))2 ) =2
2O(k log m+k log(ka)) . We then simply compute a new table
T3 = T1 ∩ T2 , from which we eliminate vectors that are notj -minimal by using the characterization of j -minimal

Bounds via integer programming
For each Sj = {u1 , . . . , ud }, we shall now show thatall j -minimal vectors v cannot be too large. To thisend, for each canonical vector v0 ∈ cone(Sj ) ∩ Zk , consider the integer linear program Ax = vT0 (x  0),
where A is the k × (m + d) matrix consisting of columns
v1 , v2 , . . . , vm , −u1 , −u2 , . . . , −ud (in this order) and x
is the column (m + d)-vector consisting of the variables
x1 , . . . , xm , y1 , . . . , yd (in this order). The following simple lemma (whose proof is in the appendix) shows that-minimal solutions to such integer programs — as weshall see, they cannot be too large as well — provide upper bounds for how large j -minimal vectors can be.
Lemma 3.5 For every j -minimal vector v ∈ coneN (V ) ∩cone(Sj ), let v0 := [v] and b = (b1 , . . . , bd ) ∈ Nd be theunique coefficients such that v = v0 + Σki=1 bi ui . Suppose
also that c = (c1 , . . . , cm ) is a -minimal solution to theinteger program Σm
i=1 xi vi = v (x  0). Then, the vector
w := (c, b) ∈ Nm+d is a -minimal solution to the integer
program Ax = v0 (x  0).
Consider the set U of all vectors v0 + Σdi=1 ai ui ,where v0 ranges over all canonical vectors and a1 , . . . , adranges over all d-tuples of nonnegative integers such that
(c1 , . . . , cm , a1 , . . . , ad ) is a -minimal solution to the integer program Ax = v0 , for some c1 , . . . , cm ∈ N. We shallsee now that the maximum absolute value B of numbers appearing in U exist, which immediately gives an upper boundfor the maximum absolute value of entries of j -minimal
vectors. The following general lemma, whose proof is a5order, e.g., i0 < i1 < . . . < is = r. Note that s < n. By astandard result in graph theory, each subpath σ[ij , ij+1 ] ofσ can be decomposed into a simple path πj from pij to pij+1of length at most n−1 and finitely many simple cycles (possibly with duplicates) C1 , . . . , Ch each of length at most n.
That is, we have P(π[ij , ij+1 ]) = P(πj ) + Σhi=1 P(Ci ).
Such a decomposition result, however, might allow somecycle Ci to avoid (i.e. not meet with) πj as can be witnessed from [29, Figure 2]. On the other hand, Ci must
visit some states of pi0 , . . . , pis as these contain all statesin σ. Thus, we simply define σ ′ to be the accepting path
π0 ⊙ π1 ⊙ . . . ⊙ πs−1 of length at most (n − 1)2 . It follows
that v ∈ Tσ′ .
(⊇) Conversely, let v ∈ Tπ for some accepting path π in
A of length at most (n − 1)2 . Then, if Sπ = {v1 , . . . , vs },then v = P(π)+Σsi=1 ai vi for some a1 , . . . , as ∈ N. Let Ci
be a cycle in A that meets with π and satisfies P(Ci ) = vi .
We can construct an accepting path σ in A with P(σ) = v
as follows: start from π as the “base” path, and for eachi ∈ {1, . . . , s}, attach ai copies of Ci to one pre-selectedcommon state of Ci and π.
⊓⊔

vectors from Lemma 3.3. All in all, this could be imple2
mented to run in time 2O(k log m+k log(ka)) .

4 Parikh Images of NFAs
In this section, we shall apply Theorem 3.1 to obtain themain result for Parikh images of NFAs.
Theorem 4.1 Let A be an NFA with n states over an alphabet Σ of size k. Then, there exists a representation ofP(A) as a union of linear sets P (v1 ; S1 ), . . . , P (vm ; Sm ),where the maximum entry of each vi is O(n3k+5 k 4k+6 ),each Si is a subset of {0, . . . , n}k with |Si | ≤ k, and2
m = O(nk +3k+5 k 4k+6 ). Furthermore, this is computable2
in time 2O(k log(kn)) .
Observe that this theorem causes an exponential blow-up
only in the size of the alphabet. Efficiency could be improved by outputting numbers in binary.
We shall devote the rest of this section to prove this theorem. Let A = (Σ, Q, δ, q0 , qF ) be a given NFA, where|Q| = n and Σ = {α1 , . . . , αk }. Throughout the proof, weshall use the notion of “cycle type”. A cycle type is a Parikh
image v ∈ Nk of any word w ∈ Σ≤n such that there is apath π of A on w from some (not necessarily initial) state p
to itself. The cycle π is said to witness v. Observe that thesum of the components of any cycle type cannot exceed n.

As an immediate corollary, we have:
Proposition 4.3 Let A be an NFA with n states over analphabet Σ of size k. Then, P(A) can be represented asa union of linear sets P (v1 ; S1 ), . . . , P (vm ; Sm ), wherevi ∈ {0, . . . , (n − 1)2 }k and the components of each vectorin Si cannot exceed n.

Characterization of P(L(A))

Remark: A slightly stronger version of this proposition was
claimed in [26], where the maximum component of each vi
cannot exceed n. Their proof turns out to have a subtle errorthat also occurs in the proof of Chrobak-Martinez Theorem[6, 20], which was recently fixed in [29]. In fact, we show in
Proposition 5.3 that our quadratic bound is essentially optimal, i.e., it cannot be lowered to o(n2 ). (End Remark)Observe now that the proof of existence in Theorem 4.1
is essentially immediate from Proposition 4.3 and Theorem 3.1. In fact, if we are only interested in existence,
this yields a better upper bound of O(n3(k+1) k 4k+6 ) (resp.
2
O(nk +3k+3 k 4k+6 )) for the maximum entry of all offsets{vi }mi=1 (resp. m) in the statement of Theorem 4.1.

We shall first give a characterization of the Parikh image ofA in terms of Parikh images of “short” paths together withsome cycle types. Given a path π = p0 β1 p1 . . . βr pr of A
from the (not necessarily initial) state p0 to the state pr , let
Sπ =⊆ {0, . . . , n}k be the set of all the cycle types that are
witnessed by some cycles C = p′0 p′1 . . . p′t p0 in A such thatp′i = pj for some i ∈ {0, . . . , t} and j ∈ {0, . . . , r}. That
is, C and π meet at state p′i = pj . Now define Tπ to be thelinear set P (P(π); Sπ ).
Lemma 4.2 The following identity holds:[
P(L(A)) =Tπ ,πDynamic programming algorithm

where π is taken over all accepting path of A of length at
most (n − 1)2 .

It remains to show that this can be made algorithmic. To thisend, we first show how to compute all the cycle types of A.
More precisely, let Q = {q0 , . . . , qn−1 }, where qn−1 :=qF , and let I = {(b1 , . . . , bk ) ∈ Nk : Σki=1 bi ≤ n}. For
each vector v ∈ Nk , we write Mv = [ai,j ]n×n for the n-byn 0-1 matrix where ai,j = 1 iff there exists a path π fromqi to qj with P(π) = v. We are interested in computing
all matrices Mv for each v ∈ I. Observe that the naive

Proof. (⊆) Assume that v ∈ P(L(A)) and σ =p0 β1 p1 . . . βr pr be an accepting path in A such that P(σ) =v. We shall construct another accepting path σ ′ in A of
length at most (n − 1)2 . For each state q occuring in σ, letl(q) be the last (i.e. maximum) index i ∈ {0, . . . , r} suchthat pi = q. Let us write down all such l(q) in an increasing6

algorithm, which runs through all paths of A from qi to qj
with P(π) = v, has time complexity that is exponential inn. We will give an algorithm for computing these in time
2O(k log n) using dynamic programming. To this end, let us
derive a recursive formula for computing Mv based on Mv′
with v′  v. As base cases, we first observe that M0 is
the n-by-n identity matrix. Furthermore, each matrix Mei
could be constructed easily from the transition relation δ.

This recurrence relation can be derived by observing thatevery path π of length i from q0 to qj can be decomposed
into the path π[0, i − 1] ending at some state qh and the path
π[i−1, i] = qh αl qj . The cycle types Γj can be “used” since
qj is visited. The proof is in the appendix.
To finish the proof of Theorem 4.1, it suffices to give2
an algorithm with running time 2O(k log(kn)) for computing a desired semilinear basis Pi,j for each set Ti,j . The
algorithm runs in (n − 1)2 + 1 stages, where at stage j =0, . . . , (n − 1)2 the set Pi,j is computed. Obviously, we first
set P0,0 = {0} and P0,j = ∅ for each j ∈ {1, . . . , n − 1}.
hInductively, suppose that Pi,h = {hvhs ; Ssh i}ms=1 has been
computed for each h ∈ {0, . . . , n−1}. We will show how tocompute Pi+1,j for any given j ∈ {0, . . . , n − 1}. For eachh ∈ {0, . . . , n − 1}, let Jh denote the set of numbers l ∈{1, . . .S
, k} such that (qh , α, qj )S∈ δ. Therefore, we have
Sl m
h
h
h
Pi,h + l∈Jh P (el , Γj ) = s=1l∈Jh P (vs +el , Ss ∪Γj ).
We use the algorithm from Theorem 3.1 to compute another semilinear basis for each P (vhs + el , Ssh ∪ Γj ) andthen compute unions in the obvious way to obtain Pi+1,j(note: duplicate is removed). The output of this algorithm
S(n−1)2
is P = i=1 Pi,n−1 . The correctness of the algorithm isimmediate from Lemma 4.6.
We now analyze the time complexity of this algorithm.
By induction, it is easy to see that at every stage of thealgorithm Ssh ∪ Γj ⊆ {0, . . . , n}k holds for each h ∈{0, . . . , n − 1} and s ∈ {1, . . . , mh }. Therefore, the maximum component over all offsets in the semilinear basis
Pi+1,j is at most a+ O(n3(k+1) k 4k+6 ), where a is the maximum entry in each vhs + el over all h ∈ {0, . . . , n − 1},l ∈ Jh , and s ∈ {1, . . . , mh }. Note that the summand O(n3(k+1) k 4k+6 ) is due to an application of Theorem 3.1. By induction, at stage i the maximum compon−1
nent over all offsets in {Pi,j }j=0
is i × O(n3(k+1) k 4k+6 ).
This means that the maximum entry of each offset in P
is O(n3k+5 k 4k+6 ), and the number of linear bases in P is2
O(nk +3k+5 k 4k+6 ) (since duplicates are always removed).
It is also easy to see that at each stage i, the algorithm
2
runs in time 2O(k log(nk)) , primarily spent in the algorithm
from Theorem 3.1. All in all, our algorithm runs in time2
2O(k log(nk)) , which is also the complexity of the entire
procedure.

Lemma 4.4 Let v = (r1 , r2 , . . . , ri−1 , ri +1, ri+1 , . . . , rk )with each ri ∈ N. Then, the following identity holds:
Mv =_Mu • Mei • Mw

u,w

where u ranges over all vectors  v whose ith entry is 0,
and w is the vector v − ei − u.
The proof of this lemma can be found in the appendix. Intuitively, this recurrence relation can be derived by observing
that a path π with P(π) = v can be uniquely decomposed
into three consecutive path segments π1 , π2 , and π3 with
P(π1 ) = u, P(π2 ) = ei , and P(π3 ) = w, for some prescribed u and w. The following lemma, whose proof is also
in the appendix, is a simple application of Lemma 4.4 anddynamic programming.
Lemma 4.5 We can compute {Mv }v∈I in time 2O(k log n) .
For each i ∈ {0, . . . , n − 1}, let Γi be the set of all cycle
types v witnessed by some cycle π = p0 p1 . . . p0 in A with
pj = qi . Since {Mv }v∈I have been computed, all sets Γicould be computed within O(nk+1 ) extra time.
We now show how to compute P(L(A)) in timeO(k2 log(kn))
2. To this end, we shall use another application of dynamic programming based on Lemma 4.2, Then−1
orem 3.1, and the sets {Γi }i=0
, which we already com2
puted. For each
0
≤
i
≤
(n
−
1)
and each 0 ≤ j < n,S
let Ti,j := π Tπ where π is taken over all paths in A of
length i from q0 to qj . By Lemma 4.2, it is the case thatS(n−1)2
P(L(A)) = i=0 Ti,n−1 ; recall that qn−1 = qF by definition. We shall now derive a recurrence relation for Ti,j .

5 Lower bounds
Lemma 4.6 It is the case that T0,0 = {0} and T0,j = ∅for each j ∈ {1, . . . , n − 1}. Whenever i > 0 and j ∈{0, . . . , n − 1}, we haveTi,j =

n−1
[
h=0



Ti−1,h +[1≤l≤k,(qh ,αl ,qj )∈δIn this section, we shall prove three lower bounds tocomplement the results in the previous section. We startby proving that every semilinear basis for the Parikh imageof a deterministic finite automaton (DFA) can be large inthe size of the alphabet.

P (el , Γj ) .

Proposition 5.1 For each k ∈ Z>0 and each integern > 1, there exists a DFA An,k over the alphabet Σk :=7

{a1 , . . . , ak } with n+1 states whose Parikh image contains
at least nk−1 /(k − 1)! linear sets.

Proposition 5.3 For each positive integer n > 2, there
exists a DFA An with 2n + 3 states such that if
P(L(An )) can be represented as a union of the linear sets
P (v1 ; S1 ), . . . , P (vr ; Sr ), then one entry in some vi is atleast n(n + 1)/2.

Proof. Let An,k = (Q = {q0 , . . . , qn }, δ, q0 , qn ) with
δ(qi , a) = qi+1 for each a ∈ Σk and 0 ≤ i < n. This
automaton has a finite language L(An,k ) with Parikh image
P(L(An,k )) containing precisely all ordered integer partitions of n into k parts. Since the set P(L(An,k )) is finite,each ordered integer partition (n1 , . . . , nk ) of n must appear in precisely one linear set. Finally, it is easy to check(e.g. see [31, Chapter 13]) that the numberof ordered park−1
titions of n into k parts equals n+k−1≥
n/(k − 1)!.
k−1⊓⊔This proof is given in the appendix. In fact, the constructed
DFA An has an equivalent regular expression of size O(n)as well, therefore yielding the same quadratic lower boundfor regular expressions.

6 Applications
Integer Programming

This proposition implies that, for every fixed k ≥ 1, there
exists infinitely many DFAs {An } over an alphabet of size kwhere An has size O(n) but P(An ) must contain Ω(nk−1 )linear bases. Therefore, this shows that k cannot be removed from the exponent in Theorem 4.1. In addition, observing that the DFAs that we constructed have equivalent
regular expressions of size O(n), Proposition 5.1 also gives
lower bounds for Parikh images of regular expressions.
Next, we show that Theorem 4.1 cannot be extended to
CFGs (equivalently, pushdown automata). More precisely,
we show that the number of linear sets for Parikh images of
CFGs could be exponential in the size of the CFGs.

Integer programming (IP) is the problem of checking
whether a given integer program Ax = b (x  0), where
A is an k-by-m integer matrix and b ∈ Zk , has a solution.
It is well-known that this problem is NP-complete [22]. On
the other hand, for k = 1, there is a pseudopolynomialtime algorithm for this problem (a.k.a. knapsack problem),
which remains NP-complete under binary representation of
input numbers [22]. Furthermore, Papadimitriou [21] hasestablished a pseudopolynomial-time algorithm for solving
IP, for any fixed k ≥ 1. The running time of his algorithm2
is 2O(k log m+k log(ka)) , where a is the maximum absolutevalue of numbers appearing in the input. Using our resultsin the previous sections, we could show that the problem
remains poly-time solvable (for any fixed k ≥ 1) even if thenumbers in b are given in binary (and A in unary).

Proposition 5.2 There exists a small constant c ∈ Z>0such that, for each integer n > 1, there exists a CFG Gn ofsize at most cn over the alphabet Σ := {a} whose Parikh
image contains precisely 2n linear sets.

Theorem 6.1 Given a k-by-m integer matrix A and a vector b ∈ Zk , let a (resp. b) be the maximum absolute value of
numbers appearing in A (resp. b). Then, checking whether
the integer program Ax = b (x  0) has a solution can be2
done in time 2O(k log m+k log(ka)+log log b) .

Proof. We will construct a CFG Gn such that
P(L(Gn )) = {0, 1, . . . , 2n − 1}, each of whose elements will appear in precisely one linear set. Ourconstruction uses the lower bound technique in [24].
n−1
Our CFG Gn contains nonterminals S, {Ai }i=0
, and
n−1
{Bi }i=0 , and consists precisely of the following rules:
S→ A0 . . . An−1

AiAi

→ ε for each 0 ≤ i < n→ Bi for each 0 ≤ i < nBiB0→ Bi−1 Bi−1
→ a

The proof of this theorem is in the appendix. It is essentiallya simple application of Theorem 3.1 and Kannan’s polytime algorithm [17] for IP for a fixed number of variables,
which improves the running time of Lenstra’s original polytime algorithm [19]. Its running time on an integer programwith d variables and input of length L is O(d9d L log L),
which is polynomial even under binary encoding of numbers in input.
Theorem 6.1 is known to be true when k = 1, by solutions to the Frobenius’s problem, and has such an application as the coin problem (e.g. see [25]). We give anothernot so obvious application of Theorem 6.1 in the appendix.

for each 0 < i < nThe initial nonterminal is declared to be S. It is easy toprove by induction that, for each word w ∈ Σ∗ , Bi ⇒∗ w
ii
iff w = a2 . This implies that Ai generates either ε or a2 .
inThus, we see that L(Gn ) = {a : 0 ≤ i < 2 }, whicheasily yields the desired result.
⊓⊔

Membership for Parikh images of NFAs

Finally, we give a lower bound proving the tightness ofquadratic upper bound in Proposition 4.3, even when restricted to DFAs.

The membership problem for Parikh images of NFAs is defined as follows: given an NFA A over Σ = {α1 , . . . , αk }8and a tuple b ∈ Nk given in binary, decide whether b ∈P(L(A)). A similar membership problem could be defined for CFGs (equivalently, pushdown automata). This
problem is known to be NP-complete (e.g. see [10]). Notice, however, that the hardness proof in [10] requires k to
be unbounded. Furthermore, since it is well-known that
NFAs can be efficiently converted to equivalent pushdown
autommata (equivalently, CFGs), it follows that the membership problem for Parikh images of NFAs is in NP. [See[26, 32] for an alternative proof via existential Presburger
arithmetic.] We first give two complementary lower bounds
for these results.

he established a normal form lemma for semilinear sets ofdimension 2 (in unary), which is simply a special case of
Theorem 3.1 for dimension 2. However, his proof makes
use of geometric facts that are specific to R2 . For this reason, he leaves open the learnability question of semilinear
sets in unary over any fixed dimension k > 2 [1, Section
9]. Replacing Abe’s normal form lemma with Theorem 3.1
and following the proof of [1, Theorem 6.1], we can easily
deduce the more general theorem.
Theorem 6.4 Semilinear sets in unary representation overany fixed dimension k ≥ 1 can be polynomially PAClearned with respect to concept complexity.

Proposition 6.2 Membership for Parikh image of NFAs
(resp. CFGs) is NP-hard when k is not fixed (resp. evenwhen k = 1).

We shall not reproduce the proof for this theorem as it essentially requires only replacing Abe’s normal form lemma
with Theorem 3.1 in the proof of [1, Theorem 6.1]. A shortsketch is provided in the appendix.

NP-hardness already holds for DFAs (reduction from thehamiltonian path problem) and for regular expressions (reduction from one-in-three 3SAT). For CFGs over unary alphabet, we use the encoding of large numbers given in
Proposition 5.2 to encode the 0-1 knapsack problem.
This leaves the complexity of the membership problem
for Parikh images of NFAs for any fixed k ≥ 1. Combining
Kannan’s poly-time algorithm for IP over a fixed number ofvariables (as in the previous application) and Theorem 4.1,
it is easy to show that this problem is solvable in time polynomial in |A| and kbk but exponential in k, i.e., polynomial
when k is fixed.

Verifying counter systems
Minsky’s counter machines are well-known to be a Turingpowerful model of computation. In verification literature, many decidable subclasses of counter machines havebeen studied including reversal-bounded counter systems[15, 16, 30], and their extensions with pushdown stacks anddiscrete clocks [7, 30]. Intuitively, r-reversal k-counter systems are simply Minsky’s counter machines with k counters, each of which can change from an incrementing mode
to a decrementing mode (or vice versa) only for a fixed r
number of times. Their connection to our result is due tothe use of Parikh’s Theorem for obtaining decidability (initially used in [16]). Due to space restriction, we shall briefly
mention only one corollary of our result.
In [30], it was shown that model checking Linear Temporal Logic (LTL) over reversal-bounded counter systems
with discrete clocks is solvable in double exponential
time, even when one of the counters is free (not reversalbounded). More precisely, if t is the number of clocks, n thenumber of states in the finite control, c the size (in binary)of the maximum number appearing in clock constraints, andkϕk the size of the input LTL formula ϕ, then model checking LTL on such systems is decidable in time exponential
in n but double exponential in c, k, r, kϕk, and t. This result was derived by carefully analyzing the complexity of
Ibarra’s original result [16] of effective semilinearity of the
Parikh images of languages recognized by reversal-bounded
counter machines and replacing the application of Parikh’s
Theorem in [16] by the linear translation of [32] from CFGs
to existential Presburger formulas expressing their Parikh
images. By replacing the application of the translation of[32] by Theorem 4.1 and not allowing a single free counter,
we can easily obtain the following upper bound.

Theorem 6.3 Given an NFA A with n states over the alphabet Σ = {α1 , . . . , αk } and a tuple b = (b1 , . . . , bk ) ∈Nk written in binary with b := max1≤i≤k {bi }, checking whether b ∈ P(L(A)) can be done in time2
2O(k log(kn)+log log b) .
Polynomial PAC-learnability of semilinear sets
Valiant’s notion of PAC (Probably Approximately Correct)
learning is a standard model in computational learning theory [3, 4]. In this framework, a learning algorithm is required to run in time polynomial in the size of the training
sample, and output a hypothesis for an (unknown) target
concept that is as precise as the “user” desires, given any
sufficiently large training sample (but still polynomial in thereciprocals of approximation/confidence parameters).
The issues of PAC-learnability of semilinear sets havebeen addressed by Abe [1]. In particular, learning semilinear sets of dimension 1 under binary representation of
numbers is shown to be as hard as learning boolean formulas in DNF, which is (still) a major open question in learning theory. On the positive side, he shows that semilinear
sets of dimension 1 and 2 can be poly-time PAC-learned
when the numbers are represented in unary. To this end,
9

Theorem 6.5 Model checking LTL over reversal-bounded
counter systems with discrete clocks is solvable in time polynomial in n and exponential in c, k, r, kϕk, and t.

[14] H. Gruber and M. Holzer. Computational complexity of
NFA minimization for finite and unary languages. In
LATA’08, pages 261–272.

We shall not reproduce the proof (rather see the full versionof the paper [30], which can be requested from the author).
The time complexity given by this theorem is tight for thefollowing reason: 1) LTL model checking over finite systems is already PSPACE-complete [28], 2) emptiness for rreversal k-counter automata is PSPACE-hard [15], 3) emptiness for discrete timed automata is PSPACE-complete evenwhen restricted to three clocks or when c is “small” (see [2]and references therein).

[15] E. M. Gurari and O. H. Ibarra. The Complexity of Decision Problems for Finite-Turn Multicounter Machines. JCSS
22:220–229 (1981)[16] O. Ibarra. Reversal-bounded multicounter machines andtheir decision problems. J. ACM 25 (1978), 116–133.
[17] R. Kannan. Improved algorithms for integer programming
and related lattice problems. In STOC’83, pages 193–206.
[18] D. Kozen. Automata and Computability. Springer, 1997.
[19] H. W. Lenstra. Integer programming with a fixed number ofvariables. Math. Oper. Res., 8(4):538–548 (1983)

References[20] A. Martinez. Efficient computation of regular expressions
from unary NFAs. In DFCS’02, pages 174–187.

[1] N. Abe. Characterizing PAC-Learnability of Semilinear
Sets. Inf. Comput. 116(1): 81-102 (1995)[21] C. H. Papadimitriou. On the complexity of integer programming. J. ACM 28(4): 765–768 (1981)[2] R. Alur and P. Madhusudan. Decision Problems for Timed
Automata: A Survey. In SFM’04, pages 1–24.
[3] D. Angluin. Computational learning theory: survey and selected bibliography. In STOC’92, pages 351–369.

[22] C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity Dover Publications,
1998.

[4] M. Anthony and N. Biggs. Computational learning theory:
an introduction. Cambridge University Press, 1992.

[23] R. Parikh. On Context-Free Languages. J. ACM 13(4):570–
581 (1966)[5] M. Bojanczyk. A new algorithm for testing if a regular language is locally threshold testable. IPL 104(3):91–94 (2007)[24] G. Pighizzini, J. Shallit, and M. Wang. Unary Context-Free
Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds. JCSS 65(2):393–414 (2002)[6] M. Chrobak. Finite automata and unary languages. In TCS
302 (2003) 497–498.

[25] J. L. Ramı́rez Alfonsı́n. The Diophantine Frobenius Problem. Oxford University Press, 2005.

[7] Z. Dang, O. Ibarra, T. Bultan, R. Kemmerer, J. Su. Binary
reachability analysis of discrete pushdown timed automata.
In CAV’00, pages 69–84.

[26] H. Seidl, Th. Schwentick, and A. Muscholl. Counting in
Trees. Texts in Logic and Games 2:575–612, 2007.

[8] L. E. Dickson. Finiteness of the odd perfect and primitive
abundant numbers with r distinct prime factors. Amer. Journal Math., 35:413–422, 1913.

[27] M. Sipser. Introduction to the Theory of Computation. PWS
Publishing Company, 1997.

[9] J. Edmonds. Systems of distinct representatives and linear
algebra. J. Res. Nat. Bur. Standards 71B:241–245 (1967)[28] A. P. Sistla and E. M. Clarke. The Complexity of Propositional Linear Temporal Logics. JACM 32(3):733–749(1985)[10] J. Esparza. Petri nets, Commutative Context-Free Grammars, and Basic Parallel Processes. Fundam. Inform.
31(1):13–25 (1997)[29] A. W. To. Unary finite automata vs. arithmetic progressions.
IPL 109(17): 1010–1014 (2009)[30] A. W. To and L. Libkin. Algorithmic metatheorems for decidable LTL model checking over infinite systems. To appear in FoSSaCS ’10.

[11] W. Gelade and F. Neven. Succinctness of the Complement and Intersection of Regular Expressions. In STACS’08,
pages 325–336.

[31] J. H. van Lint and R. M. Wilson. A Course in Combinatorics.
(second ed.) Cambridge University Press, 2001.

[12] S. Ginsburg and E. H. Spanier. Semigroups, Presburger
Formulas, and Languages. Pacific Journal of Mathematics
16(2):285–296 (1966)[32] K. N. Verma, H. Seidl, T. Schwentick. On the complexity ofequational Horn clauses. In CADE’05, pages 337–352.

[13] S. Göller, R. Mayr and A. W. To. On the Computational Complexity of Verifying One-Counter Processes. In
LICS’09, pages 235-244.

[33] G. M. Ziegler. Lectures on Polytopes. Springer, 2007.

10

we could find another vector v′ ∈ coneN (V ) ∩ cone(Sj )such that v′ j v. Using Observation (O3), it is easy toshow that at least one of the vectors (v − u1 ), . . . , (v − ud )is in coneN (V ) ∩ cone(Sj ).

APPENDIXA Proof of Lemma 3.2

C Proof of Lemma 3.5

The conical version of Caratheodory’s theorem [33,
Proposition 1.15] states that if we take V1 , . . . , Vs to be
the sequence of all subsets of VS with |Vi | ≤ rank(V ) ≤sk, then we have cone(V ) = i=1 cone(Vi ). Let d :=rank(V ) and S1 , . . . , Sr be the set of all distinct linearly
independentd-subsets
Sr of V . It is not difficult to see that
Ss
cone(Si ). In fact, we obviouslycone(V
)
=
i
i=1 S
i=1 S
s
r
have i=1 cone(Vi ) ⊇ i=1 cone(Si ). Conversely, observe that for each linearly independent subset Vi of rankd′ < d, one could add a vector v ∈ V \ Vi to Vi yielding a linearly independent (d′ + 1)-subset Vi ∪ {v} of V ;otherwise, each vector v ∈ V \ Vi is a linear combination of vectors in Vi contradicting that d′ < d. Repeating this process several times, we obtain a linearly independent d-subset of VScontaining Vi . This easily implies thatSrs
i=1 cone(Si=1 cone(Vi ) ⊆ i ). dkObserve now that r ≤ m
d ≤ m ≤ m . So, we firstcompute the rank d of V by Gaussian-elimination in thestandard way. It is known [9] that Gaussian-elimination
over rational numbers can be implemented to run in timepolynomial in the total number of bits in the input matrix. We then obtain S1 , . . . , Sr by going through eachd-subset of V and using Gaussian-elimination to check
whether it has rank d. In total, the running time is2O(d log m+log(kma)) = 2O(k log m+log a) .

That w is a solution is immediate.
Toshow -minimality, consider a vector u=(c′1 , . . . , c′m , b′1 , . . . , b′d ) ∈ Nm+d such that u  w
and AuT = v0 . Define v′ := v0 + Σdi=1 b′i ui and thus′′v′ = Σmi=1 ci vi . This means that v ∈ coneN (V ) ∩ cone(Sj )and, by j -minimality of v,it follows that v′ = v and thusb′i = bi for every 1 ≤ i ≤ d. That c is a -minimal solution
to the integer program Σm
i=1 xi vi = v (v  0) implies thatc′i = ci for every 1 ≤ i ≤ m and, thus, u = w.

D Proof of Lemma 4.4
We only show that if the Mv [j, h] = 1, then so is the(j, h)-component of the matrix in the r.h.s. The converse
can be proved by observing that all the steps below can beeasily reversed.
Let s = 1 + Σki=1 ri . Suppose that π = ql0 β1 ql1 . . . βs qls
is a path from qj to qh with P(π) = v. Thus, we have l0 = j
and ls = h. We now decompose π as follows. Let t be thefirst position where the letter αi occurs in π, i.e., βt = αiand βt′ 6= αi for all t′ < t. Let π1 := ql0 β1 . . . qlt−1 , π2 :=
qlt−1 βt qlt , and π3 := qlt βt+1 . . . qls . Let u := P(π1 ) andw := P(π3 ). Notice that the ith entry of u is 0 and w = v −ei − u. Furthermore, we have Mu [j, lt−1 ] = Mei [lt−1 , lt ] =Mw [lt , h] = 1. It follows that the (j, h)-component of thematrix Mu • Mei • Mw is 1.

B Proof of Lemma 3.3
That j is a partial order is due to:

E Proof of Lemma 4.5• Observations (O1) and (O2): the uniqueness of choiceof canonical vector v0 and coefficients a1 , . . . , ad ∈ N
for each vector v satisfying v = v0 + Σdi=1 ai ui .

This can be done using Lemma 4.4 and dynamic programming. The algorithm has n + 1 stages. At stage
j = 0, . . . , n, we compute all Mv where the components
in v sum up to j. These will be saved in the memory for
subsequent stages of the iteration. As base cases, we would
obtain M0 and Mei , for each 1 ≤ i ≤ k, directly fromthe input. Notice that boolean matrix multiplication can bedone in O(n3 ) and so each stage of the computation can be
performed in O(n2k+4 ). Thus, the entire computation runsin time 2O(k log n) .

• That  is a partial order on Nk .
To see that j is well-founded, assume that there exists a
strictly decreasing sequence v1 j v2 j . . .. Let vi = v0 +
Σdj=1 aij ui for some unique canonical vector v0 = [vi ] andunique coefficients ai = (ai1 , . . . , ajd ) ∈ Nd . In this way,
we generate a strictly decreasing sequence a1 ≻ a2 ≻ . . .
for the well-founded partial order ≻ on Nk , and therefore acontradiction. Thus, j is a well-founded partial order on
coneN (V ) ∩ cone(Sj ).
Given a j -minimal vector v ∈ coneN (V ) ∩ cone(Sj ),it is obvious that none of the vectors (v − u1 ), . . . , (v − ud )cannot be in coneN (V ) ∩ cone(Sj ). Conversely, given a
vector v ∈ coneN (V ) ∩ cone(Sj ) which is not j -minimal,

F Proof of Lemma 4.6
We first define the following notation: for every path π inA, let Γπ denote the union of all Γh over all h ∈ {0, . . . , n−1} such that qh occurs in π.
11
m + 1. For each 1 ≤ i ≤max{|Si | : 1 ≤ i ≤ r} n(n+1)
2a′nn, let Ci be the cycle p0 ap1 a . . . pi ai p′i (a′i p′i )N cp0 . Consider the accepting path π = (q0 bp0 )⊙C1 ⊙C2 ⊙· · ·⊙Cn ⊙(p0 bqF ). We have P(π) ∈ P (vh ; Sh ) for some 1 ≤ h ≤ r.
Observe also that a occurs precisely Σni=1 i = n(n + 1)/2
times in π.

an
p′n

pn

a′2

Claim. Each a′i -component of vh (1 ≤ i ≤ n) is nonzero.

a2
p′2

p2

We now prove this claim. Let Sh = {u1 , . . . , us } andP(π) = vh + Σsi=1 ti ui . For each i ∈ {1, . . . , n}, there
exists a vector uji with a positive a′j -component and tji >n(n + 1)/2; for, otherwise, the a′j -component of P(π) is

a′1
a
p1 a1
a
q0

p′1

c

m < N , a contradiction. In particular,
at most |Sh | n(n+1)
2this implies that all α-component of uji , where α 6= a′ifor all i ∈ {1, . . . , n}, is 0 as each such letter α occurs
at most n(n + 1)/2 times in π. But this means that eachai -component of vh is nonzero; for, otherwise, we could
consider the vector vh + uji which would not correspond toany accepting path in An since at least one letter ai needs
to read by An if a′i is to occur in the path. This proves ourclaim.
Now consider each word w = w0 . . . wl ∈ L(An ) suchthat P(w) = vh . It is easy to see that the number of occurences of a in w must be at least n(n + 1)/2. In fact, forevery 1 ≤ i ≤ n, define ji = min{j : wj = ai }. For
each i, the number of occurences of a in wt . . . wji , wheret = max{ji′ : ji′ < ji , 1 ≤ i′ ≤ n}, is at least i. The lower
bound of n(n + 1)/2 on the number of occurences of a inw immediately follows.

c

p0
b

c

qF
b

Figure 1. A depiction of the DFA An(⊆) Let v ∈ Ti,j . Then, there exists a path π =ql0 β1 . . . βi qli such that v ∈ Tπ , where l0 = 0 and li = j.
Let π ′ be the path segment π[0, i − 1] of π. Thus, wehave Γπ′ ⊆ Γπ . Suppose that Γπ = {u1 , . . . , um } andΓπ′ = {u1 , . . . , um′ } for some m′ ≤ m. It follows thatΓπw − Γπw′ ⊆ Γj . In other words, new cycle type could
only be introduced by visiting qj . Since v ∈ Tπ , we havev = P(π) + Σm
∈ N. Thus, if
s=1 as us for some a1 , . . . , am′αl = βi , it follows that v = (P(π ′ ) + Σmas=1 s us ) + (el +
Σm
a
u
).
This
establishes
thatv∈
Ti,h + P (el , Γj )s=m′ +1 s s
as desired.
(⊇) This inclusion could be proved by observing that all
the steps in the converse case could be easily reversed.

H Proof of Theorem 6.1
To prove this theorem, let vi (1 ≤ i ≤ m) be thei-th column vector of A and write xT = (x1 , . . . , xm ).
Then, we have Ax = Σmi=1 xi vi and thus checking forsolvability of Ax = b is equivalent to checking whetherb ∈ coneN (V ), where V = {v1 , . . . , vm }. By Theorem
2
3.1, we obtain in time 2O(k log m+k log(ka)) some semilinear
sets P (w1 ; S1 ), . . . , P (wr ; Sr ) with coneN (V ) =Ss
P
i=1 (wi ; Si ), where the maximum absolute value of entries of each wi is O(m(k 2 a)2k+3 ), each Si is a subset of
V with |Si | ≤ k, and s = O(mk+1 (k 2 a)2k+3 ). We would
then simply check whether b ∈ P (wi ; Si ) for some i =1, . . . , s. To this end, we employ Kannan’s polynomial-timealgorithm [17] for IP for fixed number of variables, which
improves the running time of Lenstra’s original polynomialtime algorithm [19]. Its running time on an integer programwith d variables and input of length L is O(d9d L log L).
Observe now that each number in Si and wi could be represented using O(k log(mak)) bits. Therefore, if Si =G Proof of Proposition 5.3
The automaton An = (Σn , Qn , δn , q0 , qF ), where Qn ={q0 , qF }∪{p0, . . . , pn }∪{p′1 , . . . , p′n } and Σn = {a, b, c}∪{ai , a′i : 1 ≤ i ≤ n}. We specify the transition function
δn in Figure 1. Notice that An has an equivalent regularexpression Rn of size O(n). For example, when n = 2, we
can define Rn to beb(a(a1 (a′1 )∗ c|aa2 (a′2 )∗ c))∗ b.
We now argue that the a-component of some vi
must be at least n(n + 1)/2. S Let m be the maxir
mum entry over all vectors in i=1 Si . Define N :=12

{u1 , . . . , ud }, the integer program Σdi=1 xi ui = b − wi has
length L = O(k log b + k 3 log(mak)) and uses d ≤ k variables. On this input, Kannan’s algorithm will terminate intime 2O(k log k+log log b+log log(ma)) . In the worst case, wewill need to run Kannan’s algorithm for each i = 1, . . . , sif the answer to the original IP question is negative. In total,2
the algorithm runs in time 2O(k log m+k log(ka)+log log b) .

• f (xi ) := a1 . . . ak where ai := i if xi ∈ Cj , andai := ε otherwise.
• f (x̄i ) := a1 . . . ak where ai := i if x̄i ∈ Cj , andai := ε otherwise.
That is, the function f associates a literal with the indicesof clauses that are satisfied when the value 1 is assigned
to the literal. The corresponding regular expression over
Σ = {1, . . . , k} is

I Another application of Theorem 6.1

Rϕ = (f (x1 )|f (x¯1 )) . . . (f (xn )|f (x¯n )).

Another not immediately obvious application is the following navigation problem. Suppose we have a robot in Zk
that can make finitely many different types of local moves
v1 , . . . , vm ∈ Zk at any given point in Zk . It is reasonable
to assume that local moves are small (i.e. given in unary).
We are interested in the following global behavior: when
initially placed at 0, can it eventually arrive at a given vector b? The vector b can be assumed to be large (i.e. given inbinary) as it pertains to the result of a global behavior. Theorem 6.1 implies that this navigation problem is poly-timesolvable when the dimension k is fixed.

Let 1 ∈ {1}k . We claim that ϕ is a positive instance of
one-in-three 3SAT iff 1 ∈ P(L(Rϕ )). To prove this, suppose that ϕ is a positive instance with a 1-in-3 satisfying
assignment σ : L → {0, 1} (i.e. σ(xi ) = 1 iff σ(x¯i ) = 0).
Consider the word w := X1 . . . Xn ∈ Σ∗ , wheref (xi ) if σ(xi ) = 1,
Xi :=f (x̄i ) if σ(xi ) = 0.
Observe that w ∈ L(Rϕ ). Since σ is a 1-in-3 satisfying
assignment, it follows that P(w) = 1 and, therefore, wehave 1 ∈ P(L(Rϕ )). The converse direction can be provedby reversing the above construction of the word w. Finally,observe that the construction of Rϕ and 1 can be done intime polynomial in the size of ϕ.

J Proof of Proposition 6.2
DFA We now give a poly-time reduction from the hamiltonian path problem to membership problem for Parikh images of DFAs. The hamiltonian path problem asks whether
a given graph G = (V = {v1 , . . . , vn }, E) with a sources := v1 ∈ V and a target t := vn ∈ V has a hamiltonian path from s to t, i.e., a path from s to t in G that
visits each vertices in V exactly once. Given G, s, t, we
define the DFA AG,s,t = (Σ, Q, δ, q0 , qF ) where Q :=V , Σ := {α1 , . . . , αn }, q0 := s, qF := t, and δ :={(vi , αj , vj ) : (vi , vj ) ∈ E}. Then, it is easy to see that
G has a hamiltonian path from s to t iff the Parikh image P(α1 . . . αn ) of the word α1 . . . αn is in P(AG,s,t ) iff(0, 1, 1, . . . , 1) ∈ P(AG,s,t ). This completes the proof of
NP-hardness of the membership problem for Parikh imagesof DFAs with unbounded alphabet size.

CFG For CFGs over unary alphabet, we could easily use
the encoding of large numbers given in Proposition 5.2 tosuccinctly encode the NP-complete 0-1 knapsack problem,i.e., given a1 , . . . , am ∈ N and b ∈ N all represented in binary, decide whether there exists a subset S ⊆ {1, . . . , m}such that Σi∈S ai = b.

K Sketch for proving Theorem 6.4
The reader should first familiarize themselves with thenotions of PAC-learnability. Abe [1, Section 2–4] gives ahighly-readable exposition; but a more gentle introduction
could be found in [3, 4]. In the following, a semilinear set
is said to have at most k generators if it is a union of linear
sets with at most k generators.
To prove Theorem 6.4, the reader should first recall
the notion of polynomially generable natural union class(PGNU) in [1, Definition 6.1–2]. [Definition 6.2 has atypo in item 2(ii): size(M ′′ ) < size(M ) should besize(M ′′ ) < size(M ′ ).] By [1, Lemma 6.1] and [1,Lemma 4.6], it suffices to show that for each fixed k ≥ 1:

Regular expressions One-in-three 3SAT is the following problem: given a boolean formula ϕ in 3-CNF, does
there exist a satisfying assignment for ϕ that additionallymakes no more than one literal true for each clause. We
shall call such an satisfying assignment 1-in-3. This problem is NP-complete (see “M. R. Garey and D. S. Johnson.
Computers and Intractability: A Guide to the Theory of NPcompleteness, W. H. Freeman, 1979.”). We shall reduce thisproblem to the membership problem for Parikh images ofregular expressions. Given ϕ = C1 ∧ . . . ∧ Ck , where Ci
is a multiset over L := {x1 , x¯1 . . . , xn , x¯n } with |Ci | = 3,
we define a function f : L → {1, . . . , k}∗ as follows:(P1) semilinear sets in unary representation with at most k
generators over any fixed dimension k ≥ 1 is a PGNU
(an adaptation of [1, Corollary 6.1]); and13

(P2) semilinear sets in unary with at most k generators overNk is a Poly Blow-up Normal Form (c.f. [1, Definition4.9]) for semilinear sets in unary over Nk (an adaptation of [1, Corollary 6.2]).
The proof of (P1) is almost identical to the proof of [1,Corollary 6.1]:
1. for any given b ∈ Z≥1 , there are at most k(b+1)k(k+1)
semilinear sets over Nk with at most k generators
whose offsets and generators contain only numbers in{0, . . . , b}; and2. (First condition of PGNU) it is easy to see that checking whether a given tuple (a1 , . . . , ak ) ∈ Nk is a member of a given semilinear set with at most k generators over Nk can be poly-time (truth-table) reduced tointeger programming with fixed number of variables,
which is poly-time solvable by Kannan’s algorithm[17] (in this case, numbers could even be represented
in binary).
The next step is to show (P2). However, this is simply acorollary of our Theorem 3.1. This completes the proof of
Theorem 6.4.

14