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:

    ... that there is no other way,
    That the history of creation proceeds according to
    Stringent laws, and that things
    Do get done in this way, but never the things
    We set out to accomplish and wanted so desperately
    To see come into being.
    John Ashbery (b. 1927)

    It takes a great deal of history to produce a little literature.
    Henry James (1843–1916)