Skip to Main content Skip to Navigation
Journal articles

Ordinal recursive bounds for Higman's theorem

Adam Cichon 1 Elias Tahhan-Bittar
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : This paper concerns Higman's theorem for stringsgenerated over a finite alphabet. We give a constructiveproof of this theorem and we construct and characterisefunctions which bound the lengths of bad sequences. These bounding functions are described by ordinal-recursive definitions and their characterisation is achievedwith reference to Hardy hierarchies of number-theoretic functions.
Document type :
Journal articles
Complete list of metadata
Contributor : Publications Loria Connect in order to contact the contributor
Submitted on : Monday, September 25, 2006 - 5:01:29 PM
Last modification on : Friday, February 4, 2022 - 3:33:21 AM


  • HAL Id : inria-00098439, version 1



Adam Cichon, Elias Tahhan-Bittar. Ordinal recursive bounds for Higman's theorem. Theoretical Computer Science, Elsevier, 1998, 201 (1-2), pp.63-84. ⟨inria-00098439⟩



Record views