2003 • Journal Article
Undecidable problems for probabilistic automata of fixed dimension
Authors:
Blondel, Vincent ,
Canterini, V
Published in:
Theory of Computing Systems : an international journal
Volume: 36 • Number: 3 • Pages: 231-245
We prove that several problems associated with probabilistic finite automata are undecidable for automata whose number of input letters and number of states are fixed. As a corollary of one of our results we prove that the problem of determining if the set of all products of two 47 x 47 matrices with nonnegative rational entries is bounded is undecidable.