{"docId":8964,"paperId":8690,"url":"https:\/\/fi.episciences.org\/8690","doi":"","journalName":"Fundamenta Informaticae","issn":"0169-2968","eissn":"1875-8681","volume":[{"vid":599,"name":"Volume 186, Issues 1-4: Trakhtenbrot's centenary"}],"section":[],"repositoryName":"arXiv","repositoryIdentifier":"2111.04083","repositoryVersion":4,"repositoryLink":"https:\/\/arxiv.org\/abs\/2111.04083v4","dateSubmitted":"2021-11-09 08:56:47","dateAccepted":"2022-06-21 22:08:20","datePublished":"2022-10-21 22:02:15","titles":["Order-theoretic trees: monadic second-order descriptions and regularity"],"authors":["Courcelle, Bruno"],"abstracts":["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"],"keywords":["Computer Science - Logic in Computer Science","Computer Science - Discrete Mathematics"]}