Fundamenta Informaticae · 2008 · 36 citations · 20 references
ComputingComputer ScienceMathematicsFormal MethodsSet TheoryTheory Of ComputationAutomata TheoryBoolean AlgebraFinite AutomataFormal Language FoundationsModel TheoryPredicate LogicAutomata On Infinite WordsDistributive LatticesFormal Power SeriesTree Automata
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.
20
On the definition of a family of automata
M. P. Schützenberger · Information and Control · 1961 · 645 citations