10.46298/fi-2022-8690
https://fi.episciences.org/8690
Courcelle, Bruno
Bruno
Courcelle
Order-theoretic trees: monadic second-order descriptions and regularity
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.
Comment: 32 pages, 6 figures
episciences.org
Computer Science - Logic in Computer Science
Computer Science - Discrete Mathematics
Attribution 4.0 International (CC BY 4.0)
2022-06-21
2022-10-21
2022-10-21
eng
journal article
arXiv:2111.04083
10.48550/arXiv.2111.04083
1875-8681
https://fi.episciences.org/8690/pdf
VoR
application/pdf
Fundamenta Informaticae
Volume 186, Issues 1-4: Trakhtenbrot's centenary
Researchers
Students