Finite-Model Theory - a Personal Perspective.

@inproceedings{DBLP:conf/icdt/Fagin90,
  author    = {Ronald Fagin},
  editor    = {Serge Abiteboul and
               Paris C. Kanellakis},
  title     = {Finite-Model Theory - a Personal Perspective},
  booktitle = {ICDT'90, Third International Conference on Database Theory, Paris,
               France, December 12-14, 1990, Proceedings},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {470},
  year      = {1990},
  isbn      = {3-540-53507-1},
  pages     = {3-24},
  ee        = {db/conf/icdt/Fagin90.html},
  crossref  = {DBLP:conf/icdt/90},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/An2-2 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Journal Version

References

[AF90]

...

[AG87]

Miklós Ajtai, Yuri Gurevich: Monotone versus positive. J. ACM 34(4): 1004-1015(1987) BibTeX

[AG89]

Miklós Ajtai, Yuri Gurevich: Datalog vs. First-Order Logic. FOCS 1989: 142-147 BibTeX

[Ajt83]

...

[Ass55]

...

[Bar85]

...

[Ben62]

...

[BGK85]

Andreas Blass, Yuri Gurevich, Dexter Kozen: A Zero-One Law for Logic with a Fixed-Point Operator. Information and Control 67(1-3): 70-90(1985) BibTeX

[BWMR82]

Ronald V. Book, Christopher B. Wilson, Xu Mei-Rui: Relativizing Time, Space, and Time-Space. SIAM J. Comput. 11(3): 571-581(1982) BibTeX

[CFI89]

Jin-yi Cai, Martin Fürer, Neil Immerman: An Optimal Lower Bound on the Number of Variables for Graph Identification. FOCS 1989: 612-617 BibTeX

[CH82]

Ashok K. Chandra, David Harel: Structure and Complexity of Relational Queries. J. Comput. Syst. Sci. 25(1): 99-128(1982) BibTeX

[Cha88]

Ashok K. Chandra: Theory of Database Queries. PODS 1988: 1-9 BibTeX

[CHS87]

...

[Chu56]

...

[CK73]

...

[Cob64]

...

[Com87]

...

[Com88]

...

[Coo71]

Stephen A. Cook: The Complexity of Theorem-Proving Procedures. STOC 1971: 151-158 BibTeX

[Coo72]

Stephen A. Cook: A Hierarchy for Nondeterministic Time Complexity. STOC 1972: 187-192 BibTeX

[Dek76]

Michael I. Dekhtyar: On the Relativization of Deterministic and Nondeterministic Complexity Classes. MFCS 1976: 255-259 BibTeX

[DG79]

...

[Edm65]

...

[Ehr61]

...

[End72]

...

[ES74]

...

[Fag72]

...

[Fag73]

...

[Fag74]

...

[Fag75a]

...

[Fag75b]

...

[Fag75c]

...

[Fag76]

...

[Fag82]

Ronald Fagin: Horn clauses and database dependencies. J. ACM 29(4): 952-985(1982) BibTeX

[Fra54]

...

[Fra67]

...

[FSS81]

Merrick L. Furst, James B. Saxe, Michael Sipser: Parity, Circuits, and the Polynomial-Time Hierarchy. FOCS 1981: 260-270 BibTeX

[FV86]

...

[Gai64]

...

[GJ79]

M. R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman 1979, ISBN 0-7167-1044-7
BibTeX

[GJS76]

M. R. Garey, David S. Johnson, Larry J. Stockmeyer: Some Simplified NP-Complete Graph Problems. Theor. Comput. Sci. 1(3): 237-267(1976) BibTeX

[GKLT69]

...

[GMSV87]

Haim Gaifman, Harry G. Mairson, Yehoshua Sagiv, Moshe Y. Vardi: Undecidable Optimization Problems for Database Logic Programs. LICS 1987: 106-115 BibTeX

[Gol84]

...

[Gra83]

Etienne Grandjean: Complexity of the First-Order Theory of Almost All Finite Structures. Information and Control 57(2/3): 180-204(1983) BibTeX

[GS86]

...

[GS90]

...

[Gur76]

...

[Gur84]

...

[Gur88]

...

[Gur90]

...

[GV85]

...

[HIS85]

Juris Hartmanis, Neil Immerman, Vivian Sewelson: Sparse Sets in NP-P: EXPTIME versus NEXPTIME. Information and Control 65(2/3): 158-181(1985) BibTeX

[Imm81]

Neil Immerman: Number of Quantifiers is Better Than Number of Tape Cells. J. Comput. Syst. Sci. 22(3): 384-406(1981) BibTeX

[Imm82]

Neil Immerman: Upper and Lower Bounds for First Order Expressibility. J. Comput. Syst. Sci. 25(1): 76-98(1982) BibTeX

[Imm86]

Neil Immerman: Relational Queries Computable in Polynomial Time. Information and Control 68(1-3): 86-104(1986) BibTeX

[Imm87]

Neil Immerman: Languages that Capture Complexity Classes. SIAM J. Comput. 16(4): 760-778(1987) BibTeX

[Imm88]

Neil Immerman: Nondeterministic Space is Closed Under Complementation. SIAM J. Comput. 17(5): 935-938(1988) BibTeX

[Imm89]

...

[JS74]

...

[Kan90]

Paris C. Kanellakis: Elements of Relational Database Theory. Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) 1990: 1073-1156 BibTeX

[Kar75]

...

[Kau87]

...

[Kol90]

Phokion G. Kolaitis: Implicit Definability on Finite Structures and Unambiguous Computations (Preliminary Report). LICS 1990: 168-180 BibTeX

[KS85]

...

[KV87]

Phokion G. Kolaitis, Moshe Y. Vardi: The Decision Problem for the Probabilities of Higher-Order Properties. STOC 1987: 425-435 BibTeX

[KV90a]

Phokion G. Kolaitis, Moshe Y. Vardi: 0-1 Laws and Decision Problems for Fragments of Second-Order Logic. Inf. Comput. 87(1/2): 301-337(1990) BibTeX

[KV90b]

...

[KV90c]

Phokion G. Kolaitis, Moshe Y. Vardi: 0-1 Laws for Infinitary Logics (Preliminary Report). LICS 1990: 156-167 BibTeX

[Lev73]

...

[Lew79]

...

[Liv82]

...

[Lyn80]

...

[Lyn85]

...

[Mai83]

David Maier: The Theory of Relational Databases. Computer Science Press 1983, ISBN 0-914894-42-0
Contents BibTeX

[Mak85]

...

[PS89]

Leszek Pacholski, Wieslaw Szwast: The 0-1 Law Fails for the Class of Existential Second Order Gödel Sentences with Equality. FOCS 1989: 160-163 BibTeX

[Rad64]

...

[Sav70]

Walter J. Savitch: Relationships Between Nondeterministic and Deterministic Tape Complexities. J. Comput. Syst. Sci. 4(2): 177-192(1970) BibTeX

[Sch52]

...

[She78]

...

[Sho67]

...

[SS88]

...

[Sze88]

Róbert Szelepcsényi: The Method of Forced Enumeration for Nondeterministic Automata. Acta Inf. 26(3): 279-284(1988) BibTeX

[Tai59]

...

[Tar54]

...

[TK84]

...

[Tra50]

...

[Ull89-1]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume I. Computer Science Press 1988, ISBN 0-7167-8158-1
Contents BibTeX

[Ull89-2]

Jeffrey D. Ullman: Principles of Database and Knowledge-Base Systems, Volume II. Computer Science Press 1989, ISBN 0-7167-8162-X
Contents BibTeX

[Var82a]

Moshe Y. Vardi: The Complexity of Relational Query Languages (Extended Abstract). STOC 1982: 137-146 BibTeX

[Var82b]

Moshe Y. Vardi: On Decomposition of Relational Databases. FOCS 1982: 176-185 BibTeX

[Vau54]

...

[Vau60]

...

[Wil80]

...

Referenced by

1. Sérgio Lifschitz, Victor Vianu: A Probabilistic View of Datalog Parallelization. ICDT 1995: 294-307
2. Serge Abiteboul, Kevin J. Compton, Victor Vianu: Queries Are Easier Than You Thought (Probably). PODS 1992: 23-32
3. Serge Abiteboul, Moshe Y. Vardi, Victor Vianu: Computing with Infinitary Logic. ICDT 1992: 113-123