On describing trees and quasi-trees from their leaves

Labri, Bordeaux University, 351 Cours de la Libération, 33400 Talence, France

^* Corresponding author: This email address is being protected from spambots. You need JavaScript enabled to view it.

Received: 5 April 2025
Accepted: 16 February 2026

Abstract

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.