Towards a language theory for infinite N-free pomsets

AbstractN-free or series–parallel pomsets are a model for the behavior of modularly constructed concurrent systems. The investigation of recognizable languages of finite N-free pomsets was initiated by Lodaya and Weil who extended the theorems by Kleene and by Myhill and Nerode on recognizable word languages to this setting. In this paper, we extend Lodaya and Weil's results in several aspects: (a) We consider the relation of recognizable sets to monadic second order logic in order to generalize Büchi's theorem. (b) We prove our results (and extensions of results by Lodaya and Weil) for sets of infinite N-free pomsets. And (c), we investigate first-order axiomatizable, starfree, and aperiodic sets of infinite N-free pomsets and prove results in the spirit of McNaughton and Papert's and Schützenberger's theorems for finite words