Finite Model Theory - History

History

  1. Trakhtenbrot 1950: failure of completeness theorem in FO,
  2. Scholz 1952: characterisation of spectra in FO,
  3. Fagin 1974: the set of all properties expressible in existential second-order logic is precisely the complexity class NP,
  4. Chandra, Harel 1979/ 80: fixed-point FO extension for db query languages capable of expressing transitive closure -> queries as central objects of FMT.
  5. Immerman, Vardi 1982: fixed point logic over ordered structures captures PTIME -> descriptive complexity (... Immerman–Szelepcsényi theorem)
  6. Ebbinghaus, Flum 1995: First comprehensive book "Finite Model Theory"
  7. Abiteboul, Hull, Vianu 1995: Book "Foundations of Databases"
  8. Immerman 1999: Book "Descriptive Complexity"
  9. Kuper, Libkin, Paredaens 2000: Book "Constraint Databases"
  10. Darmstadt 2005/ Aachen2006: first international workshops on "Algorithmic Model Theory"

Read more about this topic:  Finite Model Theory

Famous quotes containing the word history:

    “Properly speaking, history is nothing but the crimes and misfortunes of the human race.”
    —Pierre Bayle (1647–1706)

    “The visual is sorely undervalued in modern scholarship. Art history has attained only a fraction of the conceptual sophistication of literary criticism.... Drunk with self-love, criticism has hugely overestimated the centrality of language to western culture. It has failed to see the electrifying sign language of images.”
    —Camille Paglia (b. 1947)

    “The history of the world is none other than the progress of the consciousness of freedom.”
    —Georg Wilhelm Friedrich Hegel (1770–1831)