Parikh Images of Grammars: Complexity and Applications
Eryk Kopczyński
Institute of Informatics, Warsaw University

Abstract—Parikh’s Theorem states that semilinear sets are
effectively equivalent with the Parikh images of regular languages and those of context-free languages. In this paper,
we study the complexity of Parikh’s Theorem over any fixedalphabet size d. We prove various normal form theorems
in the case of NFAs and CFGs. In particular, the normal
form theorems ensure that a union of linear sets with dgenerators suffice to express such Parikh images, which inthe case of NFAs can further be computed in polynomial
time. We then apply apply our results to derive: (1) optimal
complexity for decision problems concerning Parikh images(e.g. membership, universality, equivalence, and disjointness),(2) a new polynomial fragment of integer programming, (3)an answer to an open question about PAC-learnability ofsemilinear sets, and (4) an optimal algorithm for verifying LTL
over discrete-timed reversal-bounded counter systems.
Keywords-Parikh Images, Automata, Grammars, Normal
Form, Algorithms

I. I NTRODUCTION
A semilinear set is any subset of Nd that can be described
as a finite union of linear sets over Nd of the form {v0 +Pmdi=1 αi vi : α1 , . . . , αm ∈ N} for some offset v0 ∈ N anddgenerators v1 , . . . , vm ∈ N . Parikh’s Theorem — one of
the most celebrated theorems in automata theory — statesthat semilinear sets are effectively equivalent with the setsof letter-counts (a.k.a. Parikh images) of regular languages
and those of context-free languages [Par66].
In this paper, we study the complexity of Parikh’s Theorem adopting nondeterministic finite automata (NFA) andcontext-free grammars (CFG) as representations of regular
languages and context-free languages (respectively). Our
motivations originated from the multitude of applications of
Parikh’s Theorem in automata theory (e.g. decision problems
for semilinear sets and Parikh images of regular/context-freelanguages [Esp97], [Huy80], [Huy84], [Huy85], [Huy86]
such as membership, universality and inclusion), the verification of well-known subclasses of Minsky counter machines[DIBKS00], [Esp97], [GMT09], [GI81], [Iba78], [TL10],[Yen96], automata and logics over unranked trees withcounting [BM99], [SSM07], and equational Horn clauses[VSS05], among many others. While there is a simple
polynomial-time translation from a given semilinear set
S (where numbers are given in unary) to an NFA or a
CFG whose Parikh image represents S, the reverse (moreThis extended abstract is a merge of [Kop10] and [To10]

Anthony Widjaja To
School of Informatics, University of Edinburgh

important) direction is not yet fully understood. All known
translations from NFA and CFG to semilinear sets (e.g.
see [Esp97], [Koz97], [Par66], [VSS05] and the references
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.
Contributions
The main contributions of this paper are various “normal
form theorems” for Parikh images of NFAs and Parikh
images of CFGs, along with their applications for obtaining
optimal algorithms for dealing with Parikh images of NFAs
and CFGs, and computational problems in many different
areas of theoretical computer science. For an underlying
alphabet Σ, we show that linear sets with at most |Σ|generators always suffice to compose such Parikh images.
This is a fact that was known only for |Σ| = 1 [Ram05] andfor |Σ| = 2 [Abe95], but was open for larger alphabet size(see [Abe95]).
In the case of NFAs with n states and fixed alphabet size,
we give a polynomial-time algorithm (exponential in |Σ|)for computing such Parikh images,
each of whose linear
Pk
sets is of the form S = {v0 + i=1 αi vi : α1 , . . . , αk ∈ N}with k ≤ |Σ| satisfying the linear independence property: ifv ∈ S, then the witness α1 , . . . , αk ∈ N for this is unique.
This fact is already known in the case of |Σ| = 1 as ChrobakMartinez Theorem1 [Chr03], [Mart02], but was open in thecase of |Σ| > 1. Notice that the linear independence property
allows us to check whether a vector v is a member ofthe linear set by using the standard Gaussian-elimination
algorithm, which can be implemented in polynomial-time.
Our result in fact holds also for linear grammars, which area more expressive formalism than regular languages and towhich NFAs can be translated in polynomial time. We also
consider a somewhat unusual extension of these automata
model with negative inputs, for which we show that our
results for NFA still hold. Such an extension is, in fact,essential for deriving several of our desired applications. On
the other hand, we show that the running time of algorithms
for computing Parikh images of NFAs must have |Σ| as an
exponent. This is shown by establishing an infinite family{An } of NFAs, where An has n states and its Parikh image
contains Ω(n|Σ|−1 ) linear sets.
1 Unfortunately, there was a subtle error in their proofs, which wererecently fixed in [To09]

a formula in a known polynomial fragment of Presburger
arithmetic.

We give several applications of our normal form theorem
for NFAs: (1) precise complexity of membership, inclusion,
universality, and disjointness for Parikh images of regular
languages and linear context-free languages in the case of
fixed alphabet size ranging from P to coNP, (2) a newpolynomial fragment of integer programming, (3) an answer
to an open question posed by Abe [Abe95] about polynomial
PAC-learnability of semilinear sets, and (4) an optimal algorithm for LTL model checking over discrete-timed reversalbounded counter systems. In most of these cases, the bestpreviously known complexity was one exponential higher
than the complexity that we derive.
What about the case of general CFGs? In this case, weshow that their Parikh images could have exponentiallymany linear sets even over unary alphabet, i.e., |Σ| = 1.
Despite this, in the case of d := |Σ| ∈ {1, 2}, we show that
the Parikh image of a CFG G can be expressed as finite
union of linear sets with d generators (whose magnitude
is exponential in kGk), which can be further grouped intopolynomially many “bundles” such that each linear set ineach bundle shares the same generator(s) (we call thesebundles A, B-frames). In the case of d > 2, such a normal
form is shown to be impossible even for d = 3. In spiteof this, we show that for any fixed d > 2 we can divide
Nd into smaller regions, in each of which the number ofA, B-frames is polynomial.
As an application of our normal form theorems for CFGs,
we derive precise complexity for membership, universality,
inclusion, and disjointness for Parikh images of CFGs overfixed alphabet ranging from NP to the second level ΠP
2 of thepolynomial hierarchy (previously, their known complexity
was one exponential higher). These results can, in turn, be
applied for deriving an optimal complexity for reachability
equivalence for communication-free Petri nets in the case of
fixed number of places.

Merging noteThis extended abstract is a merge of [Kop10] and [To10].
Both authors independently discovered the normal form
theorem for Parikh images of NFAs and semiliner setswith different techniques. An extension of this theorem
to incorporate negative inputs and semilinear sets over all
integers was proven in [To10], which was also observed
in [Kop10]. We are grateful to the referee who pointed
out that our results directly extend to linear grammars. In
addition, the author of [Kop10] derived the two normal
form theorems for CFGs. In this extended abstract, wefollow the presentation of [Kop10]. To make our presentation
coherent, we extend the proof of [Kop10] to incorporate
an extension of the first normal form theorem to automata
models with negative inputs. [For another proof of thisfact, see [To10].] In addition, both authors independently
discovered the application of the first normal form theorem
for deciding membership of Parikh images of NFAs with
fixed alphabet size, along with the lower bound for the caseof unfixed alphabet size and CFGs with singleton alphabet.
Applications to the problem of universality, inclusion, anddisjointness as well as extesions to CFGs with fixed alphabet
size were derived in [Kop10]. Other applications (integer
programming, etc.) were given in [To10].
Organization
The paper is organized as follows. In Section II, we begin
with some basic results concerning geometry of multisets.
Section III provides some basic results concerning commutative grammars. In Section IV, we establish our normal form
theorem for linear grammars. In Section V, we provide ournormal form for CFGs of alphabet of size 2, which we show
does not extend to alphabet of size 3. Section VI gives ournormal form for CFGs of any fixed alphabet size. In Section
VII, we give applications of our results.

Related work
It is of course well-known that semilinear sets also coincide with subsets of Nd expressible in Presburger arithmetic[GS66] (i.e., first-order logic over (N, +)). Such an alternative representation has indeed been fruitfully exploited.
In fact, using a technique developed by Esparza [Esp97],
Verma et al. [VSS05] has given a linear translation fromcontext-free grammars (equivalently, pushdown automata) to
the NP-complete existential fragment of Presburger arithmetic expressing their Parikh images. Such a translation has
been used to derive optimal algorithms for equational Hornclauses [VSS05] and can be used to provide an optimal
complexity for membership for Parikh images of NFAs
and CFGs over non-fixed alphabet size. For applications
requiring Parikh’s Theorem over fixed alphabet size, thetranslation cannot be immediately applied for producing
optimal complexity. For example, even when the input is an
NFA over a unary alphabet, the translation does not produce

II. G EOMETRY OF M ULTISETSWe denote the set of non-negative integers by N, allintegers by Z, non-negative rationals by P, all rationals
by Q, and real numbers by R. We use P for non-negative
rationals instead of the more standard Q+ to avoid double
upper indexing, as in (Q+ )X . We use the notation [K..L]
for the set of integers from K to L, and [K; L] for the setof rationals from K to L.
For F ⊆ R, F X is the set of vectors with coordinates
indexed by elements of X and coefficients from F . In
particular, the elements of NX are interpreted as
P multisetsof elements of X. For v ∈ F X , ||v||1 =x∈X |vx |,||v||∞ = maxx∈X |vx |. We say u ≥ v iff ux ≥ vx foreach x.
2

X
By FX
we denote the set of matrices with coefficients in
F and coordinates indexed with elements of X. For a matrix
X
M ∈ FX, M i , the i-th column of the matrix, is a vector
X
X
in F X . For M
P ∈ RX and v ∈ R , M v is a vector givenby (M v)j = i Mji vi , and ||M ||∞ = maxx∈X, y∈X |Myx |.
Thus, for example, [−K..K]X
X is the set of matrices M withinteger coefficients such that ||M ||∞ ≤ K.
We can add or multiply sets of scalars, vectors, or matrices, in the usual way. For example, U + V = {u + v : u ∈U, v ∈ V }, and M NX for M ∈ ZX
X is the set of vectors
which can be obtained as a linear combination of columnsof M with coefficients fromP N.
By B ⊕A we denote { b∈B αb b : ∀b ∈ B αb ∈ A}. A set
of form w + V ⊕N , where w ∈ ZΣ and V is a finite subsetof ZΣ , is called a linear set.

considering our runs as multisets rather than trees: we don’tcare where in the tree each transition (production) has been
used, we just count the total number of occurences. We showthat there is a simple condition which checks whether our
multiset corresponds to some full derivation, or a ,,cyclic”
derivation. (A similar algebraic definition of cycles is usedby the algebraic topologists.)
We will also allow productions in our commutative grammars to produce negative quantities of terminal letters.
While this does not make much sense for non-commutativegrammars, it is very natural for commutative ones. Allowing
negative productions does not increase the complexity ofsome of our proofs; indeed, some constructions can be madesimpler when using them. Disjointness of images of two
commutative regular grammars can be reduced to checking
membership of 0 when negative outputs are allowed. The
counterexample from Section V was also first constructedwith productions with negative outputs (actually, the original
construction even had productions with negative quantitiesof states (non-terminals) on the right side, which in generaldoes not have a natural meaning; in this particular case,negative quantities of both terminals and states were easy to,,normalize”).
A commutative grammar is a tuple G = (Σ, S, s0 , δ),
where Σ is a finite alphabet, S is a finite set of states,s0 ∈ S is an initial state, and δ ⊆ S × ZΣ × NS is a set
aof transitions. We will write transitions (s, a, t) as s → t;
in terms of derivations, each transition consumes the state sand produces each letter from a and each state from t. Foraa transition τ = s → t, source(τ ) = s, target(τ ) = t, andP(τ ) = a.
We will assume that each state is a source of sometransition. Since we want to limit things produced by thegrammar in term of |S|, we will also assume that for eachas → t ∈ δ, ||a||1 ≤ 1 and ||t||1 ≤ 2. (Grammars notsatisfying these conditions can be easily transformed byadding additional states.) A commutative grammar satisfying||t||1 ≤ 1 is called a regular commutative grammar;
regular grammars are equivalent to non-deterministic finite automata, with initial state s0 and transitions withtarget(τ ) = 0 as transitions to the final state—we preferto speak about regular grammars rather than NFAs for thesake of uniformity. Observe also that linear grammars treatedcommutatively are in fact regular commutative grammars.
A commutative grammar satisfying a ≥ 0 (that is, neverproducing negative quantities of terminal letters) is called
positive.
For a D ∈ Nδ , source(D) ∈ NS counts how many eachstate appears as source of a transition: source(D)(s) =Pτ :source(τ )=s D(τ ), and P(D) and target(D) counts how
many eachis produced:
Pletter and each state, respectively,P
P(D) = τ D(τ )P(τ ), target(D) = τ D(τ )target(τ ).
The support of D, supp(D) = {s ∈ S : s ∈ source(D)}.
We say that D is connected from s ∈ S if for eachLemma 1 Let M be a non-degenerate matrix in ZΣΣ , andlet v ∈ ZΣ . Then (det M )v ∈ M ZΣ .
Proof: Immediate from the well known Cramer’s rule.
Definition 2 An A, B-frame is a set of form W + M NΣ ,where W ⊆ [−A..A]Σ , and M ∈ [−B..B]Σ
Σ.
The following picture shows geometrically what an A, Bframe is for |Σ| = 2: a set W sitting inside of a box of size
A (drawn as the letter W ) is copied by shifting it in |Σ| = 2
directions. The vectors by which we are shifting are bounded
by B.

W
W
W W
W
W

B

A

Our normal form theorems will present Parikh imagesof grammars as unions of a small number of A, B-frames.
Although the A parameter is sometimes still large, suchpresentation has better properties than the usual semilinear
set presentation; see Lemma 17 below for an example.
III. C OMMUTATIVE G RAMMARS
Since in this paper we don’t care about the order ofsymbols in strings generated by our grammars, we define ourgrammars commutatively: a state (nonterminal) produces a
multiset of letters and states, not a string.
Derivation trees are defined for commutative grammars
similarly as for the usual ones; we omit this definition.
However, we usually also abstract from derivation trees, by3

t ∈ supp(D) there is a path from s to t in D, i.e., asequence τ1 , . . . , τm such that τi ∈ D, s = source(τ1 ),source(τi+1 ) ∈ target(τi ), t ∈ target(τm ). We say that D
is a cycle from s ∈ S iff it is connected from s and it
satisfies the Euler condition: source(D) = target(D) (interms of derivations, each state is consumed as many times
as it is produced). We say that D is run iff it is connectedfrom s0 and source(D) = target(D) + {s0 } (each state isconsumed as many times as it is produced, except s0 whichis consumed one time more).
For a commutative grammar G, P(G) = {P(D) :D is a run in G}.
This definition of a Parikh image of grammar, based on
our algebraic definitions of runs and cycles, which are in turnbased on connectedness and Euler condition, gives the same
set as the usual one, based on derivation trees. The theorem
below is a corollary of Theorem 3.1 from [Esp97]; a proof
can also be found in [Kop10]. For regular grammars, it isequivalent to the classic theorems of Euler characterizing
graphs with Eulerian paths and cycles.

Since we can use each state at most twice on each branch(once on the main part and once on the side part), this limits
the size of a simple cycle to exponential in size of G.
The construction for skeletons is similar. Indeed, consider
a skeleton run. If a state s appears |S| + 1 times on abranch of the production tree, it means that there exist two
successive appearances of s on this branch such that the partof the tree between them can be cut off without removing
any state from the support of this skeleton (otherwise eachsuch state would have to be different and we would have
|S| + 1 states in total).
In case of regular grammars, we use the same methods,
except that there are no side branches, and thus we obtainbetter bounds.
[Kop10] contains a generalization of the part regarding
regular grammars, which has been obtained purely using
commutative methods (that is, the Euler condition itself).
This generalization allows obtaining Theorem 8 below in a
simpler way for alphabets of size 2.
IV. N ORMAL F ORM FOR COMMUTATIVE REGULAR

Proposition 3 Let G be a commutative grammar. Then:GRAMMARS

D is a run iff there is a derivation tree from s0 where
each transition τ appears D(τ ) times, and all the
branches are closed (i.e., they end with terminals).
• D is a cycle from s iff there is a derivation tree froms where each transition τ appears D(τ ) times, and all
the branches are closed except one with the state s at
its end (we call such derivation tree cyclic).

•

In this section we derive our normal form theorems forsemilinear sets and regular grammars.
Lemma 5 Let V ⊆ [−K..K]Σ be a linearly
Pdependent setof vectors. Then for some α ∈ ZV we have v∈V αv v = 0,
|Σ|/2
where ||α||∞ ≤ K |Σ| |Σ|, and αv > 0 for some v.
Proof: Without loss of generality we can assume thatVisa minimal linearly dependent set. Thus, we getPVv∈V βv v = 0 for some rational coefficients β ∈ Q .
Let u be such that |βu | ≥ |βv | for each v. Let M ∈ ZΣΣ
be a non-degenerate matrix whose |V | − 1 columns are
V − {u} (we obtain a non-degenerate matrix since V wasa minimal linearly dependent set; if |V | < |Σ| + 1, we fillup the remaining columns with independent unit vectors).
From Lemma 1 we get that | det M |u = M w for somew ∈ ZΣ . Let αu = −| det M |, αv = wi where vP= M i , andαv = 0 for remaining vectors. We have thatαv v = 0.
Moreover, we have that for some q ∈ Q we have βv = qαv
for each v (for a minimal linearly dependent set, (βv ) is
unique up to a constant); thus, |αv | < |αu | = | det M | foreach v. From the classical Hadamard’s bound we know that
|Σ|/2
| det M | ≤ |Σ|.

A cycle is called a simple cycle iff it cannot be decomposed as a sum of smaller non-zero cycles, and a run
D is called a skeleton run if it cannot be decomposed
as a sum of a run D1 and a non-zero cycle C, wheres ∈ S, let Cs be thesupp(D1 ) = supp(D). For each state S
set of simple cycles from s, and CS
T =s∈T Cs , for T ⊆ S.
Also, let Ys = P(Cs ), and YT = s∈T Ys (cycle outputs).
Lemma 4 Let G be a commutative grammar overΣ. If D isO(1)a simple cycle or a skeleton run, then P(D) = O 2|S|.
If G is a regular grammar, then ||P(D)||1 ≤ |S| for simple
cycles, and ||P(D)||∞ ≤ O(|S|2 ) for skeleton runs.
Proof: We start with the cycle case. We consider its
cyclic derivation tree from Proposition 3.
If somewhere on the branch leading to s (the main branch)
we had another s, we can easily split our cycle into twocycles (by splitting the derivation tree). A similar thing canbe done if we had some state t in two places on the mainbranch.
A similar operation can be done when we find the samestate twice on the side part of a branch (i.e. the part disjoint
with the main branch).

Theorem 6 Let V ⊆ [−K..K]Σ . Let i(V ) be the set of all|Σ|/2
linearly independent
subsets of V . Let M = K |Σ| |Σ|.
P⊕[0..M ]Then V ⊕N =+ W ⊕N ). In particular,W ∈i(V ) (Va linear subset of ZΣ , where |Σ| is fixed, is a union of apolynomial number of A, B-frames, where both A and B
are polynomial.
4

We
will
prove
that
V ⊕N
⊆
P Proof: ⊕[0..M
]
⊕N
(V
+
W
);
the
other
inclusionisW ∈i(V )P
obvious. Let w = v∈V γv v, where γv ∈ N.
Let P ⊆ V be set of vectors v for which γv ≥ M . If
P ∈ i(V ), we are done—we have already P
expressed w in
the required form. Otherwise, by Lemma 5, v∈P αv v = 0
for some (γv ), |γv | ≤ M , and γu > 0 for some u ∈ P . This
allows us to transfer multiplicites between different cycles: if
00
we take γP/ P,
v = γv − mαPv for v ∈ P , and γv = γv for v ∈we have v γv v = v γv0 v. We perform this transferring
operation for the largest m which does not drop any γ 0 below
0. Since for some v we have γv −(m+1)αv = γv0 −αv < 0,and αv ≤ M , we have γv0 < M . Thus, after replacing γ with
γ 0 , the set P loses one element. We repeat this operation
until P ∈ i(V ).
As a corollary, we get the following normal form for
Parikh images of regular grammars:

for s = t, and anPempty set otherwise. We also haveaA(s, u, i + 1) =A(s, t, i) + a. We use theset→u∈δformulas to calculate sets A(s, t, i) for each i by induction;these sets are bounded polynomially. Ys0 is then a union ofA(s, s, i) for i ≤ |S|.
For each T ⊆ S of size at most |Σ|, let WT be theset of Parikh images of runs D such that T ⊆ supp(D),and ||D||∞ satisfies the limit from Theorem 7. Again, we
can calculate WT using a similar dynamic programmingalgorithm (we try all possible orderings of elements of T
on the path; for each ordering, we take the sum of theappropriate A(s, t, i) sets).
For each T ⊆ S of size at most |Σ|, and each sequence
Y1 . . . Ym of linearly independent elements of YT0 , take theA,B-frame given by WT and a matrix whose columns are
Y1 . . . Ym (if m < |Σ|, we fill the remaining columns withzeros). Let U be the union of these A, B-frames.
It is easy to show that U ⊆ P(G). The other inclusion,
P(G) ⊆ U , follows from Theorem 7 and Ys ⊆ Ys0 . Notethat we could not use the sets Ys directly, since calculatingthem is NP hard (by reduction of the Hamiltonian circuit
problem).
It turns out that Theorem 8 does not hold for NFAs overunbounded alphabet size and CFGs over unary alphabet,even in descriptional complexity sense.

Theorem 7 Let G be a regular commutative grammar,
and K ∈ NΣ . Then K ∈ P(G) iff there exists a run
2|Σ|
|Σ|/2
D in G, ||D||∞ = O(|S| |Σ|), and simple cycles
C1 , . . . , Cm , Ci ∈ Csupp(D) , suchPthat Ci are linearly
independent and K = P(D) + i αi P(Ci ) for some
α1 , . . . , αm .
Proof:Let D0 be a run in G such that K = P(D0 ). We
decompose the run D0 into a sum of simpler runs (onthe same
P support) and simple cycles, until we get D0 =D2 + C∈Csupp(D ) γC C, where D2 is a skeleton. From0
Lemma 4 we get that
P ||D2 ||∞ ≤ |δ|. By taking P’s, we
get K = P(D2 ) + Y ∈Ysupp(D ) γY Y , where γY ∈ N for0each Y .
Let P ⊆ Ysupp(D0 ) be the set of such cycle outputs Y
|Σ|
|Σ|/2
that γY ≥ L for L = |S| |Σ|. From Theorem 6 we
get that K can be decomposed in a way such that P islinearly independent.
P
Let D1 = D2 + Y ∈Ysupp(D ) −P γY Y . Since ||D2 ||∞ =2

1

Proposition 9 For each fixed positive integer d, there exists
a sequence {An,d }∞n=2 of deterministic finite automata An,dwith n + 1 states over an alphabet of size d whose Parikh
image contains at least Ω(nd−1 ) linear sets.
The automaton
An,d recognizes the languageSd
i=1 ai , where here Π stands for language
concatenation. We can then show that P(L(An,d )) hasΩ(nd−1 ) linear sets. For more details, see [To10].
Πni=1Proposition 10 There exists a small positive constant c anda sequence {Gn }∞n=1 of CFGs Gn of size at most cn over thealphabet Σ := {a} whose Parikh image contains precisely
2n linear sets.

|Σ|O(|S| ), γY < L, and there are at most O(|S| ) distinct
simple cycle images in Ysupp(D0 ) (since they are bounded|Σ|by O(|S|)),P we get that ||D1 ||∞ ≤ O(L |S| ). Now, K =D1 + Y ∈P γY Y .

This is done by a modification of the technique from
[PSW02] of succinct encoding large numbers. Our CFG
n−1
Gn contains nonterminals S, {Ai }i=0
, and {Bi }n−1i=0 , andconsists precisely of the following rules:

Theorem 8 Let G be a regular commutative grammar. Then
P(G) is a union of a polynomial number of A, B-frames,
where A = ||D||∞ and B = |S|. Moreover, we can compute
these A, B-frames in polynomial time.
Proof: Let a short cycle be a cycle C such that||C||1 ≤ |S|. Let Cs0 be the set of all short cycles for the
given grammar G, and Ys0 = P(Cs0 ). The set Ys0 for each states can be calculated using simple dynamic programming.
Indeed, let A(s, t, i) be the set of outputs of paths froms to t of length i. For i = 0 we have A(s, t, 0) = {0}S→

A0 . . . An−1

Ai
Ai

→
→

 for each 0 ≤ i < n
Bi for each 0 ≤ i < nBi→Bi−1 Bi−1

B0

→

a

for each 0 < i < nThe initial nonterminal is declared to be S. It is not hard toshow that this gives the desired CFG.
5

five states A, B, C, D, E; they are points with coordinates ( y(y+1), y) for y ∈ [0..31]). Since we generate2
z n together with (ABCDE)n , P(G) is a cone (i.e., aunbounded pyramid) with 32 edges (each edge is the line
, zy, z}) : z ∈ R} for some y), and hence we need{( zy(y+1)
2more than 16 three-dimensional A, B-frames to cover P(G).
This example generalizes to any number of states (bigger
examples are constructed using the same simple rule as theexample above) — we need more than 2n−2 A, B-frames
for a grammar with n states and two transitions for eachstate. Note that it is quite easy to write this grammar in thelimited form we use in this paper (i.e., for each derivationas → t, ||a||1 ≤ 1, ||t||1 ≤ 2) using O(n) states.

V. N ORMAL FORM FOR COMMUTATIVE GRAMMARSOVER BINARY ALPHABET

Theorem 11 Let Σ = {a, b}, and G be aSpositive commutative grammar over Σ. Then P(G) = i∈I Zi , where2|I| = O(|S| ), and Zi are A, B-frames, where A, B =O(1)O 2|S|.
Proof:Let D be a run of G, and T = supp(D). For Y ∈ YT , letb(Y ) = Yb /||Y ||1 ; let M (T ) be the matrix whose columns
M a and M b are the elements of YT with the smallest
and
|S|O(1)largest b(Y ), respectively. We have ||M ||∞ = O 2
2

from Lemma 4. There are at most |S| possible matrices M (T ). Let R(M ) be the set of runs D such that
M (supp(D)) = M . We will show that P(R(M )) is ofform WM + M NΣ .
P
We decompose D as D2 + C∈CT αC C, where D2
isP(D) is decomposed as P(D2 ) +P a skeleton. Thus,abΣY ∈YT αY Y + M βa + M βb , where βa ∈ N , αY ∈ N.
We can assume that each αY < det M , because otherwise we can replace (det M )Y by qa Y a + qb Y b , where
qa , qb ∈ N (the coefficients are integers from Lemma 1
and non-negative since Y a and Y b are extreme cycles).
O(1)Each Y and P(D2 ) is O 2|S|from Lemma 4, andO(1)there are O 2|S|
possible Y ’s, thus D3 = P(D2 ) +P|S|O(1)αYsatisfies
||D
||
=
O
2
.
Y
3
∞
Y ∈YT
By taking for WM the sets of possible D3 for all runs
from R(M ), we get the required conclusion.
In this proof, we have used some properties which hold
only for two letter alphabets (i.e., existence of extreme cycles). This was necessary – Theorem 11 does not generalize
straightforwardly to larger alphabets.

VI. N ORMAL FORM FOR COMMUTATIVE GRAMMARSOVER LARGER ALPHABET

The proof of the generalization Theorem 18 to alphabetsof larger (but still fixed) size is very long and technical. We
had to omit most proofs for space reasons.
In this proof, we will require lots of constants; someof them are dependant on other. To keep our constants
ordered, and make sure that there is no circular reference between them, we will name them consistently C1 , C2 , C3 , . . .
through the whole section; each constant will be definedin such a way that it will depend single exponentially on
the size of the grammar and/or polynomially on the lower
numbered constants. (C2 and C10 appear only in detailed
proofs and thus do not appear in this paper; we use the same
naming for consistence with the full version.) By induction,
all numbered constants depend single exponentially on thesize of the grammar. As usual, when we say Ci is polynomial
in Cj , we assume that the size of alphabet Σ is fixed. (If |Σ|p(|Σ|)
is not fixed, then Ci = O(Cj), where p is a polynomial.)
Let JΣ = {x ∈ RΣ : x ≥ 0, ||x||1 = 1}.
Let FC1 ⊆ [0..C5 ]1Σ (i.e., a set of some linear functions
over NΣ with integer coefficients up to C5 ) be such that foreach set of |Σ| − 1 vertices V ⊆ [0..C1 ]Σ , there exists a
non-zero f ∈ FC1 such that f V = 0. This can be done with
C5 polynomial in C1 .
Let LC3 = {0, C3 }Σ be the set of vertices of thehypercube of dimension |Σ| and edge length C3 .
Let R(C1 , C3 ) be the set of functions from FC1 × LC3
to {−1, 0, 1}.
For a r ∈ R, let∀f ∈ FC1 ∀l ∈ LC3
Σreg(r) =v∈N :,sgn(f v − f l) = rf,l∀f ∈ FC1 ∀l ∈ LC3
ΣReg(r) =v∈R :,sgn(f v − f l) ∈ {0, rf,l }x ≥ 0, x 6= 0,τ (r) =x ∈ RΣ : ∀f ∈ FC1 ∀l ∈ LC3.

sgn(f x) ∈ {0, rf,l }Theorem 12 There exists a sequence of context-free grammar (Gn ) over {x, y, z} such that Gn is of size O(n), andP(Gn ) is a union of Ω(2n ) A, B-frames.
The construction and its proof of correctness are nontrivial; see [Kop10]. We will present the general idea of theconstruction. Consider the following grammar.
S
A
B
C
D
E

→
→
→
→
→
→

0
B2
C2
D2
E2
0

|
|
|
|
|
|

SABCDEz
C 2 D2 E 2 xy
D2 E 2 x2 y
E 2 x4 y
x8 y
x16 y

The state S generates any number of z’s together withthe same number of ABCDE’s. ABCDE generates aconvex 32-gon on the surface N{x,y} (we get 32 corners
by deciding which transition always to use for each of

The following picture (Figure A) shows what JΣ andτ (r) ∩ JΣ look like for C1 = 2 and |Σ| = 3. (If t ∈ τ (r),6then also xt ∈ τ (r) for x > 0; thus, a cross of τ (r) and JΣ
gives us information about the whole τ (r).)

This observation is generalized in the following lemma,
whose proof is very technical.

zLemma 13 Let C1 , C3 , C4 ∈ N. There exist constants C7
polynomial in C1 , and C8 polynomial in C1 , C3 and C4 ,such that for each r ∈ R(C1 , C3 ), for each v ∈ reg(r), if||v||∞ ≥ C8 , then v = v0 + C4 t, where t ∈ τ (r) ∩ [0..C7 ]Σ
and v0 ∈ reg(r). Also, for each v ∈ reg(r) there is a v 0 ∈reg(r) such that ||v 0 ||∞ < C8 and v − v 0 ∈ C4 ZΣ .
Another fact we need is a polynomially bounded separation property for disjoint convex sets in RΣ . It is awell known property of convex sets that two disjoint closed
convex polygons in affine space can be separated strictlywith a hyperplane. In our case, the space is JΣ , the polygons
are its intersections with P ⊕P and Q⊕P , and we need apolynomial bound for coefficients of the hyperplane.

yxFigure A

The big equilateral triangle is JΣ . The 19 small whitecircles are points v/||v||1 for v ∈ [0..C1 ]Σ . We connect eachpair of points with a line; these lines correspond to elementsof FC1 .
For each r, τ (r) ∩ JΣ is a part of the triangle definedby their relationship with each line (above, below, or on
the line). Thus, each τ (r) is either an empty set, or one ofthe points where lines cross (including the 19 circles), ora line segment between two consecutive points where thelines cross, or a polygon bounded by lines.
The next picture shows the subdivision of RΣ into regions(reg and Reg) for |Σ| = 2 and C1 = 3; C3 is the size of thedark square in the bottom left corner. Lines shown on the
picture are boundaries between regions. They are groupedin bundles—each bundle corresponds to different element of
FC1 . Lines in each bundle correspond to different elementsof LC3 .

Lemma 14 Let C7 ∈ N. Then there exists C9 polynomial
in C7 such that:Let P, Q ⊆ [0..C7 ]Σ such that P ⊕P ∩ Q⊕P = {0}, and0∈/ P, Q. Then there is a Φ ∈ N1Σ (i.e., a linear function overΣN with integer coefficients) such that ΦP > 0, ΦQ < 0,and ||Φ||∞ ≤ C9 .
We use these two lemmas to show that an intersection ofa region and a linear set with bounded offset and periods
can be expressed as an intersection of this region and apolynomially bounded A, B-frame.
Lemma 15 Let C1 , C3 ∈ N. Then there exists a constant
C11 such that:
Let S = W + Y ⊕N , where W ⊆ [0..C3 ]Σ and Y ⊆[0..C1 ]Σ . Let r ∈ R(C1 , C3 ). Then there exists a matrixΣM ∈ [0..C1 ]Σ
Σ and W1 ⊆ [0..C11 ] such that S ∩ reg(r) =Σ(W1 + M N ) ∩ reg(r).
After applying Lemma 15 to commutative grammars, we
get:Theorem 16 Let G be a positive commutative grammar,
and let r be a region.
The intersection of P(G) ∩ reg(r) is an intersection ofreg(r) and a polynomial union of C11 , C1 -frames, where
C11 and C1 are single exponential in |G|.

There are several types of regions: bounded ones, 8 unbounded regions in angular shapes (between two consective
bundles of lines — there are 9 bundles of lines because
vectors in [0..3]Σ go in 9 directions), and unbounded stripshaped regions between semi-lines in the same bundle. It
can be easily calculated that each point where bundles oflines going in different directions cross has its coordinates
bounded polynomially (by O(AB 2 )), and thus for region
Reg(r) we can find a polynomially bounded v 0 ∈ Reg(r).
Moreover, for each v ∈ reg(r) and each C4 we can find apolynomially bounded v 0 ∈ reg(r) such that v − v 0 ∈ C4 ZΣ .

VII. A PPLICATIONS
Decision problem for Parikh images
Our normal form theorems lead to efficient algorithms
for the basic problems regarding Parikh images of regular
grammars (equivalently, Parikh images of finite automata)and (positive) context free grammars (equivalently, Parikh
images of push down automata, or of finite automata on
trees) over an alphabet of fixed size. These basic problems
include deciding membership (check whether v ∈ ZΣ , where7v is given in binary, is in P(G)), universality (P(G) = ZΣ ?),inclusion (P(G) ⊆ P(H)?), equivalence (P(G) = P(H)?),disjointness (are P(G) and P(H) disjoint?). The following
table summarizes complexities of these problems. F stands
for alphabets of fixed size, while U stands for alphabet of
unfixed size.
regular languages
alphabet size
1
2F
membershipPPP
universality
coNPc coNPc coNPc
inclusion
coNPc coNPc coNPc
disjointnessP
P
P
context-free languages
alphabet size
1
2F
membership
NPc
NPc
NPc
universality
ΠP
ΠP
ΠP
2
2
2
P
P
inclusion
Π2 c
Π2 c
ΠP
2c
disjointness coNPc coNPc coNPc

Proof of Theorem 18: The problem is ΠP
2 -hard because
we can reduce the problem of semilinear set inclusion[Huy80] to it.
We will first show the proof for d = 2.
S Usingk Theorem 11, we can write each P(Gk ) ask
i∈Ik Zi , where Ik is a polynomial setof indices and ZiO(1)is a A, B-frame, where A and B are O 2|S|.
From Lemma 17 we get that it is enough to checkinclusion on vectors v ∈ NΣ of size |v| < P = O((A +B)O(|I1 |+|I2 |) ). We call such vectors small vectors.
A witness for membership of v in a grammar G is a run D
such that P(D) = v. For each small v ∈ P(G) we can finda small witness for its membership, i.e., one that does notcontain non-productive cycles (i.e., C such that P(C) = 0;such cycles can be eliminated), and thus it can be described
as a string of length polynomial in size of G.
For each small v, and each small witness of membershipof v in G1 , we have to find a small witness of membershipof v in G2 . This can be done in ΠP
2.
For d > 2, we have to apply these methods separately foreach region from Theorem 16.
See [Kop10], [To10] for the remaining algorithms andlower bounds.
An immediate corollary of our result on inclusion of
Parikh images of CFGs over a fixed alphabet is related to the
problem of reachability equivalence for communication-free
Petri nets, which was shown in [Yen96] to be solvable indouble exponential time. In the case of nets with a fixed
number of places, our result gives a substantially lower
complexity.

U
NPc
?
?
coNPc
U
NPc
?
?
?

For example, checking membership for Parikh imagesof regular grammars boils down to generating the normal
form (Theorem 8) and then checking whether any of thesemilinear sets in the normal form contain v. Since thenormal form uses linearly independent periods for eachsemilinear set, this can be done by solving a system of
equations.
Algorithms for problems regarding context free grammars
are based on the following property of unions of a small
number of A, B-frames.
Lemma 17 Let Wi ⊆ [0..C3 ]Σ , Mi ⊆ [0..C1 ]Σ
Σ for i ∈ I.
Let Zi = Wi + Mi NΣ . Then for each v ∈ NΣ there exists av 0 ∈ NΣ such that ||v 0 ||∞ is polynomial in C1 and C3 for
fixed |Σ|, and, for each i, v ∈ Zi iff v 0 ∈ Zi .

Theorem 19 Reachability equivalence for communication
free nets with a fixed number of places is ΠP
2 -complete.
Integer Programming
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.
On the other hand, for k = 1, it is well-known that
there is a pseudopolynomial-time algorithm for this problem (a.k.a. knapsack problem), which remains NP-complete
under binary representation of input numbers. Furthermore,
Papadimitriou [Pap81] has established a pseudopolynomialtime algorithm for solving IP, for any fixed k ≥ 1. Using
Theorem 8, we could show that the problem remains polytime solvable (for any fixed k ≥ 1) even if the numbers inb are given in binary (and A in unary).

Proof: Assume that the matrices Mi are non-degenerate(the case of degenerate matrices can be solved easily bychanging the matrices).
Let C4 be the least common multiple of determinants ofmatrices Mi , C = O(C1 O(|I|) ).
Let v ∈ NΣ . Let v 0 be the vector v 0 from Lemma 13 forour v and C; We will show that it satisfies our conditions.
It is enough to check whether v ∈ Z 0 iff v 0 ∈ Z 0 for each0
Z of form w0 + Mi NΣ , where w0 ∈ Wi .
Since Mi is non-degenerate, for some α, α0 ∈ QΣ wehave v = w0 + Mi α and v 0 = w0 + Mi α0 . Since v 0 is in
the same region as v, α ≥ 0 iff α0 ≥ 0. On the other hand,v − v 0 ∈ CZΣ ⊆ (det Mi )ZΣ ⊆ Mi ZΣ from Lemma 1.
Thus, v ∈ NΣ iff v 0 ∈ NΣ .

Theorem 20 Fix an integer k > 0. Given a k-by-m integer
matrix A, where numbers are represented in unary, and avector b ∈ Zk , where numbers are represented in binary.
Then, checking whether the integer program Ax = b (x ≥ 0)
has a solution can be done in polynomial time.

Theorem 18 Let G1 and G2 be two commutative grammars
over Σ = {a, b}. Then the problem of deciding P(G1 ) ⊆P(G2 ) is ΠP
2 -complete.
8maximum number appearing in clock constraints, and kφ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 wasderived by carefully analyzing the complexity of effective
semilinearity of the Parikh images of languages recognized
by reversal-bounded counter machines [Iba78] and replacing
the application of Parikh’s Theorem in [Iba78] by the linear
translation of [VSS05] from CFGs to existential Presburger
formulas expressing their Parikh images. By replacing theapplication of the translation of [VSS05] by Theorem 8 andnot allowing a single free counter, we can easily obtain thefollowing upper bound.

Theorem 20 is known to be true when k = 1, by solutions
to the Frobenius problem, and has such applications as thecoin problem [Ram05].
Polynomial PAC-learnability of semilinear sets
Valiant’s notion of PAC (Probably Approximately Correct)
learning is a standard model in computational learningtheory [AB92]. In this framework, a learning algorithm isrequired 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 [Abe95]. In particular, learningsemilinear 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 learningtheory. On the positive side, he shows that semilinear sets ofdimension 1 and 2 can be poly-time PAC-learned when thenumbers are represented in unary. To this end, he establisheda normal form lemma for semilinear sets of dimension 2 (inunary), which is simply a special case of Theorem 8 fordimension 2. However, his proof makes use of geometricfacts that are specific to R2 . For this reason, he leaves open
the learnability question of semilinear sets in unary overany fixed dimension k > 2 [Abe95, Section 9]. Replacing
Abe’s normal form lemma with Theorem 8 and following
the proof of [Abe95, Theorem 6.1], we can easily deducethe more general theorem (a sketch is given in [To10]).

Theorem 22 Model checking LTL over reversal-bounded
counter systems with discrete clocks is solvable in timepolynomial in n and exponential in c, k, r, kφk, and t.
It turns out that none of the exponents in the algorithm canbe lowered, assuming the usual complexity assumption (see[To10]).
ACKNOWLEDGMENT
We thank anonymous referees for their useful comments.
The first author thanks Sławek Lasota for his introduction tothese problems, and to everyone on the Automata Scientific
Excursion for the great atmosphere of research. The second
author thanks Shunichi Amano, Floris Geerts, Stefan Göller,
Filip Murlak, Benjamin Rubinstein, and Tony Tan for theirhelpful comments. The first author is supported by the Polishgovernment grant no. N206 008 32/0810. The second author
is supported by EPSRC grant E005039.

Theorem 21 Semilinear sets in unary representation overany fixed dimension k ≥ 1 can be polynomially PAC-learned
with respect to concept complexity.

R EFERENCES[Abe95] N. Abe. Characterizing PAC-Learnability of Semilinear
Sets. Inf. Comput. 116(1):81–102 (1995)

Verifying counter systems
Minsky’s counter machines are well-known to be aTuring-powerful model of computation. In verification literature, many decidable subclasses of counter machines havebeen studied including reversal-bounded counter systems[GI81], [Iba78], [TL10], and their extensions with pushdown
stacks and discrete clocks [DIBKS00], [TL10]. Intuitively,
r-reversal k-counter systems are simply Minsky’s countermachines with k counters, each of which can change from anincrementing mode to a decrementing mode (or vice versa)
only for a fixed r number of times. Their connection to our
result is due to the use of Parikh’s Theorem for obtaining
decidability (initially used in [Iba78]).
In [TL10], 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 reversal-bounded).
More precisely, if t is the number of clocks, n the numberof states in the finite control, c the size (in binary) of the[AB92] M. Anthony and N. Biggs. Computational learningtheory: an introduction. Cambridge University Press, 1992.
[BHLW10] P. Barcelo, C. Hurtado, L. Libkin and P. Wood. Expressive languages for path queries over graph-structured data. To
appear in PODS’10.
[BM99] C. Beeri and T. Milo. Schemas for Integration and Translation of Structured and Semi-structured Data. In ICDT’99,
pages 296–313.
[Chr03] M. Chrobak. Finite automata and unary languages. In
TCS 302:497–498 (2003)[DIBKS00] Z. Dang, O. Ibarra, T. Bultan, R. Kemmerer and
J. Su. Binary reachability analysis of discrete pushdown timed
automata In CAV’00, pages 69–84.
[EN94] J. Esparza and M. Nielsen. Decidability issues for Petrinets – a survey. Bulletin of the EATCS 52:245–262 (1994)9

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

[Esp97] J. Esparza. Petri nets, Commutative Context-Free Grammars, and Basic Parallel Processes.
Fundam. Inform.
31(1):13–25 (1997)[Rei85] W. Reisig. Petri Nets: An Introduction. Springer, 1985.
[GS66] S. Ginsburg and E. H. Spanier. Semigroups, Presburger
Formulas, and Languages. Pacific Journal of Mathematics
16(2):285–296 (1966)[SSM07] H. Seidl, Th. Schwentick, and A. Muscholl. Counting
in Trees. Texts in Logic and Games 2:575–612 (2007)[Sto77] L. Stockmeyer. The polynomial-time hierarchy. Theoret.
Comput. Sci. 3:1–22 (1977)[GMT09] S. Göller, R. Mayr and A. W. To. On the Computational
Complexity of Verifying One-Counter Processes. In LICS’09,
pages 235–244.

[To09] A. W. To. Unary finite automata vs. arithmetic progressions. IPL 109(17):1010–1014 (2009)[GI81] E. Gurari and O. Ibarra. The Complexity of Decision
Problems for Finite-Turn Multicounter Machines. JCSS
22:220–229 (1981)[To10] A. W. To. Parikh Images of Regular Languages: Complexity and Applications. CoRR abs/1002.1464: (2010)[Hac76] M.H.T. Hack. Decidability Questions for Petri Nets. PhD
Thesis, MIT, 1976.

[TL10] A. W. To and L. Libkin. Algorithmic metatheorems for
decidable LTL model checking over infinite systems. In
FoSSaCS’10, pages 221–236.

[Huy80] T. D. Huynh. The Complexity of Semilinear Sets. In
ICALP’80, pages 324–337.

[VSS05] K. N. Verma, H. Seidl and T. Schwentick. On thecomplexity of equational Horn clauses. In CADE’05, pages
337–352.

[Huy84] D. T. Huynh. Deciding the inequivalence of context-freegrammars with 1-letter terminal alphabet is ΣP
2 –complete.
TCS 33:305–326 (1984)[Yen96] H. C. Yen. On reachability equivalence for BPP-nets. TCS
179:301–317 (1996)[Huy85] D. T. Huynh. Complexity of equivalence problems forcommutative grammars. Inform. and Control 66(1/2):103–
121 (1985)[Huy86] D. T. Huynh. A simple proof for the ΣP
2 upper boundof the inequivalence problem for semilinear sets. Inform.
Process. Cybernet. (EIK) 22:147–156 (1986)[Hüt94] H. Hüttel. Undecidable equivalences for basic parallel
processes. In TACS’94.
[Iba78] O. Ibarra. Reversal-bounded multicounter machines andtheir decision problems. JACM 25:116–133 (1978)[Kop10] E. Kopczyński. Complexity of Problems for Commutative
Grammars. CoRR abs/1003.4105: (2010)[Koz97] Automata and Computability. Springer, 1997.
[Kos82] S. R. Kosaraju. Decidability of Reachability in Vector
Addition Systems. In STOC’82, pages 267–281.
[Mart02] A. Martinez. Efficient computation of regular expressions from unary NFAs. In DFCS’02, pages 174–187.
[Pap81] C. H. Papadimitriou. On the complexity of integer
programming. J. ACM 28(4): 765–768 (1981)[Par66] R. J. Parikh. On context-free languages. JACM 13(4):570–
581, 1966.
[Pet81] J. Peterson. Petri Net Theory and the Modeling of Systems.
Prentice-Hall, 1981.
[PSW02] G. Pighizzini, J. Shallit, and M. Wang. Unary ContextFree Grammars and Pushdown Automata, Descriptional Complexity and Auxiliary Space Lower Bounds. JCSS 65(2): 393–
414 (2002)

10