Part 1. Eilenberg's variety theorem gives a bijective correspondence between varieties of languages
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.
Date and Venue
Start Date
Venue
Sala 0.04 (DMP - FCUP)
Speaker
Ondrej Klima and Libor Polak (Dept. Mathematics, Masaryk University, Brno, Czech Republic)
Area
Semigroups, Automata and Languages