A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Decision Problems for Probabilistic Finite Automata on Bounded Languages
Tekijät: Bell PC, Halava V, Hirvensalo M
Kustantaja: IOS PRESS
Julkaisuvuosi: 2013
Journal: Fundamenta Informaticae
Tietokannassa oleva lehden nimi: FUNDAMENTA INFORMATICAE
Lehden akronyymi: FUND INFORM
Numero sarjassa: 1
Vuosikerta: 123
Numero: 1
Aloitussivu: 1
Lopetussivu: 14
Sivujen määrä: 14
ISSN: 0169-2968
DOI: https://doi.org/10.3233/FI-2013-797
Tiivistelmä
For a finite set of matrices {M-1, M-2, ... , M-k} subset of Q(txt), we then consider the decidability of computing the maximal spectral radius of any matrix in the set X = {M-1(j1) M-2(j2) ... M-k(jk)vertical bar j(1), j(2), ... , j(k) >= 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).
For a finite set of matrices {M-1, M-2, ... , M-k} subset of Q(txt), we then consider the decidability of computing the maximal spectral radius of any matrix in the set X = {M-1(j1) M-2(j2) ... M-k(jk)vertical bar j(1), j(2), ... , j(k) >= 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).
Turun yliopiston Tutkimustietojärjestelmän portaali