• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Decision Problems for Probabilistic Finite Automata on Bounded Languages

Paul C. Bell, Vesa Halava, Mika Hirvensalo, Decision Problems for Probabilistic Finite Automata on Bounded Languages. Fundamenta Informaticae 123(1), 1–14, 2013.

http://dx.doi.org/10.3233/FI-2013-797

Abstract:

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).

BibTeX entry:

@ARTICLE{uconv1571472,
  title = {Decision Problems for Probabilistic Finite Automata on Bounded Languages},
  author = {Bell, Paul C. and Halava, Vesa and Hirvensalo, Mika},
  journal = {Fundamenta Informaticae},
  volume = {123},
  number = {1},
  publisher = {IOS PRESS},
  pages = {1–14},
  year = {2013},
  keywords = {Probabilistic finite automata;Bounded languages;Formal power series;Undecidability;Hilbert's tenth problem},
  ISSN = {0169-2968},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Publication Forum rating of this publication: level 1

Edit publication