eng
episciences.org
Fundamenta Informaticae
0169-2968
1875-8681
2022-10-21
Volume 186, Issues 1-4:...
10.46298/fi-2022-8690
8690
journal article
Order-theoretic trees: monadic second-order descriptions and regularity
Bruno Courcelle
An order-theoretic forest is a countable partial order such that the set of
elements larger than any element is linearly ordered. It is an order-theoretic
tree if any two elements have an upper-bound. The order type of a branch can be
any countable linear order. Such generalized infinite trees yield convenient
definitions of the rank-width and the modular decomposition of countable
graphs.
We define an algebra based on only four operations that generate up to
isomorphism and via infinite terms these order-theoretic trees and forests. We
prove that the associated regular objects, those defined by regular terms, are
exactly the ones that are the unique models of monadic second-order sentences.
https://fi.episciences.org/8690/pdf
Computer Science - Logic in Computer Science
Computer Science - Discrete Mathematics