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/
Go to the corresponding LIPIcs Volume Portal


Haase, Christoph ; Kiefer, Stefan ; Lohrey, Markus

Counting Problems for Parikh Images

pdf-format:
LIPIcs-MFCS-2017-12.pdf (0.5 MB)


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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI