Skip to Main content Skip to Navigation

Constructions d'ordres, analyse de la complexité

Abstract : Our concern in the thesis is in the study of orders, through the analysis of complexity within rewriting, but also through the construction of monotonous [lambda]-calculi within the framework of ordinal terms, and subrecursivc hierarchies. We show how to extract some knowledge in terms of complexity from the proof of termination in rewriting theory. This allows us to establish some hierarchies of caracterisation of complexity classes in terms of rewriting. So, one has an a priori complexity measure of functions with respect to their proof of termination. We study more specifically the case of the Knuth-Bendix ordering and polynomial interpretations. Next to that, we engaged ourselves into an other challenge, a more fundamental approach. This concerns the notion of ordering within typed [lambda]-calculi. The interest comes from the fact that such a representation is necessary when one has to represent a structure with an [oméga] -ary operation: that is an operation that only applies to monotonous sequences (which is the case of ordinal terms). We develop semantical tools, in particular we present a mono id al close category on graphs, but also syntactical constructions, in particular a calcul us where types arc graphs in which the traditional approach would be in terms of sets.
Document type :
Complete list of metadatas
Contributor : Thèses Ul <>
Submitted on : Thursday, March 29, 2018 - 12:47:02 PM
Last modification on : Tuesday, April 24, 2018 - 1:30:09 PM


Files produced by the author(s)


  • HAL Id : tel-01750475, version 1



Guillaume Bonfante. Constructions d'ordres, analyse de la complexité. Autre [cs.OH]. Institut National Polytechnique de Lorraine, 2000. Français. ⟨NNT : 2000INPL102N⟩. ⟨tel-01750475⟩



Record views


Files downloads