Series-parallel languages on scattered and countable posets (Q533879)

The paper investigates the recognition of languages of countable labelled posets by finite automata. The first result shows that the class of scattered and countable \(N\)-free posets without infinite antichains corresponds precisely to the smallest class of posets obtained from the empty set and the singleton and closed under finite union and sum indexed by countable scattered linear orderings. Next, the authors define rational expressions and finite automata for languages of labelled countable scattered \(N\)-free posets without infinite antichains and show that both formalisms have the same expressive power.