Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Hilbert's tenth problem

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

A Note on Two-pebble Automata Over Infinite Alphabets

Kaminski M., Tan T.

Fundamenta Informaticae

2010

Vol. 98, nr 4

379-390

It is shown that the emptiness problemfor two-pebble automata languages is undecidable and that two-pebble automata are weaker than three-pebble automata.

On the existence of a new family of Diophantine equations for Omega

Ord T., Kieu T.D.

Fundamenta Informaticae

2003

Vol. 56, nr 3

273-284

We show how to determine the k-th bit of Chaitin's algorithmically random real number W by solving k instances of the halting problem. From this we then reduce the problem of determining the k-th bit of W to determining whether a certain Diophantine equation with two parameters, k and N, has solutions for an odd or an even number of values of N. We also demonstrate two further examples of W in number theory: an exponential Diophantine equation with a parameter k which has an odd number of solutions iff the k-th bit of W is 1, and a polynomial of positive integer variables and a parameter k that takes on an odd number of positive values iff the k-th bit of W is 1.