On classes of meet automata

Sala 0.04 (DMP - FCUP)
Monday, 26 November, 2007 - 16:00

Part 1. Eilenberg's variety theorem gives a bijective correspondence between varieties of languages and varieties of finite semigroups. The second author gave a similar relation between conjunctive varieties of languages and varieties of semiring homomorphisms. In this paper, we add a third component to this result by considering varieties of meet automata. We consider three significant classes of languages, two of them consisting of reversible languages. We present conditions on meet automata and identities for semiring homomorphisms for their characterization.

Part 2. In a recent paper we factorized the most general Eilenberg-type theorem through varieties of meet automata. The only syntactic presentation of such classes was the usage of pseudoidentities on transformation semirings of such automata. Here we present a new type of conditions suitable for identification of classes of meet automata. We found rich hierarchies of such classes, many of them related to the reversible automata.

Speaker: 

Ondrej Klima and Libor Polak (Dept. Mathematics, Masaryk University, Brno, Czech Republic)