Recognizable Sets of N-Free Pomsets Are Monadically Axiomatizable

摘要

It is shown that any recognizable set of finite N-free pomsets is axiom-atizable in counting monadic second order logic. Differently from similar results by Courcelle, Kabanets, and Lapoire, we do not use MSO-transductions (i.e., one-dimensional interpretations), but two-dimensional interpretations of a generating tree in an N-free pomset. Then we have to deal with the new problem that set-quantifications over the generating tree are translated into quantifications over binary relations in the N-free pomset. This is solved by an adaptation of a result by Potthoff & Thomas on monadic antichain logic.