Polynomially Ambiguous Probabilistic Automata on Restricted Languages

Bell, PC Polynomially Ambiguous Probabilistic Automata on Restricted Languages. In: LIPIcs : Leibniz International Proceedings in Informatics , 132. (International Colloquium on Automata, Languages and Programming (ICALP), 08 July 2019 - 12 July 2019, Patras, Greece). (Accepted)

Preview

Text Polynomially Ambiguous Probabilistic Automata.pdf - Accepted Version Available under License Creative Commons Attribution. Download (426kB) | Preview

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 non-strict cut-points of polynomially ambiguous PFA remains undecidable even when the input word is over a bounded language and all PFA transition matrices are commutative. In doing so, we introduce a new technique based upon the Turakainen construction of a PFA from a Weighted Finite Automata which can be used to generate PFA of lower dimensions and of subexponential ambiguity. We also study freeness/injectivity problems for polynomially ambiguous PFA and study the border of decidability and tractability for various cases.

Item Type:	Conference or Workshop Item (Paper)
Uncontrolled Keywords:	Probabilistic finite automata; ambiguity; undecidability; bounded language; emptiness
Subjects:	Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions:	Computer Science and Mathematics
Publisher:	Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
Date of acceptance:	19 April 2019
Date of first compliant Open Access:	14 June 2019
Date Deposited:	14 Jun 2019 10:37
Last Modified:	13 Apr 2022 15:17
Editors:	Baier, C, Chatzigiannakis, I, Flocchini, P and Leonardi, S
URI:	https://researchonline.ljmu.ac.uk/id/eprint/10880

View Item