On ordinal invariants in well quasi orders and finite antichain orders

Dzamonja, Mirna, Schmitz, Sylvain and Schnoebelen, Philippe (2018) On ordinal invariants in well quasi orders and finite antichain orders. In: Well quasi-orders in computation, logic, language and reasoning. Trends in Logic . Springer. (In Press)

[img] PDF (Chapter) - Accepted Version
Restricted to Repository staff only until 31 December 2099.

Download (255kB) | Request a copy


We investigate the ordinal invariants height, length, and width of well quasi orders (WQO), with particular emphasis on width, an invariant of interest for the larger class of orders with finite antichain condition (FAC). We show that the width in the class of FAC orders is completely determined by the width in the class of WQOs, in the sense that if we know how to calculate the width of any WQO then we have a procedure to calculate the width of any given FAC order. We show how the width of WQO orders obtained via some classical constructions can sometimes be computed in a compositional way. In particular this allows proving that every or- dinal α can be obtained as the width of some WQO poset. One of the difficult ques- tions is to give a complete formula for the width of Cartesian products of WQOs. Even the width of the product of two ordinals is only known through a complex re- cursive formula. Although we have not given a complete answer to this question we have advanced the state of knowledge by considering some more complex special cases and in particular by calculating the width of certain products containing three factors. In the course of writing the paper we have discovered that some of the rele- vant literature was written on cross-purposes and some of the notions re-discovered several times, hence the pun in the title (see Kruskal (1972)). Therefore we also use the occasion to give a unified presentation of the known results.

Item Type: Book Section
Uncontrolled Keywords: wqo,width,ordinal invariants
Faculty \ School: Faculty of Science > School of Mathematics
Depositing User: LivePure Connector
Date Deposited: 15 Nov 2018 16:30
Last Modified: 03 Apr 2021 01:37
URI: https://ueaeprints.uea.ac.uk/id/eprint/68922

Actions (login required)

View Item View Item