Affiliations: Department of Computer Science, Loughborough University, Loughborough, LE11 3TU, UK. [email protected] | TUCS-Turku Centre for Computer Science, Department of Mathematics, University of Turku, FIN-20014, Turku, Finland, [email protected], [email protected]
Note: [] Address for correspondence: Department of Computer Science, Loughborough University, Loughborough, LE11 3TU, UK
Abstract: 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's tenth problem. We then consider the set of so called “F-Problems” (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. For a finite set of matrices $\{M_1, M_2, \ldots ,M_k\} \subseteq \mathbb{Q}^{t \times t}$, we then consider the decidability of computing the maximal spectral radius of any matrix in the set $X = \{M^{j_1}_1 M^{j_2}_2 \cdot M^{j_k}_k \vert j_1, j_2,\ldots, j_k \geq 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).
Keywords: Probabilistic finite automata, Bounded languages, Formal power series, Undecidability, Hilbert's tenth problem
