Bruno Courcelle - Order-theoretic trees: monadic second-order descriptions and regularity

fi:8690 - Fundamenta Informaticae, October 21, 2022, Volume 186, Issues 1-4: Trakhtenbrot's centenary
Order-theoretic trees: monadic second-order descriptions and regularityArticle

Authors: 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.


    Volume: Volume 186, Issues 1-4: Trakhtenbrot's centenary
    Published on: October 21, 2022
    Accepted on: June 21, 2022
    Submitted on: November 9, 2021
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Discrete Mathematics

    Consultation statistics

    This page has been seen 112 times.
    This article's PDF has been downloaded 73 times.