License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2021.15
URN: urn:nbn:de:0030-drops-144559
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14455/
Go to the corresponding LIPIcs Volume Portal

Bell, Paul C. ; Semukhin, Pavel

Decision Questions for Probabilistic Automata on Small Alphabets

pdf-format:
LIPIcs-MFCS-2021-15.pdf (0.7 MB)

Abstract

We study the emptiness and λ-reachability problems for unary and binary Probabilistic Finite Automata (PFA) and characterise the complexity of these problems in terms of the degree of ambiguity of the automaton and the size of its alphabet. Our main result is that emptiness and λ-reachability are solvable in EXPTIME for polynomially ambiguous unary PFA and if, in addition, the transition matrix is over {0, 1}, we show they are in NP. In contrast to the Skolem-hardness of the λ-reachability and emptiness problems for exponentially ambiguous unary PFA, we show that these problems are NP-hard even for finitely ambiguous unary PFA. For binary polynomially ambiguous PFA with commuting transition matrices, we prove NP-hardness of the λ-reachability (dimension 9), nonstrict emptiness (dimension 37) and strict emptiness (dimension 40) problems.

BibTeX - Entry

@InProceedings{bell_et_al:LIPIcs.MFCS.2021.15,
  author =	{Bell, Paul C. and Semukhin, Pavel},
  title =	{{Decision Questions for Probabilistic Automata on Small Alphabets}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14455},
  URN =		{urn:nbn:de:0030-drops-144559},
  doi =		{10.4230/LIPIcs.MFCS.2021.15},
  annote =	{Keywords: Probabilistic finite automata, unary alphabet, emptiness problem, bounded ambiguity}
}

Keywords: Probabilistic finite automata, unary alphabet, emptiness problem, bounded ambiguity
Collection: 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Issue Date: 2021
Date of publication: 18.08.2021

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