Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, Epiciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Model Theory and Computational Complexity

Abstract : Model theory has lately become a domain of interest to computer scientists. The reason is that model theory, and in particular its restriction to finite models, has led to some new results in computational complexity (e.g. NLOGSPACE=co-NLOGSPACE). In this report, firstly we present a survey of this theory and we focus on the descriptive complexity aspects and other links between computational complexity and model theory. Secondly, we extend some results of Grandjean and Lynch. We give a more precise logical characterization of complexity classes NTIME(n^d) for some d. This leads us to show applications of this result and to give openings made possible by this result.
Document type :
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:08:43 AM
Last modification on : Saturday, September 11, 2021 - 3:19:17 AM


Files produced by the author(s)


  • HAL Id : hal-02101873, version 1



Grégory Lafitte, Jacques Mazoyer. Model Theory and Computational Complexity. [Research Report] LIP RR-1998-02, Laboratoire de l'informatique du parallélisme. 1997, 2+33p. ⟨hal-02101873⟩



Record views


Files downloads