The Expressiveness of Recognizability by Orbite Finite Nominal Monoids
summary
Claim: monadic second-order logic with rigid guards exactly captures languages recognisable by orbit-finite nominal monoids, and the first-order fragment corresponds to the aperiodic sub-class. Construction uses nominal sets, an effective syntactic enforcement of rigidity, a projectability property to control MSO projection (power-set) and a detailed analysis of Green’s relations to build MSO formulas from monoid elements. Result restores many algebraic/logical equivalences lost in naïve register models and yields effective translations both ways.
AI-written summary · about