Systolic Tree omega-Languages
Angelo Monti, Adriano Peron · 2007
. The class of !-languages recognized by systolic tree automata is introduced. That class extends the class of Buchi !-languages and is closed under boolean operations. The emptiness problem for systolic tree automata on infinite sequences is decidable. A characterization of systolic tree !-languages in terms of a (suitable) concatenation of (finitary) systolic tree languages is also provided. 1 Introduction The subject of automata accepting infinite sequences was established in the sixties by Buchi, McNaughton and Rabin (for a survey, see [1]). Their work opened connections between automata theory and fields of logic and set-theoretic topology. The early papers were motivated by decision problems in mathematical logic (e.g., see [2]). One motivation for considering automata on infinite sequences (Buchi automata) was the analysis of the "sequential calculus", a system of monadic second-order logic for the formalization of properties of sequences. Buchi showed that any condition on seq...