Abstract
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 × 47 matrices with nonnegative rational entries is bounded is undecidable.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Blondel, Canterini Undecidable Problems for Probabilistic Automata of Fixed Dimension . Theory Comput. Systems 36, 231–245 (2003). https://doi.org/10.1007/s00224-003-1061-2
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-003-1061-2