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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 1998, 201 (1-2), pp.63-84
Liste complète des métadonnées

https://hal.inria.fr/inria-00098439
Contributeur : Publications Loria <>
Soumis le : lundi 25 septembre 2006 - 17:01:29
Dernière modification le : jeudi 17 mai 2018 - 12:52:03

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

75