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:

    “The history of all hitherto existing society is the history of class struggles.”
    —Karl Marx (1818–1883)

    “The one duty we owe to history is to rewrite it.”
    —Oscar Wilde (1854–1900)

    “The greatest honor history can bestow is that of peacemaker.”
    —Richard M. Nixon (1913–1995)