Reference:

Christoph Haase, Stefan Kiefer, and Markus Lohrey. Counting problems for Parikh images. In Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), pages 12:1–12:13, 2017.

Abstract:

Given finite-state automata (or context-free grammars) A,B over the same alphabet and a Parikh vector p, we study the complexity of deciding whether the number of words in the language of A with Parikh image p is greater than the number of such words in the language of B. Recently, this problem turned out to be tightly related to the cost problem for weighted Markov chains. We classify the complexity according to whether A and B are deterministic, the size of the alphabet, and the encoding of p (binary or unary).

Suggested BibTeX entry:

@inproceedings{17HKL-MFCS,
    author = {Christoph Haase and Stefan Kiefer and Markus Lohrey},
    booktitle = {Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
    pages = {12:1--12:13},
    title = {Counting Problems for {P}arikh Images},
    year = {2017}
}