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.CONCUR.2020.22
URN: urn:nbn:de:0030-drops-128344
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12834/
Bell, Paul C. ;
Semukhin, Pavel
Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs
Abstract
We show the surprising result that the cutpoint isolation problem is decidable for probabilistic finite automata where input words are taken from a letter-bounded context-free language. A context-free language ℒ is letter-bounded when ℒ ⊆ a₁^* a₂^* ⋯ a_?^* for some finite ? > 0 where each letter is distinct. A cutpoint is isolated when it cannot be approached arbitrarily closely. The decidability of this problem is in marked contrast to the situation for the (strict) emptiness problem for PFA which is undecidable under the even more severe restrictions of PFA with polynomial ambiguity, commutative matrices and input over a letter-bounded language as well as to the injectivity problem which is undecidable for PFA over letter-bounded languages. We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous. We also show that the problem is at least NP-hard and use our decision procedure to solve several related problems.
BibTeX - Entry
@InProceedings{bell_et_al:LIPIcs:2020:12834,
author = {Paul C. Bell and Pavel Semukhin},
title = {{Decidability of Cutpoint Isolation for Probabilistic Finite Automata on Letter-Bounded Inputs}},
booktitle = {31st International Conference on Concurrency Theory (CONCUR 2020)},
pages = {22:1--22:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-160-3},
ISSN = {1868-8969},
year = {2020},
volume = {171},
editor = {Igor Konnov and Laura Kov{\'a}cs},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12834},
URN = {urn:nbn:de:0030-drops-128344},
doi = {10.4230/LIPIcs.CONCUR.2020.22},
annote = {Keywords: Probabilistic finite automata, cutpoint isolation problem, letter-bounded context-free languages}
}
|
Keywords: |
|
Probabilistic finite automata, cutpoint isolation problem, letter-bounded context-free languages |
|
Collection: |
|
31st International Conference on Concurrency Theory (CONCUR 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
26.08.2020 |
