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: formal power series

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 Kleene-Schützenberger Theorem for Trace Series over Bounded Lattices

Huschenbett M.

Fundamenta Informaticae

2011

Vol. 112, nr 2/3

171-191

We study weighted trace automata with weights in strong bimonoids. Traces form a generalization of words that allow to model concurrency; strong bimonoids are algebraic structures that can be regarded as "semirings without distributivity". A very important example for the latter are bounded lattices, especially non-distributive ones. We show that if both operations of the bimonoid are locally finite, then the classes of recognizable and mc-rational trace series coincide and, in general, are properly contained in the class of c-rational series. Moreover, if, in addition, in the bimonoid the addition is idempotent and the multiplication is commutative, then all three classes coincide.

The equivalence problem of DOL and DFOL power series

Honkala J.

Fundamenta Informaticae

1999

Vol. 38, Nr 1,2

201-208

We show that it is decidable whether or not a given D0L power series and a given DF0L power series over a computable field are equal. This generalizes to power series the result of Ruohonen stating that DF0L-D0L language equivalence is decidable.