% *** books, surveys

@BOOK{EF:finmt,
	AUTHOR = "Heinz-Dieter Ebbinghaus and J{\"o}rg Flum",
	TITLE = "Finite Model Theory",
	SERIES = pml,
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1995
}

@ARTICLE{Fag:finmtp,
	AUTHOR = "Ronald Fagin",
	TITLE = "Finite-Model Theory---A Personal Perspective",
	JOURNAL = tcs,
	VOLUME = 116,
	NUMBER = 1,
	PAGES = "3--31",
	YEAR = 1993
}
		  
@INCOLLECTION{Imm:descc,
	AUTHOR = "Neil Immerman",
	TITLE = "Descriptive and Computational Complexity",	
	EDITOR = "J. Hartmanis",
	BOOKTITLE = "Lecture Notes AMS Short Course in Computational
		Complexity Theory, Atlanta, GA, 5--6 Jan 1988",
	SERIES = "Proceedings of Symposia in Applied Mathematics",
	VOLUME = 38,
	PUBLISHER = ams,
	ADDRESS = "Providence, RI",	
	PAGES = "75--91",
	YEAR = 1989,	
	URL = "http://www.cs.umass.edu/~immerman/ams-survey.ps"
}

@ARTICLE{Imm:descla,
	AUTHOR = "Neil Immerman",
	TITLE = "Descriptive Complexity: A Logician's Approach to Computation",
	JOURNAL = nams,
	VOLUME = 42,
	NUMBER = 10,
	PAGES = "1127--1133",
	YEAR = 1995,
	URL = "http://www.cs.umass.edu/~immerman/ams-notices.ps"
}

@INCOLLECTION{Gur:towltc,
	AUTHOR = "Yuri Gurevich",
	TITLE = "Toward Logic Tailored for Computational Complexity",
	EDITOR = "M. M. Richter et al.",
	BOOKTITLE = "Proceedings Logic Colloquium '83, Aachen, FRG,
		18--23 July 1983, Part  2: Computation and Proof Theory",
	SERIES = lnm,
	VOLUME = 1104,	
	PAGES = "175--216",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1984
}

@INCOLLECTION{Gur:logccs,
	AUTHOR = "Yuri Gurevich",
	TITLE = "Logic and the Challenge of Computer Science",
	EDITOR = "E. B{\"o}rger",
	BOOKTITLE = "Trends in Theoretical Computer Science",
	SERIES = "Principles of Computer Science Series",
	VOLUME = 12,
	CHAPTER = 1,
	PAGES = "1--57",
	PUBLISHER = "Computer Science Press",
	ADDRESS = "Rockville, MD",
	YEAR = 1988
}


% *** first-order logic, second-order logic, fragments
		  
@ARTICLE{Imm:numqib,
	AUTHOR = "Neil Immerman",
	TITLE = "Number of Quantifiers Is Better Than Number of Tape Cells",
	JOURNAL = jcss,
	VOLUME = 22,
	NUMBER = 3,
	PAGES = "384--406",
	YEAR = 1981
}

@ARTICLE{Imm:upplwf,
	AUTHOR = "Neil Immerman",
	TITLE = "Upper and Lower Bounds for First Order Expressibility",
	JOURNAL = jcss,
	VOLUME = 25,
	NUMBER = 1,
	PAGES = "76--98",
	YEAR = 1992
}

@ARTICLE{Lei:desccc,
	AUTHOR = "Daniel Leivant",
	TITLE = "Descriptive Characterizations of Computational Complexity",
	JOURNAL = jcss,
	VOLUME = 39,
	NUMBER = 1,
	PAGES = "51--83",
	YEAR = 1989
}

@TECHREPORT{Ros:modlfs,
	AUTHOR = "Eric Rosen",
	TITLE = "Modal Logic over Finite Structures",
	NUMBER = "95-27",
	INSTITUTION = "Inst.\ for Research in Cognitive Science, Univ.\ of 
		Pennsylvania, Philadelphia, PA",
	YEAR = 1995,
	URL = "ftp://ftp.cis.upenn.edu/pub/ircs/tr/95-27.ps.Z"
}

@PHDTHESIS{Ros:finmtf,
	AUTHOR = "Eric Rosen",
	TITLE = "Finite Model Theory and Finite Variable Logics",
	TYPE = "{PhD} thesis (Technical Report 95-28)",
	SCHOOL = "Inst.\ for Research in Cognitive Science, Univ.\ of 
		Pennsylvania, Philadelphia, PA",
	YEAR = 1995,
	URL = "ftp://ftp.cis.upenn.edu/pub/ircs/tr/95-28.ps.Z"
}

@INCOLLECTION{Daw:ressol,
	AUTHOR = "Anuj Dawar",
	TITLE = "A Restricted Second-Order Logic for Finite Structures",
	EDITOR = "D. Leivant",
	BOOKTITLE = "Selected Papers Int'l Workshop on Logic and
		Computational Complexity, LCC'94, Indianapolis, IN, USA, 
		13--16 Oct 1994",
	SERIES = lncs,
	VOLUME = 960,	
	PAGES = "393--413",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1995,
	URL = "ftp://ftp.swan.ac.uk/pub/compsci/ADawar/restricted.ps"
}

@BOOK{Ott:bouvlc,
	AUTHOR = "Martin Otto",
	TITLE = "Bounded Variable Logics and Counting",
	SERIES = lnl,
	VOLUME = 9,
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1997
}
		  
% *** fixed-point logics
		  
@INCOLLECTION{AU:unidrl,
	AUTHOR = "A. V. Aho and J. D. Ullman",
	TITLE = "Universality of Data Retrieval Languages",
	BOOKTITLE = "Conf.\ Record 6th Annual ACM Symp.\ on Principles of 
		Programming Languages, POPL'79, San Antonio, TX, USA,
		29--31 Jan 1979",
	PAGES = "110--117",
	PUBLISHER = acm,
	ADDRESS = "New York",
	YEAR = 1979
}

@ARTICLE{CH:strcrq,
	AUTHOR = "Ashok Chandra and David Harel",
	TITLE = "Structure and Complexity of Relational Queries",
	JOURNAL = jcss,
	VOLUME = 25,
	NUMBER = 1,
	PAGES = "99--128",
	YEAR = 1982
}
		  
@ARTICLE{CH:horcqg,
	AUTHOR = "Ashok K. Chandra and David Harel",
	TITLE = "{H}orn Clause Queries and Generalizations",
	JOURNAL = jlp,
	VOLUME = 1,
	NUMBER = 1,
	PAGES = "1--15",
	YEAR = 1985
}

@INCOLLECTION{Var:comrql,
	AUTHOR = "Moshe Y. Vardi",
	TITLE = "The Complexity of Relational Query Languages 
		(Extended Abstract)",
	BOOKTITLE = "Proceedings 14th Annual ACM Symp.\ on Theory of Computing,
		 STOC'82, San Francisco, CA, USA, 5--7 May 1982",
	PAGES = "137--146",
	PUBLISHER = acm,
	ADDRESS = "New York",
	YEAR = 1982
}

@ARTICLE{Imm:relqcp,
	AUTHOR = "Neil Immerman",
	TITLE = "Relational Queries Computable in Polynomial Time",
	JOURNAL = ic,
	VOLUME = 68,
	NUMBER = "1--3",
	PAGES = "86--104",
	YEAR = 1986,
	URL = "http://www.cs.umass.edu/~immerman/query.ps"
}

@ARTICLE{Imm:lanccc,
	AUTHOR = "Neil Immerman",
	TITLE = "Languages That Capture Complexity Classes",
	JOURNAL = siamjc,
	VOLUME = 16,
	NUMBER = 4,
	PAGES = "760--778",
	YEAR = 1987,
	URL = "http://www.cs.umass.edu/~immerman/capture.ps"
}

@ARTICLE{BGK:zeroll,
	AUTHOR = "Andreas Blass and Yuri Gurevich and Dexter Kozen",
	TITLE = "A Zero-One Law for Logic with a Fixed-Point Operator",
	JOURNAL = ic,
	VOLUME = 67,
	NUMBER = 1,
	PAGES = "70--90",
	YEAR = 1985
}

@ARTICLE{GS:fixpef,
	AUTHOR = "Yuri Gurevich and Saharon Shelah",
	TITLE = "Fixed-Point Extensions of First-Order Logic",	
	JOURNAL = apal,
	VOLUME = 32,
	NUMBER = ???,
	PAGES = "265--280",
	YEAR = 1986
}	

@INCOLLECTION{BG:exifpl,
	AUTHOR = "Andreas Blass and Yuri Gurevich",
	TITLE = "Existential Fixed-Point Logic",
	EDITOR = "E. B{\"o}rger",
	BOOKTITLE = "Computation Theory and Logic",
	SERIES = lncs,
	VOLUME = 270,
	PAGES = "20--36",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1987
}

@INCOLLECTION{Dah:skonfc,
	AUTHOR = "Elias Dahlhaus",
	TITLE = "{S}kolem Normal Forms Concerning the Least Fixpoint",
	EDITOR = "E. B{\"o}rger",
	BOOKTITLE = "Computation Theory and Logic",
	SERIES = lncs,
	VOLUME = 270,
	PAGES = "101--106",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1987
}

@ARTICLE{AG:monvp,
	AUTHOR = "Miklos Ajtai and Yuri Gurevich",
	TITLE = "Monotone versus Positive",
	JOURNAL = jacm,
	VOLUME = 34,
	NUMBER = 4,
	PAGES = "1004--1015",
	YEAR = 1987
}

@ARTICLE{Lei:inddfs,
	AUTHOR = "Daniel Leivant",
	TITLE = "Inductive Definitions over Finite Structures",
	JOURNAL = iandc,
	VOLUME = 89,
	NUMBER = 2,
	PAGES = "95--108",
	YEAR = 1990
}  
		  
@ARTICLE{McC:wheap,
	AUTHOR = "Gregory L. McColm",
	TITLE = "When is Arithmetic Possible?",
	JOURNAL = apal,
	VOLUME = 50,
	NUMBER = 1,
	PAGES = "29--50",
	YEAR = 1990
}

@INCOLLECTION{Bos:ehrfgf,
	AUTHOR = "Uwe Bosse",
	TITLE = "An ``{E}hrenfeucht-{F}ra{\"i}ss{\'e} Game'' for Fixpoint Logic
		and Stratified Fixpoint Logic",
	EDITOR = "E. B{\"o}rger and G. J{\"a}ger and H. Kleine B{\"u}ning and
		S. Martini and M. M. Richter",
	BOOKTITLE = "Selected Papers 6th Workshop on Computer Science Logic,
		CSL'92, San Miniato, Italy, 28 Sept -- 2 Oct 1992",
	SERIES = lncs,
	VOLUME = 702,
	PAGES = "100--114",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1993
}

@ARTICLE{Gro:compfp,
	AUTHOR = "Martin Grohe",
	TITLE = "Complete Problems for Fixed-Point Logics",
	JOURNAL = jsl,
	VOLUME = 60,
	NUMBER = 2,
	PAGES = "517--527",
	YEAR = 1995
}

@PHDTHESIS{Gro:strfpl,
	AUTHOR = "Martin Grohe",
	TITLE = "The Structure of Fixed-Point Logics",
	SCHOOL = "Inst.\ f{\"u}r Math.\ Logik und Grundl.\ der Math.,
		Albert-Ludwigs-Universit{\"a}t Freiburg",
	MONTH = dec,
	YEAR = 1994,
	URL = "http://logimac.mathematik.uni-freiburg.de/preprints/grohe/d.ps"
}
@UNPUBLISHED{Gro:exilfp,
	AUTHOR = "Martin Grohe",
	TITLE = "Existential Least Fixed-Point Logic and Its Relatives",
	MONTH = mar,
	YEAR = 1996,
	NOTE = "To appear in " # jlc,
	URL = "http://logimac.mathematik.uni-freiburg.de/preprints/grohe/elfp.ps"
}
		  
@INCOLLECTION{GO:inddcf,
	AUTHOR = "Erich Gr{\"a}del and Martin Otto",
	TITLE = "Inductive Definability with Counting on Finite Structures",
	EDITOR = "E. B{\"o}rger and G. J{\"a}ger and H. Kleine B{\"u}ning and
		S. Martini and M. M. Richter",
	BOOKTITLE = "Selected Papers 6th Workshop on Computer Science Logic,
		CSL'92, San Miniato, Italy, 28 Sept -- 2 Oct 1992",
	SERIES = lncs,
	VOLUME = 702,
	PAGES = "231--247",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1993
}

@ARTICLE{Ott:exppfp,
	AUTHOR = "Martin Otto",
	TITLE = "The Expressive Power of Fixed-Point Logic with Counting",
	JOURNAL = jsl,
	VOLUME = 61,
	NUMBER = 1,
	PAGES = "147--176",
	YEAR = 1996
}
		
@ARTICLE{Kol:exppsl,
	AUTHOR = "Phokion G. Kolaitis",
	TITLE = "The Expressive Power of Stratified Logic Programs",
	JOURNAL = iandc,
	VOLUME = 90,
	NUMBER = 1,
	PAGES = "50--66",
	YEAR = 1991
} 

@ARTICLE{KP:whynnf,
	AUTHOR = "Phokion G. Kolaitis and Christos H. Papadimitriou",
	TITLE = "Why Not Negation by Fixpoint?",
	JOURNAL = iandc,
	VOLUME = 43,
	NUMBER = 1,
	PAGES = "125--144",
	YEAR = 1991
}

@ARTICLE{AV:comfol,
	AUTHOR = "Serge Abiteboul and Victor Vianu",
	TITLE = "Computing with First-Order Logic",
	JOURNAL = jcss,
	VOLUME = 50,
	NUMBER = 2,
	PAGES = "309--335",	
	YEAR = 1995
}
	
@INCOLLECTION{AV:fixefo,
	AUTHOR = "Serge Abiteboul and Victor Vianu",
	TITLE = "Fixpoint Extensions of First-Order Logic and {D}atalog-Like
		Languages",
	BOOKTITLE = "Proceedings 4th Annual IEEE Symp.\ on Logic in Computer
		Science, LICS'89, Pacific Grove, CA, USA, 5--9 June 1989",
	PAGES = "71--79",
	PUBLISHER = ieee,
	ADDRESS = "Los Alamitos, CA",
	YEAR = 1989
}	

@ARTICLE{AV:datedq,
	AUTHOR = "Serge Abiteboul and Victor Vianu",
	TITLE = "{D}atalog Extensions for Database Queries and Updates",
	JOURNAL = jcss,
	VOLUME = 43,
	NUMBER = 1,
	PAGES = "62--124",
	YEAR = 1991
}

@UNPUBLISHED{AV:exppql,
	AUTHOR = "Serge Abiteboul and Victor Vianu",
	TITLE = "Expressive Power of Query Languages",
	NOTE = "Unpublished draft",
	URL = "ftp://ftp.inria.fr/INRIA/Projects/verso/VersoReport-036.ps.Z"
}

@INCOLLECTION{AVV:fixlrm,
        AUTHOR = "Serge Abiteboul and Moshe Y. Vardi and Victor Vianu",
        TITLE = "Fixpoint Logics, Relational Machines, and Computational
                Complexity",
        BOOKTITLE = "Proceedings 7th Annual IEEE Structure in Complexity
                Theory Conference, STRUCTURE'92, Boston, MA, USA, 
                22--25 June 1992",
        PAGES = ???,
        PUBLISHER = ieee,
        ADDRESS = "Los Alamitos, CA",
        YEAR = 1992,
	URL = "ftp://ftp.inria.fr/INRIA/Projects/verso/VersoReport-042.ps.Z"
}

@ARTICLE{Ste:logscc,
        AUTHOR = "Iain A. Stewart",
        TITLE = "Logical and Schematic Charaterization of Complexity Classes",
        JOURNAL = actai,
        VOLUME = 30,
        NUMBER = 1,
        PAGES = "61--87",
        YEAR = 1987
}

@ARTICLE{GM:powdtc,
	AUTHOR = "Erich Gr{\"a}del and Gregory L. McColm",
	TITLE = "On the Power of Deterministic Transitive Closures",
	JOURNAL = iandc,
	VOLUME = 119,
	NUMBER = 1,
	PAGES = "129--135",
	YEAR = 1995
}	

% *** infinitary logics

@INCOLLECTION{KV:inflcs,
	AUTHOR = "Phokion G. Kolaitis and Moshe Y. Vardi",
	TITLE = "Infinitary Logic for Computer Science",
	EDITOR= "W. Kuich",
	BOOKTITLE = "Proceedings 19th Int'l Coll.\ on Automata, Languages,
		and Programming, ICALP'92, Wien, Austria, 13--17 July 1992",
	SERIES = lncs,
	VOLUME = 623,
	PAGES = "450--473",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1992
}

@ARTICLE{KV:inflzo,
	AUTHOR = "Phokion G. Kolaitis and Moshe Y. Vardi",
	TITLE = "Infinitary Logics and 0-1 Laws",
	JOURNAL = iandc,
	VOLUME= 98,
	NUMBER = 2,
	PAGES = "258--294",
	YEAR = 1992
}

@INCOLLECTION{KV:fixlvi,
	AUTHOR = "Phokion G. Kolaitis and Moshe Y. Vardi",
	TITLE = "Fixpoint Logic vs.\ Infinitary Logic in Finite-Model Theory",
	BOOKTITLE = "Proceedings 7th Annual IEEE Symp.\ on Logic in Computer
		Science, LICS'92, Santa Cruz, CA, USA, 22--25 June 1992",
	PAGES = "46--57",
	PUBLISHER = ieee,
	ADDRESS = "Los Alamitos, CA",
	YEAR = 1992
}

@ARTICLE{AVV:comil,
	AUTHOR = "Serge Abiteboul and Moshe Y. Vardi and Victor Vianu",
	TITLE = "Computing with Infinitary Logic",
	JOURNAL = tcs,
	VOLUME = 149,
	NUMBER = 1,
	PAGES = "101--128",
	YEAR = 1995
}

@ARTICLE{DLW:inflid,
	AUTHOR = "Anuj Dawar and Steven Lindell and Scott Weinstein",
	TITLE = "Infinitary Logic and Inductive Definability over Finite 
		Structures",
	JOURNAL = iandc,
	VOLUME = 119,
	NUMBER = 2,
	PAGES = "160--175",
	YEAR = 1995
}

@INCOLLECTION{DHK:impdil,
	AUTHOR = "Anuj Dawar and Lauri Hella and Phokion Kolaitis",
	TITLE = "Implicit Definability and Infinitary Logic in Finite Model
		Theory",
	EDITOR = "Z. F{\"u}l{\"o}p and F. G{\'e}cseg",
	BOOKTITLE = "Proceedings 22nd Int'l Coll.\ on Automata, Languages,
		and Programming, ICALP'95, Szeged, Hungary, 10--14 July 1995",
	SERIES = lncs,
	VOLUME = 944,
	PAGES = "624--635",
	PUBLISHER = springer,
	ADDRESS = "Berlin",
	YEAR = 1995,
	URL = "http://www.swan.ac.uk/compsci/AllStaff/ADmore/icalp.ps"
}