Logic and bounded-width rational languages of posets over countable scattered linear orderings
This paper has been published in Lecture Notes in Computer Sciences, Vol. 5407, 2009, and the copyright is owned by Springer.
In this paper we consider languages of labelled N-free posets over countable and scattered linear orderings. We prove that a language of such posets is series-rational if and only if it is recognizable by a finite depth-nilpotent algebra if and only if it is bounded-width and monadic second-order definable. This extends previous results on languages of labelled N-free finite and ω-posets and on languages of labelled countable and scattered linear orderings.