A logical characterization of systolic languages

In this paper we study, in the framework of mathematical logic, ℒ(SBTA) i.e. the class of languages accepted by Systolic Binary Tree Automata. We set a correspondence (in the style of Büchi Theorem for regular languages) between ℒ(SBTA) and MSO[Sig], i.e. a decidable Monadic Second Order logic over a suitable infinite signature Sig. We also introduce a natural subclass of ℒ(SBTA) which still properly contains the class of regular languages and which is proved to be characterized by Monadic Second Order logic over a finite signature Sig' ⊂ Sig. Finally, in the style of McNaughton Theorem for star free regular languages, we introduce an expression language which precisely denotes the class of languages defined by the first order fragment of MSO[Sig'].