Rabin tree automata and finite monoids

AbstractWe incorporate finite monoids into the theory of recognizability of ω-tree languages by Rabin automata. We define a free monoid of ω-trees and associate with each ω-tree language L a language L̂ of infinite words over this monoid. Using this correspondence we introduce strong monoid recognizability of ω-tree languages (strengthening the standard notion for infinite words) and show it to be equivalent to Rabin recognizability. We also show that there exists an ω-tree language L which is not Rabin recognizable, but its associated language L̂ is monoid recognizable (in the standard sense). Our positive result opens the theory of varieties of ω-tree languages, in extension of the ones for finite and infinite words and finite trees