Series-parallel languages on scattered and countable posets
type: Item
instance of: scholarly article
title: Series-parallel languages on scattered and countable posets
zbMATH Open document ID: 1238.68072
author: Nicolas Bedon
author: Chloé Rispal
published in: Theoretical Computer Science
publication date: 2011-05-10T00:00:00Z
review text: 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.
reviewed by: Galina Jirásková
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 06A07
zbMATH DE Number: 5886216
zbMATH Keywords: \(N\)-free posets
zbMATH Keywords: linear orderings
zbMATH Keywords: sp-rational languages
zbMATH Keywords: automata
MaRDI profile type: Publication
full work available at URL: j.tcs.2011.01.016
OpenAlex ID: W1991307158
cites work: Logic and Bounded-Width Rational Languages of Posets over Countable Scattered Linear Orderings
cites work: Series-Parallel Languages on Scattered and Countable Posets
cites work: A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS
cites work: Q4412103
cites work: Weak Second‐Order Arithmetic and Finite Automata
cites work: Q4737909
cites work: Q2754184
cites work: Towards a language theory for infinite N-free pomsets.
cites work: Q4381401
cites work: Series-parallel languages and the bounded-width property
cites work: Rationality in algebras with a series operation
cites work: Decidability of Second-Order Theories and Automata on Infinite Trees
cites work: $ℵ_0$-categoricity of linear orderings
cites work: The Recognition of Series Parallel Digraphs
DOI: 10.1016/J.TCS.2011.01.016
description: scientific article; zbMATH DE number 5886216