Gespeichert in:
| Hauptverfasser: | , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2312.14587 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916328666824704 |
|---|---|
| author | Abriola, Sergio Halfon, Simon Lopez, Aliaume Schmitz, Sylvain Schnoebelen, Philippe Vialard, Isa |
| author_facet | Abriola, Sergio Halfon, Simon Lopez, Aliaume Schmitz, Sylvain Schnoebelen, Philippe Vialard, Isa |
| contents | The complexity of a well-quasi-order (wqo) can be measured through three ordinal invariants: the width as a measure of antichains, height as a measure of chains, and maximal order type as a measure of bad sequences.
We study these ordinal invariants for the finitary powerset, i.e., the collection Pf(A) of finite subsets of a wqo A ordered with the Hoare embedding relation. We show that the invariants of Pf(A) cannot be expressed as a function of the invariants of A, and provide tight upper and lower bounds for them.
We then focus on a family of well-behaved wqos, for which these invariants can be computed compositionally, using a newly defined ordinal invariant called the approximate maximal order type. This family is built from multiplicatively indecomposable ordinals, using classical operations such as disjoint unions, products, finite words, finite multisets, and the finitary powerset construction. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_14587 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Measuring well quasi-ordered finitary powersets Abriola, Sergio Halfon, Simon Lopez, Aliaume Schmitz, Sylvain Schnoebelen, Philippe Vialard, Isa Logic in Computer Science Discrete Mathematics 06 F.2.2; G.2 The complexity of a well-quasi-order (wqo) can be measured through three ordinal invariants: the width as a measure of antichains, height as a measure of chains, and maximal order type as a measure of bad sequences. We study these ordinal invariants for the finitary powerset, i.e., the collection Pf(A) of finite subsets of a wqo A ordered with the Hoare embedding relation. We show that the invariants of Pf(A) cannot be expressed as a function of the invariants of A, and provide tight upper and lower bounds for them. We then focus on a family of well-behaved wqos, for which these invariants can be computed compositionally, using a newly defined ordinal invariant called the approximate maximal order type. This family is built from multiplicatively indecomposable ordinals, using classical operations such as disjoint unions, products, finite words, finite multisets, and the finitary powerset construction. |
| title | Measuring well quasi-ordered finitary powersets |
| topic | Logic in Computer Science Discrete Mathematics 06 F.2.2; G.2 |
| url | https://arxiv.org/abs/2312.14587 |