Counting problems for Parikh images
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 t...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2017
|
| Summary: | 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). |
|---|