Decision Problems for Probabilistic Finite Automata on Bounded Languages

作者：Bell Paul C^*; Halava Vesa; Hirvensalo Mika

来源：Fundamenta Informaticae, 2013, 123(1): 1-14.

DOI：10.3233/FI-2013-797

• Probabilistic finite automata
• Bounded languages
• Formal power series
• Undecidability
• Hilbert%26apos
• s tenth problem

We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert%26apos;s tenth problem. We then consider the set of so called %26quot;F-Problems%26quot; (emptiness, infiniteness, containment, disjointness, universe and equivalence) and show that they are also undecidable for bounded (non-)strict cut-point languages on probabilistic finite automata. %26lt;br%26gt;For a finite set of matrices {M-1, M-2, ... , M-k} subset of Q(txt), we then consider the decidability of computing the maximal spectral radius of any matrix in the set X = {M-1(j1) M-2(j2) ... M-k(jk)vertical bar j(1), j(2), ... , j(k) %26gt;= 0}, which we call a bounded matrix language. Using an encoding of a probabilistic finite automaton shown in the paper, we prove the surprising result that determining if the maximal spectral radius of a bounded matrix language is less than or equal to one is undecidable, but determining whether it is strictly less than one is in fact decidable (which is similar to a result recently shown for quantum automata).

• 出版日期2013