Skip to Main content Skip to Navigation
Theses

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 :
Theses
Complete list of metadatas

https://hal.univ-lorraine.fr/tel-01750475
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

File

INPL_T_2000_BONFANTE_G.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-01750475, version 1

Collections

Citation

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

Share

Metrics

Record views

158

Files downloads

77