LIPIcs.MFCS.2017.12.pdf
- Filesize: 0.51 MB
- 13 pages
Document
Counting Problems for Parikh Images
Authors
-
Part of:
Volume:
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-01
Cite AsGet BibTex
Christoph Haase, Stefan Kiefer, and Markus Lohrey. Counting Problems for Parikh Images. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 12:1-12:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.MFCS.2017.12
https://doi.org/10.4230/LIPIcs.MFCS.2017.12
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).
Keywords
- Parikh images
- finite automata
- counting problems
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
E. Allender and K. W. Wagner. Counting hierarchies: Polynomial time and constant depth circuits. Bulletin of the EATCS, 40:182-194, 1990.
-
A. Bertoni, M. Goldwurm, and N. Sabadini. The complexity of computing the number of strings of given length in context-free languages. Theor. Comput. Sci., 86(2):325-342, 1991.
-
E. Galby, J. Ouaknine, and J. Worrell. On matrix powering in low dimensions. In Proc. STACS 2015, volume 30 of LIPIcs, pages 329-340, 2015.
-
F. Green, J. Köbler, K. W. Regan, T. Schwentick, and J.Torán. The power of the middle bit of a #p function. Journal of Computer and System Sciences, 50(3):456-467, 1995.
-
C. Haase and S. Kiefer. The odds of staying on budget. In Proc. ICALP 2015, Part II, volume 9135 of LNCS, pages 234-246. Springer, 2015.
- C. Haase, S. Kiefer, and M. Lohrey. Efficient quantile computation in markov chains via counting problems for parikh images. CoRR, abs/1601.04661, 2016. URL: http://arxiv.org/abs/1601.04661.
-
C. Haase, S. Kiefer, and M. Lohrey. Computing quantiles in Markov chains with multi-dimensional costs. In Proc. LICS 2017. IEEE, 2017. To appear.
-
H. B. Hunt III, D. J. Rosenkrantz, and T. G. Szymanski. On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. Syst. Sci., 12(2):222-268, 1976.
-
E. Kopczyński. Complexity of problems of commutative grammars. Log. Meth. Comput. Sci., 11(1), 2015.
-
D. Kuske and M. Lohrey. First-order and counting theories of omega-automatic structures. J. Symbolic Logic, 73:129-150, 2008.
-
R. E. Ladner. Polynomial space counting problems. SIAM J. Comput., 18(6):1087-1097, 1989.
-
M. Mahajan and V. Vinay. A combinatorial algorithm for the determinant. In Proc. SODA 1997, pages 730-738. ACM/SIAM, 1997.
-
C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
-
Z. Sawa. Efficient construction of semilinear representations of languages accepted by unary nondeterministic finite automata. Fundam. Inform., 123(1):97-106, 2013.
-
L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time (preliminary report). In Proc. STOC 1973, pages 1-9. ACM, 1973.
-
S. Toda. PP is as hard as the polynomial-time hierarchy. SIAM J. Comput., 20(5):865-877, 1991.