| Résume | Well-quasi-orders are employed in numerous fields as a mathematical toolbox for proving finiteness statements. In particular, they guarantee the termination of algorithms that construct—either explicitly or implicitly—bad sequences, antichains, or descending chains of downwards-closed sets.
In this talk, I will present an `instrumentation' framework that allows to derive upper bounds on the lengths of bad sequences (and if time allows, antichains and descending chains), and thus on the complexity of the corresponding algorithms.
The talk will be based on material that can be found in http://tel.archives-ouvertes.fr/tel-01663266, https://hal.archives-ouvertes.fr/hal-02020728, https://arxiv.org/abs/2310.02847, and the references therein. |
