Showing cs.LOShow all
3 papers · 1 filter
cs.LO2023
Measuring well quasi-ordered finitary powersets
Sergio Abriola, Simon Halfon, Aliaume Lopez +3
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…
cs.LO2023
Ordinal measures of the set of finite multisets
Isa Vialard
Well-partial orders, and the ordinal invariants used to measure them, are relevant in set theory, program verification, proof theory and many other areas of computer science and ma…
cs.LO2022
On the cartesian product of well-orderings
Isa Vialard
The width of a well partial ordering (wpo) is the ordinal rank of the set of its antichains ordered by inclusion. We compute the width of wpos obtained as cartesian products of fin…