A Note on the Logical Definability of Rational Trace Languages
Christian Choffrut · Fundamenta Informaticae · 2012
The regular languages in the free monoid generated by a finite alphabet A are exactly the languages that are the models of some sentence of the second-order monadic logic of one successor and a unary predicate for each letter. For trace monoids the n