We give a uniform proof for the recognizability of sets of finite words, traces, or N-free pomsets that are axiomatized in monadic second order logic. This proof method uses Shelah's composition theorem for bounded theories. Using this method, we can also show that elementarily axiomatizable sets are aperiodic. In the second part of the paper, it is shown that width-bounded and aperiodic sets of N-free pomsets are elementarily axiomatizable.
展开▼
