On describing trees and quasi-trees from their leaves
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913718018768896 |
|---|---|
| author | Courcelle, Bruno |
| author_facet | Courcelle, Bruno |
| contents | 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. 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 characterizations by universal first-order sentences. Furthermore, we consider cases where O-trees and quasi-trees can be reconstructed from their leaves by CMSO-transductions. These transductions are transformations of relational structures defined by monadic second-order (MSO) formulas. The letter "C" for 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, and to modular decomposition and to other canonical graph decompositions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_02672 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On describing trees and quasi-trees from their leaves Courcelle, Bruno Logic in Computer Science 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. 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 characterizations by universal first-order sentences. Furthermore, we consider cases where O-trees and quasi-trees can be reconstructed from their leaves by CMSO-transductions. These transductions are transformations of relational structures defined by monadic second-order (MSO) formulas. The letter "C" for 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, and to modular decomposition and to other canonical graph decompositions. |
| title | On describing trees and quasi-trees from their leaves |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2503.02672 |