Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

2 2008

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Partial Conway and Iteration Semirings

Bloom S.L., Ésik Z., Kuich W.

Fundamenta Informaticae

2008

Vol. 86, nr 1-2

19-40

A Conway semiring is a semiring S equipped with a unary operation *: S →S, always called 'star', satisfying the sum star and product star identities. It is known that these identities imply a Kleene type theorem. Some computationally important semirings, such as N or N^{rat}((σ)) of rational power series of words on σ with coefficients in N, cannot have a total star operation satisfying the Conway identities. We introduce here partial Conway semirings, which are semirings S which have a star operation defined only on an ideal of S; when the arguments are appropriate, the operation satisfies the above identities. We develop the general theory of partial Conway semirings and prove a Kleene theorem for this generalization.

Multi-Valued MSO Logics Over Words and Trees

Droste M., Kuich W., Rahonis G.

Fundamenta Informaticae

2008

Vol. 84, nr 3-4

305-327

We introduce multi-valued Büchi and Muller automata over distributive lattices and a multi-valued MSO logic for infinite words. For this logic, we prove the expressive equivalence of w-recognizable and MSO-definable infinitary formal power series over distributive lattices with negation function. Then we consider multi-valued Muller tree automata and a multi-valued MSO logic for trees over distributive lattices. For this logic, we establish a version of Rabin's theorem for infinitary tree series.