Facial reconstruction

Search LJMU Research Online

Browse Repository | Browse E-Theses

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)

Polynomially Ambiguous Probabilistic Automata.pdf - Accepted Version
Available under License Creative Commons Attribution.

Download (426kB) | Preview


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 & Mathematics
Publisher: Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
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 View Item