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:
“Well, for us, in history where goodness is a rare pearl, he who was good almost takes precedence over he who was great.”
—Victor Hugo (1802–1885)
“Free from public debt, at peace with all the world, and with no complicated interests to consult in our intercourse with foreign powers, the present may be hailed as the epoch in our history the most favorable for the settlement of those principles in our domestic policy which shall be best calculated to give stability to our Republic and secure the blessings of freedom to our citizens.”
—Andrew Jackson (1767–1845)
“The history of work has been, in part, the history of the worker’s body. Production depended on what the body could accomplish with strength and skill. Techniques that improve output have been driven by a general desire to decrease the pain of labor as well as by employers’ intentions to escape dependency upon that knowledge which only the sentient laboring body could provide.”
—Shoshana Zuboff (b. 1951)