{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T03:04:30Z","timestamp":1767236670750,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2015,6,23]],"date-time":"2015-06-23T00:00:00Z","timestamp":1435017600000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The value 1 problem is a decision problem for probabilistic automata over\nfinite words: given a probabilistic automaton, are there words accepted with\nprobability arbitrarily close to 1? This problem was proved undecidable\nrecently; to overcome this, several classes of probabilistic automata of\ndifferent nature were proposed, for which the value 1 problem has been shown\ndecidable. In this paper, we introduce yet another class of probabilistic\nautomata, called leaktight automata, which strictly subsumes all classes of\nprobabilistic automata whose value 1 problem is known to be decidable. We prove\nthat for leaktight automata, the value 1 problem is decidable (in fact,\nPSPACE-complete) by constructing a saturation algorithm based on the\ncomputation of a monoid abstracting the behaviours of the automaton. We rely on\nalgebraic techniques developed by Simon to prove that this abstraction is\ncomplete. Furthermore, we adapt this saturation algorithm to decide whether an\nautomaton is leaktight. Finally, we show a reduction allowing to extend our\ndecidability results from finite words to infinite ones, implying that the\nvalue 1 problem for probabilistic leaktight parity automata is decidable.<\/jats:p>","DOI":"10.2168\/lmcs-11(2:12)2015","type":"journal-article","created":{"date-parts":[[2016,11,21]],"date-time":"2016-11-21T13:13:12Z","timestamp":1479733992000},"source":"Crossref","is-referenced-by-count":5,"title":["Deciding the value 1 problem for probabilistic leaktight automata"],"prefix":"10.46298","volume":"Volume 11, Issue 2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6576-4680","authenticated-orcid":false,"given":"Nathana\u00ebl","family":"Fijalkow","sequence":"first","affiliation":[]},{"given":"Hugo","family":"Gimbert","sequence":"additional","affiliation":[]},{"given":"Edon","family":"Kelmendi","sequence":"additional","affiliation":[]},{"given":"Youssouf","family":"Oualhadj","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2015,6,23]]},"reference":[{"key":"994:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1572\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1572\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:06:38Z","timestamp":1681243598000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1572"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,23]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-11(2:12)2015","relation":{"is-same-as":[{"id-type":"arxiv","id":"1504.04136","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1504.04136","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2015,6,23]]},"article-number":"1572"}}