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:
“The history of all Magazines shows plainly that those which have attained celebrity were indebted for it to articles similar in natureto Berenice—although, I grant you, far superior in style and execution. I say similar in nature. You ask me in what does this nature consist? In the ludicrous heightened into the grotesque: the fearful coloured into the horrible: the witty exaggerated into the burlesque: the singular wrought out into the strange and mystical.”
—Edgar Allan Poe (1809–1849)
“Considered in its entirety, psychoanalysis won’t do. It’s an end product, moreover, like a dinosaur or a zeppelin; no better theory can ever be erected on its ruins, which will remain for ever one of the saddest and strangest of all landmarks in the history of twentieth-century thought.”
—Peter B. Medawar (1915–1987)
“The principal office of history I take to be this: to prevent virtuous actions from being forgotten, and that evil words and deeds should fear an infamous reputation with posterity.”
—Tacitus (c. 55–c. 120)