Wyniki wyszukiwania - BazTech

1

The Supports of Weighted Unranked Tree Automata

Droste M., Heusel D.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

37--58

EN

We investigate the supports of weighted unranked tree automata. Our main result states that the support of a weighted unranked tree automaton over a zero-sum free, commutative strong bimonoid is recognizable. For this, we use methods of Kirsten (DLT 2009), in particular, his construction of finite automata recognizing the supports of weighted automata on strings over zero-sum free, commutative semirings. We also get an effective construction of a finite tree automaton recognizing the support of a given weighted unranked tree automaton for zero-sum free, commutative strong bimonoids where Kirsten’s zero generation problem is decidable. In addition, we give a translation of nested weighted automata into weighted unranked tree automata for arbitrary commutative strong bimonoids. As a consequence,we derive analogous results for the supports of nested weighted automata. Finally, we give similar results for the supports of weighted pushdown automata.

2

The uncountable cofinality of the automorphism group of the countable universal distributive lattice

Droste M., Truss J. K.

Demonstratio Mathematica

|

2011

|

Vol. 44, nr 3

473-479

EN

We show that the automorphism group of the countable universal distributive lattice has strong uncountable cofinality, and we adapt the method to deduce the strong uncountable cofinality of the automorphism group of the countable universal generalized boolean algebra.

3

Multi-Valued MSO Logics Over Words and Trees

Droste M., Kuich W., Rahonis G.

Fundamenta Informaticae

|

2008

|

Vol. 84, nr 3-4

305-327

EN

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.

4

Observations on the Smoothness Properties of Real Functions Computed by Weighted Finite Automata

Droste M., Kari J., Steinby P.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

99-106

EN

We continue investigations of weighted finite automata (WFA) as devices to compute real functions. Based on eigenvalues of the transition matrices of automata we provide a simple necessary condition for continuity and smoothness properties of the functions they compute. Using this condition we show that polynomials are the only smooth functions computed by WFA and that any WFA computing a polynomial of degree k must have at least k+1 states.