Abstract
Landmark results of Myhill, Büchi, Elgott,Trakhtenbrot, Schützenberger, McNaughton and Papert state that for languages of finite words, (1) being definable in monadic second-order logic is equivalent to being recognizable by a finite monoid, and (2) being definable in first-order logic is equivalent to being recognizable by an aperiodic finite monoid.
Bojanzyk initiated the study of orbit finite nominal monoids for recognizing languages of words over an orbit finite nominal alphabet. He also gave partial extensions of the above results (1) and (2). In this talk, I will explain how perfect extensions of (1) and (2) can be achieved. This requires the use of proper definitions of the logic formalisms, making use of -- what we call -- rigidly guarded equality tests.
The results are joint work with Clemens Ley and Gabriele Puppis.