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
|
| _version_ | 1797105311916490752 |
|---|---|
| author | Haase, CJ Kiefer, S Lohrey, M |
| author_facet | Haase, CJ Kiefer, S Lohrey, M |
| author_sort | Haase, CJ |
| collection | OXFORD |
| description | 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). |
| first_indexed | 2024-03-07T06:45:41Z |
| format | Conference item |
| id | oxford-uuid:fac5d3d9-274e-413a-9734-2b40541cbd62 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:45:41Z |
| publishDate | 2017 |
| publisher | Schloss Dagstuhl |
| record_format | dspace |
| spelling | oxford-uuid:fac5d3d9-274e-413a-9734-2b40541cbd622022-03-27T13:08:46ZCounting problems for Parikh imagesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:fac5d3d9-274e-413a-9734-2b40541cbd62Symplectic Elements at OxfordSchloss Dagstuhl2017Haase, CJKiefer, SLohrey, MGiven 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). |
| spellingShingle | Haase, CJ Kiefer, S Lohrey, M Counting problems for Parikh images |
| title | Counting problems for Parikh images |
| title_full | Counting problems for Parikh images |
| title_fullStr | Counting problems for Parikh images |
| title_full_unstemmed | Counting problems for Parikh images |
| title_short | Counting problems for Parikh images |
| title_sort | counting problems for parikh images |
| work_keys_str_mv | AT haasecj countingproblemsforparikhimages AT kiefers countingproblemsforparikhimages AT lohreym countingproblemsforparikhimages |