Measuring well quasi-orders

26^th June 2023, 10:00
Isa Vialard

Abstract

Well-structured transition systems (WSTS) are tansition
systems whose set of configurations is a well-quasi order (WQO) and
whose transitions respect this order. Therefore, complexity of problems
on WSTSs can often be linked to the measures of the underlying wqo,
called the ordinal invariants.

The ordinal invariants, i.e., maximal order type, height, and width,
are measures of a wqo based on the ordinal rank of the trees of its bad
sequences, strictly decreasing sequences, and antichain sequences,
respectively. Complex wqos are often built from simpler wqos through
basic constructions such as disjoint sum, direct sum, cartesian
product, and higher-order constructions like powerset or sequences. One
main challenge is to compute the ordinal invariants of such wqos
compositionally.

This talk will focus on the width of the cartesian product.