License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2017.12
URN: urn:nbn:de:0030-drops-80597
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8059/
Haase, Christoph ;
Kiefer, Stefan ;
Lohrey, Markus
Counting Problems for Parikh Images
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).
BibTeX - Entry
@InProceedings{haase_et_al:LIPIcs:2017:8059,
author = {Christoph Haase and Stefan Kiefer and Markus Lohrey},
title = {{Counting Problems for Parikh Images}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {12:1--12:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-046-0},
ISSN = {1868-8969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and Jean-Francois Raskin},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8059},
URN = {urn:nbn:de:0030-drops-80597},
doi = {10.4230/LIPIcs.MFCS.2017.12},
annote = {Keywords: Parikh images, finite automata, counting problems}
}
|
Keywords: |
|
Parikh images, finite automata, counting problems |
|
Collection: |
|
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) |
|
Issue Date: |
|
2017 |
|
Date of publication: |
|
01.12.2017 |
