On describing trees and quasi-trees from their leaves
RAIRO - Theoretical Informatics and Applications · 2026 · 60 · 13
DOI: 10.1051/ita/2026009 ↗Kurz gefasst
Fachartikel in der Zeitschrift RAIRO - Theoretical Informatics and Applications, online erschienen am 03.04.2026. Verfasst von Bruno Courcelle. Die Arbeit nennt 26 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).
Abstract (Originalsprache)
Generalized trees, we call them O-trees, are defined as hierarchical partial orders, i.e., such that the elements larger than any one are linearly ordered. This partial order generalizes the ancestor relation of a rooted tree. As for rooted trees, the root of an O-tree is its unique maximal element if there is such; however, an O-tree may have no root. Quasi-trees are, roughly speaking, undirected O-trees. For O-trees and quasi-trees, we define relational structures on their leaves that characterize them up to isomorphism. These structures have axiomatizations by universal first-order sentences. Our main purpose is to reconstruct O-trees and quasi-trees from their leaves and relevant relations on leaves, by logically defined transformations, called transductions. Monadic second-order (MSO) transductions are defined by monadic second-order (MSO) formulas. We use actually CMSO transductions where the letter “C”, meaning counting, refers to the use of set predicates that count cardinalities of finite sets modulo fixed integers. O-trees and quasi-trees make it possible to define respectively, the modular decomposition and the rank-width of a countable graph. Their constructions from their leaves by transductions of different types apply to rank-decompositions, to modular decomposition and to other canonical graph decompositions.
Zitieren
APA
Courcelle, B. (2026). On describing trees and quasi-trees from their leaves. RAIRO - Theoretical Informatics and Applications, 60, 13. https://doi.org/10.1051/ita/2026009
Vancouver
Courcelle B. On describing trees and quasi-trees from their leaves. RAIRO - Theoretical Informatics and Applications. 2026;60:13. doi:10.1051/ita/2026009
BibTeX
@article{Courcelle2026,
author = {Courcelle, Bruno},
title = {On describing trees and quasi-trees from their leaves},
journal = {RAIRO - Theoretical Informatics and Applications},
year = {2026},
volume = {60},
pages = {13},
doi = {10.1051/ita/2026009}
}
EUVIMED