Algebraic and logical descriptions of generalized trees
Quasi-trees generalize trees in that the unique "path" between two nodes may be infinite and have any countable order type. They are used to define the rank-width of a countable graph in such a way that it is equal to the least upper-bound of the rank-widths of its finite induced subgraphs...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2017-07-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/2050/pdf |
| Summary: | Quasi-trees generalize trees in that the unique "path" between two nodes may
be infinite and have any countable order type. They are used to define the
rank-width of a countable graph in such a way that it is equal to the least
upper-bound of the rank-widths of its finite induced subgraphs. Join-trees are
the corresponding directed trees. They are useful to define the modular
decomposition of a countable graph. We also consider ordered join-trees, that
generalize rooted trees equipped with a linear order on the set of sons of each
node. We define algebras with finitely many operations that generate (via
infinite terms) these generalized trees. 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. These results use and
generalize a similar result by W. Thomas for countable linear orders. |
|---|---|
| ISSN: | 1860-5974 |