Series-parallel languages on scattered and countable posets
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.
scientific article; zbMATH DE number 5886216
scientific article