  We consider Parikh images of languages accepted by non-deterministic finite
automata and context-free grammars; in other words, we treat the languages in a
commutative way --- we do not care about the order of letters in the accepted
word, but rather how many times each one of them appears. In most cases we
assume that the alphabet is of fixed size. We show tight complexity bounds for
problems like membership, equivalence, and disjointness. In particular, we show
polynomial algorithms for membership and disjointness for Parikh images of
non-deterministic finite automata over fixed alphabet, and we show that
equivalence is Pi2P complete for context-free grammars over fixed terminal
alphabet.
