Showing 2023Show 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.FL2023
On the piecewise complexity of words and periodic words
M. Praveen, Philippe Schnoebelen, Isa Vialard +1
The piecewise complexity of a word is the minimal length of subwords needed to exactly characterise . Its piecewise minimality index is the smallest length suc…
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…