Ackermannian and Primitive-Recursive Bounds with Dickson's Lemma
Diego Figueira, Santiago Figueira, Sylvain Schmitz, Philippe Schnoebelen · 2011
Dickson's Lemma is a simple yet powerful tool widely used in decidability proofs, especially when dealing with counters or related data structures in algorithmics, verification and model-checking, constraint solving, logic, etc. While Dickson's Lemma is well-known, most computer scientists are not aware of the complexity upper bounds that are entailed by its use. This is mainly because, on this issue, the existing literature is not very accessible. We propose a new analysis of the length of bad sequences over (Nk,≤), improving on earlier results and providing upper bounds that are essentially tight. This analysis is complemented by a ``user guide'' explaining through practical examples how to easily derive complexity upper bounds from Dickson's Lemma.