Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Decision Problems for Probabilistic Finite Automata on Bounded Languages

Bell P. C., Halava V., Hirvensalo M.

Fundamenta Informaticae

2013

Vol. 123, nr 1

1--14

We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert’s tenth problem. We then consider the set of so called “F-Problems” (emptiness, infiniteness, containment, disjointness, universe and equivalence) and show that they are also undecidable for bounded (non-)strict cut-point languages on probabilistic finite automata. For a finite set of matrices { M1 , M2 , . . . , Mk }⊆ Q txt , we then consider the decidability of computing the maximal spectral radius of any matrix in the set X = { Mj11 Mj22··· Mjkk|j1, j2, . . . , jk≥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).

Recurrent Construction of MacWilliams and Chebyshev Matrices

Gogin N., Hirvensalo M.

Fundamenta Informaticae

2012

Vol. 116, nr 1-4

93-110

We give two recursive expressions for both MacWilliams and Chebyshev matrices. The expressions give rise to simple recursive algorithms for constructing the matrices. In order to derive the second recursion for the Chebyshev matrices we find out the Krawtchouk coefficients of the discrete Chebyshev polynomials, a task interesting on its own.