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 steps toward the emancipation of women are first intellectual, then industrial, lastly legal and political. Great strides in the first two of these stages already have been made of millions of women who do not yet perceive that it is surely carrying them towards the last.”
—Ellen Battelle Dietrick, U.S. suffragist. As quoted in History of Woman Suffrage, vol. 4, ch. 13, by Susan B. Anthony and Ida Husted Harper (1902)
“Every literary critic believes he will outwit history and have the last word.”
—Mason Cooley (b. 1927)
“What would we not give for some great poem to read now, which would be in harmony with the scenery,—for if men read aright, methinks they would never read anything but poems. No history nor philosophy can supply their place.”
—Henry David Thoreau (1817–1862)