History
- Trakhtenbrot 1950: failure of completeness theorem in FO,
- Scholz 1952: characterisation of spectra in FO,
- Fagin 1974: the set of all properties expressible in existential second-order logic is precisely the complexity class NP,
- Chandra, Harel 1979/ 80: fixed-point FO extension for db query languages capable of expressing transitive closure -> queries as central objects of FMT.
- Immerman, Vardi 1982: fixed point logic over ordered structures captures PTIME -> descriptive complexity (... Immerman–Szelepcsényi theorem)
- Ebbinghaus, Flum 1995: First comprehensive book "Finite Model Theory"
- Abiteboul, Hull, Vianu 1995: Book "Foundations of Databases"
- Immerman 1999: Book "Descriptive Complexity"
- Kuper, Libkin, Paredaens 2000: Book "Constraint Databases"
- Darmstadt 2005/ Aachen2006: first international workshops on "Algorithmic Model Theory"
Read more about this topic: Finite Model Theory
Famous quotes containing the word history:
“Jesus Christ belonged to the true race of the prophets. He saw with an open eye the mystery of the soul. Drawn by its severe harmony, ravished with its beauty, he lived in it, and had his being there. Alone in all history he estimated the greatness of man.”
—Ralph Waldo Emerson (1803–1882)
“Literary works cannot be taken over like factories, or literary forms of expression like industrial methods. Realist writing, of which history offers many widely varying examples, is likewise conditioned by the question of how, when and for what class it is made use of.”
—Bertolt Brecht (1898–1956)
“The history of the world is none other than the progress of the consciousness of freedom.”
—Georg Wilhelm Friedrich Hegel (1770–1831)