{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T16:53:19Z","timestamp":1753894399147,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We study the emptiness and $\\lambda$-reachability problems for unary and\nbinary Probabilistic Finite Automata (PFA) and characterise the complexity of\nthese problems in terms of the degree of ambiguity of the automaton and the\nsize of its alphabet. Our main result is that emptiness and\n$\\lambda$-reachability are solvable in EXPTIME for polynomially ambiguous unary\nPFA and if, in addition, the transition matrix is binary, we show they are in\nNP. In contrast to the Skolem-hardness of the $\\lambda$-reachability and\nemptiness problems for exponentially ambiguous unary PFA, we show that these\nproblems are NP-hard even for finitely ambiguous unary PFA. For binary\npolynomially ambiguous PFA with fixed and commuting transition matrices, we\nprove NP-hardness of the $\\lambda$-reachability (dimension 9), nonstrict\nemptiness (dimension 37) and strict emptiness (dimension 40) problems.<\/jats:p>","DOI":"10.46298\/lmcs-19(4:36)2023","type":"journal-article","created":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T08:55:12Z","timestamp":1703148912000},"source":"Crossref","is-referenced-by-count":0,"title":["Decision Questions for Probabilistic Automata on Small Alphabets"],"prefix":"10.46298","volume":"Volume 19, Issue 4","author":[{"given":"Paul C.","family":"Bell","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Semukhin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2023,12,21]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/12731\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/12731\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,21]],"date-time":"2023-12-21T08:55:12Z","timestamp":1703148912000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/9753"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,21]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(4:36)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"2105.10293v3","asserted-by":"subject"},{"id-type":"arxiv","id":"2105.10293v2","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2105.10293","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2105.10293","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2023,12,21]]},"article-number":"9753"}}