Jump to content

Talk:Finite model theory

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Sterling (talk | contribs) at 00:48, 16 January 2011 (→Outline). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
WikiProject iconMathematics Start‑class Mid‑priority
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
StartThis article has been rated as Start-class on Wikipedia's content assessment scale.
MidThis article has been rated as Mid-priority on the project's priority scale.

Perhaps we could mention that finite model theory might help us resolve P vs. NP? (See http://www2.ing.puc.cl/~jabaier/iic2212/poll-1.pdf for instance). My understanding is that several finite model theorists are in that field in hopes of conquering this major problem. Any thoughts?

Outline

  1. Character 1: Finite structure. Belongs to MT. relationship between a formal language and its interpretations. ...
  2. History:
    1. Trakhtenbrot 1950: failure of completeness theorem in FO,
    2. Scholz 1952: characterisation of specra 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. Kanellakis, Kuper, Revesz 1995: Constraint Query Languages -> infinite sets in databases -> algorithmic model theory.
    7. Book: Ebbinghaus, Flum 1995: Finite Model Theory
    8. Book: Immermann 1999: Descriptive Complexity
    9. Book: Abiteboul, Hull, Vianu 1995: Foundations of Databases
  3. Character 2: Discrimination of structures
  4. Parts: FMT vs MT, Language/ Complexity classification
  5. Applications: databases, descriptive complexity, languages/ modeling
  6. Tools: games, locality, 0-1 laws
  7. Objects of study: FO, extensions of FO/ restrictions of SO, sub-FO

Sterling (talk) 00:48, 16 January 2011 (UTC)[reply]

Retrieved from "https://en.wikipedia.org/w/index.php?title=Talk:Finite_model_theory&oldid=408119468"