Affiliations: Institute of Computer Science, Leipzig University
D-04009 Leipzig, Germany. E-mail: [email protected] | Institut für Diskrete Mathematik und Geometrie,
Technische Universität Wien Wiedner Hauptstraße 8-10, A-1040 Wien,
Austria. E-mail: [email protected] | Department of Mathematics, Aristotle University of
Thessaloniki 54124 Thessaloniki, Greece. E-mail: [email protected]
Note: [] Address for correspondence: Department of Mathematics, Aristotle
University of Thessaloniki, 54124 Thessaloniki, Greece
Abstract: 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 ω-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.
Keywords: Distributive lattices, multi-valued automata over infinite words and trees, infinitary formal power series, multi-valued MSO logic
