On varieties of meet automata

Warning

This publication doesn't include Faculty of Economics and Administration. It includes Faculty of Science. Official publication website can be found on muni.cz.

Authors	KLÍMA Ondřej POLÁK Libor
Year of publication	2008
Type	Article in Periodical
Magazine / Source	Theoretical Computer Science
MU Faculty or unit	Faculty of Science
Citation
Field	General mathematics
Keywords	varieties of languages; varieties of meet automata; varieties of semiring homomorphisms
Description	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.
Related projects:	Institute for Theoretical Computer Science Mathematical structures and their physical applications Algebraic Methods in Automata and Formal Language Theory