User menu

Accès à distance ? S'identifier sur le proxy UCLouvain

Undecidable problems for probabilistic automata of fixed dimension

Primary tabs

Blondel, Vincent [UCL] Canterini, V

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.

Document type Article de périodique (Journal article) – Article de recherche
Access type Accès restreint
Publication date 2003
Language Anglais
Journal information "Theory of Computing Systems : an international journal" - Vol. 36, no. 3, p. 231-245 (2003)
Peer reviewed yes
Publisher Springer-verlag (New York)
issn 1432-4350
e-issn 1433-0490
Publication status Publié
Affiliation UCL
Links
Bibliographic reference Blondel, Vincent ; Canterini, V. Undecidable problems for probabilistic automata of fixed dimension. In: Theory of Computing Systems : an international journal, Vol. 36, no. 3, p. 231-245 (2003)
Permanent URL http://hdl.handle.net/2078.1/41073