2023/12/22 by Sergio Abriola, Abriola, Sergio, Simon Halfon +9
Computer Science · Mathematics · #06 #Advanced Algebra and Logic #Discrete Mathematics (cs.DM) #F.2.2 #FOS: Computer and information sciences #G.2 #Logic in Computer Science (cs.LO) #Rings, Modules, and Algebras #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2312.14587
openalex publication_date 2023/12/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.