Ordinal recursive bounds for Higman's theorem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Theoretical Computer Science Année : 1998

Ordinal recursive bounds for Higman's theorem

Elias Tahhan-Bittar
  • Fonction : Auteur

Résumé

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.

Domaines

Autre [cs.OH]

Dates et versions

inria-00098439 , version 1 (25-09-2006)

Identifiants

Citer

Adam Cichon, Elias Tahhan-Bittar. Ordinal recursive bounds for Higman's theorem. Theoretical Computer Science, 1998, 201 (1-2), pp.63-84. ⟨10.1016/S0304-3975(97)00009-1⟩. ⟨inria-00098439⟩
103 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More