Polynomially ambiguous probabilistic automata on restricted languages

Bell, Paul

Abstract

We consider the computability and complexity of decision questions for Probabilistic Finite Automata (PFA) with sub-exponential ambiguity. We show that the emptiness problem for strict and non-strict cut-points of polynomially ambiguous commutative PFA remains undecidable, implying that the problem is undecidable when inputs are from a letter monotonic language. We show that the problem remains undecidable over a binary input alphabet when the input word is over a bounded language, in the noncommutative case. In doing so, we introduce a new technique based upon the Turakainen construction of a PFA from a Weighted Finite Automaton which can be used to generate PFA of lower dimensions and of sub-exponential ambiguity. We also study freeness/injectivity problems for polynomially ambiguous PFA and study the border of decidability and tractability for various cases.

Citation

Bell, P. (2022). Polynomially ambiguous probabilistic automata on restricted languages. Journal of Computer and System Sciences, 53 - 65. https://doi.org/10.1016/j.jcss.2022.02.002

• Acceptance Date: Feb 9, 2022
• Publication Date: Aug 1, 2022
• Journal: Journal of Computer and System Sciences
• Print ISSN: 0022-0000
• Publisher: Elsevier
• Pages: 53 - 65
• DOI: https://doi.org/10.1016/j.jcss.2022.02.002
• Keywords: Probabilistic finite automataAmbiguityUndecidabilityBounded languageFormal language theory
• Public URL: https://keele-repository.worktribe.com/output/423611
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0022000022000162?via%3Dihub