Decision Problems for Probabilistic Finite Automata on Bounded Languages
Paul C. Bell, Vesa Halava, Mika Hirvensalo · Fundamenta Informaticae · 2013
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.