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 metadatas

https://hal.inria.fr/inria-00098439
Contributor : Publications Loria <>
Submitted on : Monday, September 25, 2006 - 5:01:29 PM
Last modification on : Friday, April 12, 2019 - 10:18:09 AM

Identifiers

  • HAL Id : inria-00098439, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

142