Haase, C;
Haase, S;
Lohrey, M;
(2017)
Counting problems for parikh images.
In:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017).
(pp. 12:1-12:13).
Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik: Dagstuhl, Germany.
Preview |
Text
LIPIcs-MFCS-2017-12.pdf - Published Version Download (535kB) | Preview |
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).
| Type: | Proceedings paper |
|---|---|
| Title: | Counting problems for parikh images |
| Event: | 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017) |
| ISBN-13: | 9783959770460 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.MFCS.2017.12 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.MFCS.2017.12 |
| Language: | English |
| Additional information: | © Christoph Haase, Stefan Kiefer, and Markus Lohrey; licensed under Creative Commons License CC-BY. |
| Keywords: | Parikh images, finite automata, counting problems |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery.ucl.ac.uk/id/eprint/10088922 |
Archive Staff Only
 |
View Item |
