\newcommand{\apal}{{\it Annals of Pure and Applied Logic }}
\newcommand{\bsl}{{\it Bulletin of Symbolic Logic }}
\newcommand{\cav}{{\it Computer Aided Verification, Proc. Intl. Conf.}}
\newcommand{\cjtcs}{{\it Chicago J.~Theoret.~Comp.~Sci. }}
\newcommand{\eatcs}{{\it Bull.~ European Assoc.~Theoretical Comp.~Sci. }}
\newcommand{\focs}{{\it IEEE Found.~of Comp.~Sci.~Symp. }}
\newcommand{\pods}{{\it ACM Symp.~Principles Database Systems }}
\newcommand{\stacs}{{\it Symp.~Theoretical Aspects Comp.~Sci. }}
\newcommand{\stoc}{{\it ACM Symp.~ Theory Of Comput. }}
\newcommand{\strc}{{\it IEEE Structure in Complexity Theory Symp. }}
\newcommand{\ic}{{\it Information and Computation }}
\newcommand{\IC}{{\it Information and Computation}}
\newcommand{\jacm}{{\it J.~ Assoc.~Comput.~Mach. }}
\newcommand{\jalg}{{\it J.~Algorithms }}
\newcommand{\jcss}{{\it J.~Comput.~Sys.~Sci. }}
\newcommand{\jsc}{{\it J.~Symbolic Comp. }}
\newcommand{\jsl}{{\it J.~Symbolic Logic }}
\newcommand{\lics}{{\it IEEE Symp.~Logic In Comput.~Sci. }}
\newcommand{\mst}{{\it Math.~Systems Theory }}
\newcommand{\popl}{{\it ACM Symp.~Principles of Programming Languages }}
\newcommand{\sicomp}{{\it SIAM J.~Comput. }}
\newcommand{\tcs}{{\it Theoret.~Comp.~Sci. }}



\begin{thebibliography}{Imm89b}
\bibitem[AV91]{AV}
S.~Abiteboul and V.~Vianu, ``Generic Computation And Its
Complexity,'' {\it 32nd IEEE Symposium on FOCS} (1991), 209-219.
\bibitem[AHV95]{AHV}S.~Abiteboul, R.~Hull, and V.~Vianu, {\it Foundations
  of Databases}, 1995, Addison-Wesley.
\bibitem[AVV97]{AVV}S.~Abiteboul, M.Y.~Vardi, and V.~Vianu, ``Fixpoint Logics,
Relational Machines, and Computational Complexity,'' \jacm 44(1) (1997), 30 -- 56.
\bibitem[AAI97]{Allender et al} M.~Agrawal, E.~Allender, R.~Impagliazzo, T.~Pitassi and
 S.~Rudich, ``Reducing the Complexity of Reductions,'' \stoc (1997), 730--738.
\bibitem[AHU74]{AHU}  A.V.~Aho, J.E.~Hopcroft and J.D.~Ullman, {\it The
    Design and Analysis of Computer Algorithms,} Addison-
    Wesley (1974).
\bibitem[Ajt83]{Ajtai}  M.~Ajtai, ``$\Sigma^1_1$ Formulae on Finite 
    Structures,'' {\it Annals of Pure and Applied Logic} 
    { 24} (1983), 1-48.
\Bibitem[Ajt87]{Ajtai-expander} M.~Ajtai, ``Recursive Construction for
  3-Regular Expanders,''  {\it 28th IEEE Symp. on Foundations of Computer
  Science} (1987), 295-304. 
\bibitem[Ajt89]{Ajtai-existential-hierarchy}M.~Ajtai, ``First-Order
  Definability on Finite Structures,'' \apal (1989), 211-225.
\bibitem[AF90]{Ajtai-Fagin} M.~Ajtai and R.~Fagin, ``Reachability
is Harder for Directed than for Undirected Graphs,'' {\it J.
Symb. Logic,} { 55} (1990), 113-150.
\bibitem[AFS97]{AFS}M.~Ajtai, R.~Fagin, and L.~Stockmeyer, ``The Closure of
  Monadic NP,'' IBM Research Report RJ 10092 (1997).
The closure of monadic NP, with Miklos Ajtai and Larry
Stockmeyer. J. Computer and System Sciences 60, June 2000,
pp. 660-716. (Special issue for selected papers from the 1998 ACM Symp. on
Theory of Computing).


\bibitem[AG87]{Ajtai-Gurevich}M.~Ajtai and Y.~Gurevich, ``Monotone versus
  Positive,'' \jacm 34 (1987), 1004--1015.
\bibitem[AKL79]{AKLLR} R.~Aleliunas, R.~Karp, R.~Lipton, L.~Lov\'asz, and C.~Rackoff,
    ``Random Walks, Universal Traversal Sequences, and the
    Complexity of Maze Problems,'' \focs  (1979), 218-233.
\bibitem[ABI97]{ABI}E.~Allender,N.~Immerman,J.~Balc\'azar,``A First-Order
Isomorphism Theorem,''  \sicomp\ 26(2) (1997), 557-567.
\bibitem[ACF94]{Carter-memory-hierarchy}B.~Alpern,  L.~Carter, E.~Feig, and T.~Selker,
  ``The Uniform Memory Hierarchy Model of Computation,'' {\it Algorithmica,
  12(2-3)} (1994),  72--109.
\bibitem[AG94]{Gottlieb}G.~Almasi and A.~Gottlieb, {\it 
Highly Parallel Computing (Second Edition) } 1994, Benjamin-Cummings.
\bibitem[ASE92]{probabilistic method} N.~Alon, J.~Spencer, and
  P.~Erd\H{o}s, {\it The Probabilistic Method,} 1992, John Wiley and Sons,
  Inc. 
\bibitem[ADN95]{ADN}H.~Andr\'eka, I.~D\"untsch, and I.~N\'emeti,
``Expressibility of Properties of Relations,'' \jsl 60(3) (1995), 970 - 991.
\bibitem[AF97]{Arora-Fagin}S.~Arora and R.~Fagin, ``On Winning Strategies in
Ehrenfeucht-Fra\"{\i}ss\'e Games,'' \tcs 174(1-2) (1997), 97-121.
\bibitem[ALMSS]{ALMSS}S. Arora, C. Lund, R. Motwani,  M.Sudan, and
  M. Szegedy, ``Proof Verification and the Hardness of Approximation
  Problems,'' \jacm 45(3) (1998), 501-555.  
\bibitem[AS92]{AS} S. Arora and S. Safra, ``Probabilistic Checking of
Proofs: a New Characterization of NP,'' \jacm 45(1) (1998), 70-122.  A
preliminary version appeared in  \focs (1992), 2-13.
\bibitem[Ba81]{Babai}L.~Babai, ``Moderately Exponential
Bound for Graph Isomorphism,''in {\it Proc. Int. Conf. Fundamentals of
       Computation Theory } (1981), Springer LNCS, 34 -- 50.
\bibitem[BK80]{BK} L.~Babai and L.~Ku{\v c}era, Canonical Labelling of Graphs in
    Linear Average Time,'' {\it 20th IEEE Symp. on Foundations of Computer
    Science} (1980), 39-46.
\bibitem[BL83]{Babai-Luks}  L.~Babai and E.~Luks, ``Canonical Labelling of Graphs,''
    {\it 15th ACM STOC Symp.}, (1983), 171-183.
\bibitem[BDG]{BDG} J.~Balc\'azar, J.~D\'ias, and J.~Gabarr\'o,
{\it Structural Complexity,} Vols. I and II, EATCS Monographs on
Theoretical Computer Science, 1988, Springer-Verlag.
\bibitem[BI97]{uniform}D.M.~Barrington and N.~Immerman, ``Time, Hardware,
 and Uniformity,'' in {\it Complexity Theory Retrospective II}, L.~Hemaspaandra
 and A.~Selman, editors, 1997, Springer-Verlag, 1-22.  
\bibitem[BIS88]{BIS}D.M.~Barrington, N.~Immerman, and H.~Straubing, ``On Uniformity Within 
    $\nc^1$,'' {\it Third Annual Structure in Complexity Theory Symp.} (1988), 47-59.
\bibitem[BBI97]{BBI}D.M.~Barrington, J.~Buss, and N.~Immerman, ``Capturing
Deterministic Space via Number of Variables,'' in preparation.
\bibitem[Bar77]{Barwise pebble game} J.~Barwise, ``On Moschovakis Closure Ordinals,''
J. Symb. Logic 42 (1977), 292-296.
\bibitem[Bea86]{Beame} P.~Beame, ``Limits on the Power of 
    Concurrent-Write Parallel Machines,'' {\it 18th ACM STOC}
    (1986), 169-176.
\bibitem[Bea96]{Beame-switching} P.~Beame, ``A Switching Lemma Primer,''
manuscript, http://www.cs.washington.edu/homes/beame/papers.html.
\bibitem[Ben62]{Bennett}J.~Bennett, ``On Spectra'' (1962), Ph.D. thesis,
    Princeton University.
\bibitem[BG03]{BG03} Andreas Blass and Yuri Gurevich, ``Strong Extension Axioms and
  Shelah's Zero-One Law for Choiceless Polynomial Time,'' \jsl 68(1) (2003), 65-131.
\bibitem[BGK85]{BGK} A.~Blass, Y.~Gurevich and D.~Kozen, ``A Zero--One Law for Logic With
                a Fixed Point Operator,'' \ic 67 (1985), 70-90.
\bibitem[Bol82]{Bollobas} B\'ela Bollob\'as, {\it Random Graphs,} Academic Press 
    (1982).
\bibitem[BH92]{BH}R.~Boppana and M.~Halld\'orsson, "Approximating Maximum
       Independent Sets by Excluding Subgraphs," {\it BIT } 32(2)   (1992),
       180-196.
\bibitem[BS90]{BS} R.~Boppana and M.~Sipser, ``The Complexity of Finite
       Functions,'' in {\it Handbook of Theoretical Computer Science,
       Vol. A}  1990, Jan van Leeuwen, ed., Elsevier, Amsterdam and
       M.I.T. Press, Cambridge, MA.
\bibitem[B82]{Borger} E.~B\"orger, ``Decision Problems in Predicate
Logic,'' in {\it Logic Colloquium '82,} G.~Lolli, G.~Longo and A.~Marcia
(editors) North-Holland, 1984, 263 -- 301.
\bibitem[BCD88]{Tompa} A.~Borodin, S.A.~Cook, P.W.~Dymond, W.L.~Ruzzo,
    and M.~Tompa, ``Two Applications of Complementation via Inductive
    Counting,''  {\it Third Annual Structure in Complexity Theory Symp.} (1988), 116-125.
\bibitem[BCH86]{BCH} P.~Beame, S.~Cook, H.J.~Hoover, ``Log Depth
    Circuits for Division and Related Problems,'' {\it SIAM
    J. Comput. 15:4} (1986), 994-1003.
\bibitem[BCP83]{BCP}  A.~Borodin, S.~Cook, and N.~Pippenger, ``Parallel Computation for
    Well-Endowed Rings and Space-Bounded Probabilistic Machines,'' {\it
    Information and Control,} 58 (1983), 113-136.
\bibitem[Bra96]{Bradfield}J.~Bradfield, ``On the Expressivity of the Modal
  Mu-Calculus,'' \stacs (1996).
\bibitem[B\"uc60]{Buchi} R.~B\"uchi, ``Weak Second-Order Arithmetic and
Finite Automata,'' {\it Zeit. Math. Logik. Grund. Math. 6} (1960), 66-92.
\bibitem[CFI92]{CFI}J.-Y.~Cai, M.~F\"urer, N.~Immerman, ``An Optimal Lower Bound on the Number
    of Variables for Graph Identification,'' {\it Combinatorica} { 12}
    (4) (1992) 389-410.
\bibitem[CH80a]{CH80a}  Ashok Chandra and David Harel, ``Computable Queries for
   Relational Databases,'' {\it JCSS} 21(2) (1980), 156-178.
\bibitem[CH80b]{CH80b}  Ashok Chandra and David Harel, ``Structure and Complexity of
    Relational Queries,'' \focs (1980), 333-347. Also appeared in a revised
    as [CH82]
\bibitem[CH82]{CH}A.~Chandra and D.~Harel, ``Structure and Complexity of
    Relational Queries,''  {\it JCSS} 25 (1982), 99-128.
\bibitem[CKS81]{CKS}A.~Chandra, D.~Kozen, and L.~Stockmeyer, 
    ``Alternation,'' {\it JACM,} { 28}, No. 1, (1981), 114-133.
\bibitem[CSV84]{CSV}  A.~Chandra, L.~Stockmeyer and U.~Vishkin, ``Constant
    Depth Reducibility,'' {\it  SIAM J. of Comp.} { 13}, No. 2, 1984, 
    (423-439).
\bibitem[CE81]{Clarke-Emerson}
E.~Clarke and E.A.~Emerson, ``Design and Synthesis of Synchronization
 Skeletons Using Branching 
  Time Temporal Logic,'' in {\em Proc. Workshop on Logic of Programs}, LNCS
  131, 1981, Springer-Verlag, 52-71. 
\bibitem[Coh66]{Cohen} P.~Cohen, {\it Set Theory and the Continuum
  Hypothesis,} 1966, Benjamin.
\bibitem[Co88]{Compton-survey}K.~Compton, ``0-1 laws in logic and
  combinatorics,'' in {\it NATO Adv.\ Study Inst.\ on Algorithms and Order},
  I.~Rival, editor, 1988, D.~Reidel, 353--383.
\bibitem[Coo71]{Cook sat} S.~Cook, ``The Complexity of Theorem
    Proving Procedures,'' {\it Proc. Third Annual ACM STOC Symp.}
    (1971), 151-158.
\bibitem[Coo85]{Cook}  S.~Cook, ``A Taxonomy of Problems with
    Fast Parallel Algorithms,'' {\it Information and Control}
    { 64} (1985), 2-22.
\bibitem[Cop94]{Coppersmith} D.~Coppersmith, ``A Left Coset Composed of
$n$-cycles,'' Research Report RC19511 IBM (1994).
\bibitem[Cou90]{Courcelle-th-ref}B.~Courcelle, ``The Monadic Second-Order
Logic of GraphsI: Recognizable Sets of Finite Graphs,'' \ic 85 (1990), 12 -
75.
\bibitem[Cou97]{Courcelle}B.~Courcelle, ``On the Expression of Graph
Properties in Some Fragments of Monadic Second-Order Logic,'' in
    {\it Descriptive Complexity and Finite Models,} N.~Immerman and
    Ph.~Kolaitis, eds., 1997, American Mathematical Society, 33 - 62.
\bibitem[Da84]{Dahlhaus sat}E.~Dahlhaus, ``Reduction
   to NP-Complete Problems by Interpretations,'' in {\it Logic and Machines: 
   Decision Problems and Complexity,} B\"orger, R\"odding, and Hasenjaeger eds.,
    Lecture Notes In Computer Science 171, Springer-Verlag (1984),  357-365.
\bibitem[Daw93]{Dawar-thesis}
  A.~Dawar, ``Feasible Computation Through Model
  Theory,'' PhD Dissertation, University of Pennsylvania (1993).
\bibitem[DGH98]{DGH}A.~Dawar, G.~Gottlob, L.~Hella, ``Capturing Relativized
Complexity Classes without Order,'' to appear in {\it Mathematical Logic Quarterly}.
\bibitem[DH95]{Dawar-Hella}Anuj Dawar and Lauri Hella, ``The Expressive
  Power of Finitely Many Generalized Quantifiers,'' \ic 123(2) (1995),
  172-184.
\bibitem[DDLW98]{DLW-bit}A.~Dawar, K.~Doets, S.~Lindell, and S.~Weinstein, ``Elementary
  Properties of the Finite Ranks,'' {/it Mathematical Logic Quarterly} 44 (1998), 349-353.
\bibitem[DLW95]{DLW}A.~Dawar, S.~Lindell, and S.~Weinstein, ``Infinitary
logic and inductive definability over finite structures,'' \ic, 119 (1995), 160-175. 
\bibitem[DRR05] Anuj Dawar, David Richerby, and Benjamin Rossman,
  ``Choiceless Polynomial Time, Counting and the Cai-Fuerer-Immerman
  Graphs'', Proceedings of the 12th Workshop on Logic, Language,
  Information and Computation (2005), 13-24. 
\bibitem[DGS86]{DGS}L.~Denenberg, Y.~Gurevich and S.~Shelah,  "Definability by
  Constant-Depth Polynomial-Size Circuits",  {\it Information and Control}
    { 70} (1986), 216-240.
\bibitem[deR84]{de Rougemont} M.~de Rougemont, ``Uniform Definability on Finite Structures
    with Successor,'' {\it 16th ACM STOC Symp.}, (1984), 409-417.
\bibitem[DL98]{Diffie-Landau}W.~Diffie and S.~ Landau, {\it Privacy on the Line: the Politics
  of Wiretapping and Encryption,} MIT Press, 1998.
\bibitem[DS95]{DS-pods}G.~Dong, J.~Su, ``Space-Bounded
  FOIES,'' \pods (1995), 139 -150.
\bibitem[DS93]{Dong-Su}
  G.~Dong, J.~Su,  ``Incremental and Decremental Evaluation of Transitive
  Closure by First-Order Queries,''  \ic, 120(1) (1995), 101-106.
  Preliminary results presented at the 1993 Australian Computer Science
  Conference. 
\bibitem[EF95]{EF} H.-D.~Ebbinghaus, J.~Flum, {\it Finite Model Theory}
1995, Springer 1995.   
\bibitem[EFT94]{EFT} H.-D.~Ebbinghaus, J.~Flum, and W.~Thomas, {\it
Mathematical Logic}, 2nd edition 1994, Springer-Verlag.
\bibitem[Ehr61]{Ehrenfeucht} A.~Ehrenfeucht, ``An Application of Games to the Completeness Problem
    for Formalized Theories,'' Fund. Math. 49 (1961), 129-141.
\bibitem[End72]{Enderton}  H.~Enderton, {\it A Mathematical Introduction to Logic,} 
    Academic Press, 1972.
\bibitem[ES74]{Erdos-Spencer} P.~Erd\H{o}s and J.~Spencer, {\it
    Probabilistic Methods in Combinatorics,} 1974, Academic Press.
\bibitem[Ete95]{Etessami}K.~Etessami, ``Counting Quantifiers, Successor
  Relations, and Logarithmic Space,'' \strc (1995), 2-11.
\bibitem[Ete95a]{Etessami-thesis}K.~Etessami, ``Ordering and Descriptive
  Complexity'' Ph.D. thesis, 1995,  UMass, Amherst. 
\bibitem[EI95]{reach}K.~Etessami and N.~Immerman, ``Reachability and the
  Power of Local Ordering,'' \tcs 148(2) (1995), 261-279.
\bibitem[EI95a]{trees}K.~Etessami and N.~Immerman, ``Tree Canonization and
  Transitive Closure,'' to appear in \ic. A preliminary version appeared in \lics (1995), 331-341.
\bibitem[Fag73]{Fagin-thesis} R.~Fagin, ``Contributions to the Model Theory
    of Finite Structures'', Ph.D.~Thesis (1973), U.~C.~Berkeley.
\bibitem[Fag74]{Fagin}  R.~Fagin, ``Generalized First-Order Spectra and
    Polynomial-Time Recognizable Sets,'' in {\it Complexity
    of Computation,} (ed. R.~Karp), {\it SIAM-AMS Proc. 7}
    (1974), 27-41.
\bibitem[Fag75]{Fagin connect} R.~Fagin, ``Monadic generalized spectra,'' {\it Zeitschr.  
    f. math. Logik und Grundlagen d. Math.}   21 (1975),  89-96.
\bibitem[Fag76]{Fagin probability}R.~Fagin, ``Probabilities on Finite
    Models,'' {\it J. Symbol. Logic} { 41}, No. 1 (1976),50-58.
\bibitem[Fag93]{fagin-survey}R.~Fagin, ``Finite-Model Theory --
    a Personal Perspective,'' \tcs 116 (1993), 3-31.
\bibitem[Fag97]{Fagin-games}  R.~Fagin, ``Easier Ways to Win Logical
Games,'' in
    {\it Descriptive Complexity and Finite Models,} N.~Immerman and
    Ph.~Kolaitis, eds., 1997, American Mathematical Society, 1 - 32.
\bibitem[FSV95]{FSV}R.~Fagin, L.~Stockmeyer, and M.Y.~Vardi, ``On
    monadic NP vs. monadic co-NP,'' \ic 120(1) (1995), 78-92.
\bibitem[FV98]{Feder-Vardi}T.~Feder and M.Y.~Vardi, ``The Computational
     Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study
     through Datalog and Group Theory,'' (1998).
\bibitem[Fel50]{Feller} W.~Feller, {\it An Introduction to Probability
  Theory and Its Applications,} Vol. 1, 1950, John Wiley, New York.
\bibitem[FRW84]{FRW} F.~Fich, Prabhakar Ragde, and, Avi Wigderson
    (1984), ``Relations Between Concurrent-Write Models of Parallel
    Computation,'' {\it Third ACM Symp. on Principles of
    Distributed Computing,} 179-189.
\bibitem[FW78]{FortuneWyllie}  S.~Fortune and J.~Wyllie, ``Parallelism in Random Access Machines,''
  \stoc (1978), 114-118.
\bibitem[Fra54]{Fraisse} R.~Fra\"{\i}ss\'e, ``Sur les Classifications des Systems de Relations,'' Publ. Sci.
    Univ. Alger I (1954). 
\bibitem[Fur87]{Furer}M.~F\"urer, ``A Counterexample In Graph Isomorphism
    Testing -- Extended Abstract,'' manuscript (October, 1987).
\bibitem[FSS84]{FSS}  M.~Furst, J.B.~Saxe, and M.~Sipser, ``Parity, 
    Circuits, and the Polynomial-Time Hierarchy,'' 
    {\it Math. Systems Theory}, 17 (1984), 13-27.
\bibitem[Gab81]{Gabbay}D.~Gabbay, ``Expressive Functional Completeness in
    Tense Logic,'' in: {\it Aspects of Philosophical Logic,} 1981, ed. Monnich,
    D. Reidel, Dordrecht, 91-117.
\bibitem[Gai81]{Gaifman} H.~Gaifman, ``On Local and Non-Local Properties,''  {\it Proc. Herbrand
Logic Colloq.} (1981), 105-135.
\bibitem[GH97]{Gire}F.~Gire and H.~Hoang,  ``An Extension of Fixpoint
  Logic with a Symmetry-Based Choice Construct,'' \ic 144(1) (1998), 40-65.
\bibitem[G\"od30]{Godel-completeness}G\"odel, K., ``Die Vollst\"andigkeit der Axiome des Logischen
Funktionenkalk\"uls,'' {\it Monatshefte f\"ur Mathematik und Physik 37} (1930), 349 - 360, (English
translation in \cite{vH}).
\bibitem[Go82]{Go82}  L.~Goldschlager, "A Universal Interconnection Pattern for Parallel
    Computers," JACM, October 1982.
\bibitem[Go77]{Goldschlager} L.~Goldschlager, ``The Monotone and
   Planar Circuit Value Problems are Log Space Complete for
   P,'' {\it SIGACT News} 9(2) (1977).
\bibitem[Gr\"a92]{Gradel} E.~Gr\"adel, ``Capturing
  Complexity Classes by Fragments of Second Order Logic,''
  \tcs 101 (1992), 35-57.
\bibitem[Gr\"a92a]{Gradel-TC}E.~Gr\"adel, ``On Transitive Closure Logic,'' {\it
Computer Science Logic} (1992), LNCS, Springer, 149--163.
\bibitem[GM95]{GM}E.~Gr\"{a}del and G.~McColm, ``On 
  the Power of Deterministic Transitive Closures,''  \ic 119 (1995), 129-135.
\bibitem[GM96]{GM96}E.~Gr\"{a}del and G.~McColm, ``Hierarchies in Transitive Closure Logic, Stratified 
  Datalog and Infinitary Logic,'' {\it Annals of Pure and Applied Logic 77} (1996), 166--199.
\bibitem[GO93]{Gradel-Otto}E.~Gr\"{a}del and M.~Otto, ``Inductive
Definability with Counting on Finite Structures,'' {\em Computer Science
Logic} 1993, LNCS 702, Springer, 231--247.
\bibitem[Gra84]{Grandjean}  E.~Grandjean, ``The Spectra of First-Order Sentences and
    Computational Complexity,'' { SIAM J. of Comp.} { 13}, No. 2 (1984),
    356-373.
\bibitem[Gra85]{Grandjean2}E.~Grandjean, ``Universal quantifiers and 
    time complexity of Random Access Machines,'' {\it  Math. Syst. Th.} (1985), 171-187.
\bibitem[Gra89]{Grandjean3}E.~Grandjean, ``First-order spectra with one variable,'' 
    to appear in {\it J. Comput. Syst. Sci.}
\bibitem[Gro95]{Grohe-complete} M.~Grohe, ``Complete Problems for Fixed-Point
Logics,'' \jsl 60 (1995), 517-527.
\bibitem[Gro96]{Grohe-equivalence} M.~Grohe, ``Equivalence in Finite-Variable
Logics is Complete for Polynomial Time,'' \focs (1996).
\bibitem[Gro96a]{Grohe-arity} M.~Grohe, ``Arity Hierarchies,'' {\it Annals
of Pure and Applied Logic} 82 (1996), 103-163.
\bibitem[Gro97]{Grohe-McArthur}M.~Grohe, ``Large Finite Structures With
  Few $L^k$-Types,'' \lics (1997).
\bibitem[GS98]{Grohe-Schwentick}M. Grohe and T. Schwentick, ``Locality of
order-invariant first-order forumlas. MFCS'98, 437-445.  Full version to
appear in ACM TOCL. 
\bibitem[Gro97a]{Grohe-Lk-canonization}M.~Grohe, ``Canonization for
  $L^k$-Invariants is Hard,'' {\it Annual Conference of
  the European Association for Computer Science Logic} (1997), M.~Nielsen and
  W.~Thomas, eds., 185-200.
\bibitem[Gro97b]{Grohe-planar}M.~Grohe, ``Fixed-Point Logics on Planar
   Graphs,'' manuscript (1997).
\bibitem[Gur83]{Gurevich-logspace} Y.~Gurevich, "Algebras of
feasible functions,"  \focs (1983), 210-214.
\bibitem[Gur84]{Gurevich} Y.~Gurevich, ``Toward Logic Tailored for 
    Computational Complexity,'' {\it Computation and Proof
    Theory} (M.M. Richter et. al., eds.). Springer-Verlag
    Lecture Notes in Math. 1104 (1984), 175-216.
\bibitem[Gur88]{Gurevich-challenge}Y.~Gurevich, ``Logic and the Challenge of 
    Computer Science,'' in {\it Current Trends in Theoretical Computer
    Science,} ed. E.~B\"orger, Computer Science Press
    (1988), 1-57.
\bibitem[Gur91]{evolvingAlgebra}Y.~Gurevich, `` Evolving Algebras: A
  Tutorial Introduction,'' {\it Bulletin of EATCS, 43} (1991), 264-284.
\bibitem[Gur93]{lipari-guide}Y.~Gurevich, "Evolving Algebras 1993: Lipari
  Guide", {\it Specification and Validation Methods,} ed. E. B\"orger, Oxford
  University Press, 1995, 9--36.  
\bibitem[GS85]{GS-IFP}  Y.~Gurevich and S.~Shelah, ``Fixed-Point Extensions of
    First-Order Logic,'' {\it Annals of Pure and Applied Logic 32 } (1986),
    265--280.
\bibitem[GS96]{GS-rigid} Y.~Gurevich and S.~Shelah, ``On Finite Rigid
Structures,'' \jsl 61(2) (1996), 549 - 562.
\bibitem[HP93]{Hajek-Pudlak} P.~Hajek and P.~Pudlak, {\it Metamathematics of
First-Order Arithmetic,} 1993, Springer, Berlin.
\bibitem[Ha65]{Hanf} W.~Hanf, ``Model-Theoretic Methods in the Study of
    Elementary Logic,'' in J.~Addison, L.~Henkin, and A.~Tarski, eds., {\it
    The Theory of Models,} 1965, North Holland, 105-135.
\bibitem[HIM78]{HIM}J.~Hartmanis, N.~Immerman, and S.~Mahaney, ``One-Way Log
   Tape Reductions,'' \focs (1978), 65-72.
\bibitem[Has86]{Hastad} J.~Hastad, ``Almost Optimal Lower Bounds for Small Depth Circuits,'' 
    {\it 18th ACM STOC Symp.,} (1986), 6-20.
\bibitem[He96]{Hella}L.~Hella, ``Logical Hierarchies in PTIME,'' \ic 129(1)
(1996), 1-19.
\bibitem[HKL97]{HKL} L.~Hella, Ph.~Kolaitis, and K.~Luosto,
 ``How to Define a Linear Order on Finite Models,''\apal 87 (1997), 241-267.
\bibitem[HKL96]{HKL96} L.~Hella, Ph.~Kolaitis, and K.~Luosto,
``Almost Everywhere Equivalence of Logics in Finite Model Theory,'' \bsl
2(4) (1996), 422 - 443.
\bibitem[HLN97]{HLN} L.~Hella, L.~Libkin, and  J.~Nurmonen, ``Notions of
  locality and their logical characterizations over finite models,''
  manuscript.
\bibitem{HI} W.~Hesse and N.~Immerman, ``Complete problems for Dynamic
Complexity Classes,'' \lics (2002), 313-322.
\bibitem[Hil85]{Hillis}D.~Hillis, {\it The Connection Machine} 1985,  MIT Press.
\bibitem[Hon82]{Hong cycle} J.-W.~Hong, ``On Some Deterministic Space Complexity Problems,''
    {\it SIAM J. Comput.} { 11} (1982), 591-601.
\bibitem[Ho86]{Hong}J.-W.~Hong, {\it Computation: Computability,
Similarity, and Duality,} 1986, John Wiley \& Sons.
\bibitem[HT72]{HT}  J.~Hopcroft and R.~Tarjan, ``Isomorphism of Planar
    Graphs,'' in {\it Complexity of Computer Computations,} R.~Miller and
    J.W.~Thatcher, eds., (1972), Plenum Press, 131-152.
\bibitem[HU79]{HU} J.~Hopcroft and J.~Ullman, {\it Introdution to Automata Theory,
    Languages, and Computation,} Addison-Wesley (1979).
\bibitem[I79]{Number of Quantifiers}  N.~Immerman, ``Length of
    Predicate Calculus Formulas as a New Complexity 
    Measure,'' {\it 20th IEEE FOCS Symp.} (1979), 337-347.  Revised
    version:  ``Number of Quantifiers is Better than Number 
    of Tape Cells,'' {\it  JCSS} 22(3), June 1981, 65-72.
\bibitem[I80]{bounds}  N.~Immerman, ``Upper and Lower Bounds for First Order
    Expressibility,''{\it 21st IEEE FOCS Symp.} (1980), 74-82. Revised
    version:  {\it JCSS} 25(1) (1982), 76-98. 
\bibitem[I82]{queries}  N.~Immerman, ``Relational Queries Computable in Polynomial
    Time,'' {\it 14th ACM STOC Symp.} (1982), 147-152.  Revised version:
    {\it Information and Control,} {68} (1986), 86-104. 
\bibitem[I83]{capture}  N.~Immerman, ``Languages Which 
    Capture Complexity Classes,''  {\it 15th ACM STOC Symp.} (1983),
    347-354.  Revised version: ``Languages That Capture Complexity
    Classes,'' {\it SIAM J. Comput.} 16(4)  (1987), 760-778. 
\bibitem[I87]{expo} N.~Immerman, ``Expressibility as a Complexity Measure: Results
    and Directions,'' {\it  Second Structure in Complexity Theory Conf.} (1987), 194-202.
\bibitem[I88]{space} N.~Immerman, ``Nondeterministic Space is Closed 
    Under Complementation,'' {\it SIAM J. Comput.} 17(5) (1988), 935-938.
    Also appeared in {\it  Third Structure in Complexity Theory 
    Conf.} (1988), 112-115.
\bibitem[I89]{ams} N.~Immerman, ``Descriptive and Computational Complexity,''in
    {\it Computational Complexity Theory,} ed. J.~Hartmanis, Lecture Notes
    for AMS Short Course on Computational Complexity Theory, {\it
    Proc. Symp.  in Applied Math.} 38, American Mathematical Society
    (1989), 75-91.
\bibitem[I89a]{parallel} N.~Immerman, ``Expressibility and 
    Parallel Complexity,'' {\it SIAM J. of Comput.} 18  (1989), 625-638.
\bibitem[I91]{vark}N.~Immerman, ``DSPACE$[n^k]\; =\; $VAR$[k+1]$,''
{\it Sixth IEEE Structure in Complexity Theory Symp.} (July,
1991), 334-340.
\bibitem[IKL95]{fmt tutorial}N.~Immerman, Ph.~Kolaitis, and J.~Lynch, ``A
    Tutorial on Finite Model Theory,'' DIMACS, August, 1995.
\bibitem[IK87]{IK} N.~Immerman and D.~Kozen, ``Definablitity with Bounded Number
    of Bound Variables,'' {\it Second LICS Symp.} (1987), 236-244.
\bibitem[IL95]{mult}N.~Immerman, S.~Landau, ``The Complexity of Iterated
    Multiplication,'' \ic 116(1) (1995), 103-116.
\bibitem[IL90]{canon} N.~Immerman and E.~Lander, ``Describing Graphs: A First-Order
    Approach to Graph Canonization,'' in {\it
    Complexity Theory Retrospective,} Alan Selman, ed., 
    Springer-Verlag (1990), 59-81.
\bibitem[IPS96]{srl}N.~Immerman, S.~Patnaik and  D.~Stemple, ``The
  Expressiveness of a Family of Finite Set Languages,'' {\em Theoretical
  Computer Science} 155(1) (1996), 111-140.  A preliminary version appeared in 
  {\it Tenth ACM Symposium on Principles of Database
  Systems} (1991), 37-52.
\bibitem[IV97]{IV}N.~Immerman and M.Y.~Vardi, ``Model Checking and Transitive
  Closure Logic,'' {\em Proc. 9th Int'l Conf. on Computer-Aided
  Verification} (1997), Lecture Notes in Computer Science, Springer-Verlag,
  291 - 302.
\bibitem[JL77]{JL}N.~Jones and W.~Laaser, ``Complete Problems for
    Deterministic Polynomial Time,'' \tcs 3 (1977), 105-117.
\bibitem[JLL76]{JLL}N.~Jones, E.~Lien and W.~Laaser, ``New Problems
Complete for Nondeterministic Logspace,'' \mst 10 (1976), 1-17.
\bibitem[JS74]{JS} N.~Jones and A.~Selman, ``Turing Machines and the Spectra
    of First-Order Formulas,'' {\it J. Symbolic Logic} { 39} (1974), 
    139-150.
\bibitem[Ka79]{Karp-parity} R.~Karp, ``Probabilistic Analysis of a
  Canonical Numbering Algorithm for Graphs,''   {\it Relations between combinatorics
  and other parts of mathematics,}  Proceedings of Symposia in Pure
  Mathematics 34, 1979, American Mathematical Society, 365 - 378.
\bibitem[KL82]{Karp-Lipton}R.~Karp and R.~Lipton, ``Turing Machines That
 Take Advice,'' {\it Ensiegn. Math.} 28 (1982), 192-209.
\bibitem[KV95]{KV} Ph.~Kolaitis and J.~V\"a\"an\"anen, ``Generalized
    Quantifiers and Pebble Games on Finite Structures,'' {\it Annals of Pure
   and Applied Logic}, 74(1) (1995), 23--75.  
\bibitem[KV98]{KV-constraint} Ph.~Kolaitis and M.Y.~Vardi, ``Conjunctive-Query Containment 
	and Constraint Satisfaction,'' \pods (1998).
\bibitem[KV92a]{Kolaitis-Vardi}Ph.~Kolaitis and M.Y.~Vardi, ``0-1 Laws
   for Fragments of Second-Order Logic: an Overview,'' in Y.~Moschovakis,
   editor, {\em Logic From Computer Science} 1992, Springer-Verlag,
   265--286.
\bibitem[Ku87]{K} L.~Ku\v{c}era, ``Canonical Labeling of Regular Graphs in 
    Linear Average Time,'' {\it 28th IEEE FOCS Symp.} (1987), 271-279.
\bibitem[Kur64]{Kuroda} S.~Kuroda, ``Classes of Languages and Linear-Bounded
    Automata,'' {\it Information and Control} { 7} (1964), 207-233.
\bibitem[Kur94]{Kurshan}R.~Kurshan, {\it Computer-Aided Verification of
 Coordinating Processes,} 1994, Princeton University Press, Princeton, NJ.
\bibitem[L75]{Ladner cvp} R.~Ladner, ``The Circuit Value Problem is
log space complete for P,'' {\it SIGACT News,} 7(1) (1975), 18 -- 20.
\bibitem[LR96]{LR}R.~Lassaigne and M.~de Rougemont, {\it Logique
et Complexit\'e,} 1996, Hermes.
\bibitem[LJK87]{Tompa notes} K.J.~Lange, B.~Jenner, and B.~Kirsig, ``The Logarithmic
    Hierarchy Collapses: $A\Sigma_2^L = A\Pi_2^L$,'' {\it 14th ICALP} (1987).
\bibitem[Lei87]{Leivant87}D.~Leivant, ``Characterization of Complexity Classes in
    Higher-Order Logic,''  {\it  Second Structure in Complexity Theory 
    Conf.} (1987), 203--217.
\Bibitem[Lei89]{Leivant} D.~Leivant, ``Descriptive Characterizations of
    Computational Complexity,'' \jcss 39 (1989), 51-83.
\bibitem[LP81]{LP}H.~Lewis and C.~Papadimitriou, {\it Elements of the
Theory of Computation} 1982, Prentice-Hall.
\bibitem[LP82]{lp-symmetric}  H.~Lewis and C.~Papadimitriou, 
  ``Symmetric Space Bounded Computation,'' {\it Theoret. Comput. Sci.} {
  19} (1982),161-187.  
\bibitem[LV93]{LV} M.~Li and P.~Vit\'anyi, {\it An Introduction to
  Kolmogorov Complexity and its Applications,} 1993, Springer-Verlag, New York.
\bibitem[L04]{Libkin} L.~Libkin, {\it Elements of Finite Model Theory,} 
 2004, Springer.
\bibitem[L92]{Lindell} S.~Lindell, ``A purely logical
characterization of circuit uniformity,'' {\it 7th Structure in
Complexity Theory Conf.} (1992), 185-192.
\bibitem[L]{Lindell bit} S.~Lindell, "How to define exponentiation from
addition and multiplation in first-order logic on finite structures," manuscript.
\bibitem[LG77]{LG}  L.~Lov\'asz and P.~G\'acs, ``Some Remarks on 
    Generalized Spectra,'' {\it Zeitchr. f. math, Logik und 
    Grundlagen d. Math,} 23 (1977), 547-554.
\bibitem[Luk82]{Luks}  E.~Luks, "Isomorphism of Graphs of Bounded Valence Can be Tested in
    Polynomial Time," \jcss 25 (1982), pp. 42-65.
\bibitem[Lyn82]{Lynch}J.~Lynch, ``Complexity Classes and Theories of
    Finite Models,'' {\it  Math. Sys. Theory} { 15} (1982), 127-144.
\bibitem[MP94]{Makowsky-Pnueli} J.~Makowsky, Y.~Pnueli, ``Arity versus
alternation in Second-Order Logic,'' in {\it Logical Foundations of
Computer Science,} A.~Nerode, Y.~Matiyasevich eds., Springer LNCS 813 1994,
240 - 252.
\bibitem[McM93]{McMillan}K.~McMillan, {\it Symbolic Model Checking,} 1993,
  Kluwer.
\bibitem[MP71]{McNaughton-Papert}R.~McNaughton and S.~Papert, {\it
Counter-Free Automata,} 1971, MIT Press, Cambridge, MA.
\bibitem[Man89]{Manber}U.~Manber, {\it Introduction to Algorithms: A
Creative Approach,} Addison-Wesley, (1989).
\bibitem[MT97]{Matz-Thomas} O.~Matz and W.~Thomas, ``The Monadic
Quantifier Alternation Hierarchy Over Graphs is Infinite,'' \lics (1997),  236-244.
\bibitem[MI94]{NP-syntax}J.A.~Medina and N.~Immerman, ``A Syntactic Characterization of
NP-Completeness,'' \lics (1994), 241-250.
\bibitem[MI96]{MI-PCP}J.A.~Medina and N.~Immerman, ``A Generalization of Fagin's
  Theorem,'' \lics (1996), 2 -- 12.
\bibitem[MSV94]{MSVT}P.~Miltersen, S.~Subramanian,
 J.~Vitter, and R.~Tamassia, ``Complexity
 Models for Incremental Computation,'' \tcs (130:1)
 (1994), 203-236.
\bibitem[Mos74]{Moschovakis}  Y.~Moschovakis, {\it Elementary Induction on Abstract
    Structures,} North Holland (1974).
\bibitem[Mos80]{Moschovakis-descriptive}  Y.~Moschovakis, {\it Descriptive set theory,}
1980,   North-Holland Pub. Co., Amsterdam, 637 p.
%\bibitem[Mye83]{Myers} D.~Myers, ``The Random Access Hierarchy,'' 
%    {\it 15th ACM STOC} (1983), 355-364.
\bibitem[NT95]{Nisan-Ta-Shma}N.~Nisan and A.~Ta-Shma, ``Symmetric Logspace is Closed
Under Complement,'' \cjtcs (1995).
\bibitem[O01]{Otto-twoVar} M.~Otto, ``Two Variable first-Order Logic Over
Ordered Domains,'' \jsl 66(2) (2001), 685-702.
\bibitem[Ott96]{Otto} M.~Otto, ``The Expressive Power of Fixed-Point
Logic with Counting,'' \jsl 61(1) (1996), 147 - 176
\bibitem[Ott97]{Otto-book}M.~Otto, {\it  Bounded Variable Logics and
  Counting: A Study in Finite Models,} 1997,
   Lecture Notes in Logic, vol.~9, Springer-Verlag.
\bibitem[Pap94]{Papa} C.~Papadimitriou, {\it Computational
Complexity} 1994, Addison-Wesley.
\bibitem[Pap85]{Papa-P-is-P} C.~Papadimitriou, ``A
  Note on the Expressive Power of Prolog,'' {\it EATCS
  Bulletin 26} (1985), 21-23.
\bibitem[PY]{PY} C.~Papadimitriou and M.~Yannakakis,
 ``Optimization, Approximation, and Complexity Classes,'' \jcss,  43 (1991), 425-440.
\bibitem[PI94]{dynfo}S.~Patnaik and N.~Immerman, ``Dyn-FO: A Parallel,
  Dynamic Complexity Class,'' \jcss 55(2) (1997), 199-209.  A
  preliminary version appeared in \pods (1994), 210-221.  
\bibitem[Poi82]{Poizat}  B.~Poizat, "Deux ou trois choses que je sais de Ln" 
    {\it JSL} { 47} (1982), 641-658.
\bibitem[R96]{Ramalingam}G. Ramalingam {\it Bounded Incremental
  Computation,} 1996, Springer LNCS 1089.
\bibitem[Raz87]{Razborov} A.~Razborov, ``Lower Bounds on the Size
    of Bounded Depth Networks Over a Complete Basis With Logical
    Addition,'' {\it Matematischi Zametki} {41} (1987), 598-607 (in
    Russian).  English translation in {\it Mathematical Notes of the
    Academy of Sciences of the USSR} {41}, 333-338.
\bibitem[Rei87]{Reif} J.~Reif, ``On Threshold Circuits and Polynomial
    Computation,'' {\it Second Annual Structure in Complexity Theory Symp.}
    (1987), 118-123.
\bibitem[Rei05]{Reingold}O.~Reingold, ``Undirected ST-Connectivity in
  Log-Space'', \stoc 2005, 376 - 385.
\bibitem[RS72]{Rodding}D.~R\"odding and H.~Schwichtenberg, ``Bemerkungen
zum Spektralproblem,'' {\it Zeitschrift f\"r math. Logik und Grundlagen der
Mathematik } 18 (1972), 1-12.
\bibitem[Ros82]{Rosenstein}J.~Rosenstein, {\it Linear Orderings,} 1982,
  Academic Press.
\bibitem[Ruz81]{Ruzzo} L.~Ruzzo, ``On Uniform Circuit 
    Complexity,'' {\it  J. Comp. Sys. Sci.,} { 21}, No. 2
    (1981), 365-383.
\bibitem[Sav70]{Savitch} W.~Savitch, ``Relationships Between
    Nondeterministic and Deterministic Tape Complexities,''
    {\it J. Comput. System Sci.} { 4} (1970), 177-192.
\bibitem[Sav73]{Savitch-gap}W.~Savitch, ``Maze Recognizing Automata and 
    Nondeterministic Tape Complexity,'' \jcss 7 (1973), 389-403.
\bibitem[Sch97]{Schweikardt} N.~Schweikardt, ``The Monadic Quantifier
  Alternation Hierarchy over Grids and Pictures,'' {\it Annual Conference of
  the European Association for Computer Science Logic} (1997), M. Nielsen and
  W.~Thomas, eds., 383-397.
\bibitem[Sch94]{Schwentick} T.~Schwentick, ``Graph Connectivity and Monadic
    NP,'' \focs (1994), 614-622.
\bibitem[Sch97a]{Schwentick-padding} T.~Schwentick, ``Padding and the Expressive
  Power of Existential Second-Order Logics,'' {\it Annual Conference of
  the European Association for Computer Science Logic} (1997), M.~Nielsen and
  W.~Thomas, eds., 399-412.
\bibitem[SB98]{Schwentick-Barthelmann}T.~Schwentick and K.~Barthelmann,
  ``Local Normal Forms for First-Order Logic with Applications to Games and
  Automata,'' to appear in \stacs (1998).  
\bibitem[See95]{Seese} D.~Seese, ``FO-Problems and Linear Time
    Computability,'' Tech Report, Institut f\"{ur} Informatik und Formale
    Beschreibungsverfahren, Universit\"at Karlsruhe, Germany (1995).
\bibitem[Sip83]{Sipser-hierarchy}  M.~Sipser, "Borel Sets and Circuit Complexity," 
    {\it 15th Symp. on Theory of Computation} (1983), 61-69.
\bibitem[Smo87]{Smolensky} R.~Smolensky, ``Algebraic Methods in the 
    Theory of Lower Bounds for Boolean Circuit Complexity,'' {\it 19th
    ACM STOC} (1987), 77-82.
\bibitem[Spe93]{Spencer-zero-one}J.~Spencer, ``Zero-One Laws With Variable Probability,''
  \jsl 58 (1993), 1--14.
\bibitem[Ste94]{Stewart projection}I.~Stewart, ``On completeness for NP via projection
translations,'' Math. Syst. Theory 27 (1994), 125--157.
\bibitem[Ste91]{Stewart}
  I.~Stewart, ``Comparing the Expressibility of Languages
  Formed Using NP-Complete Operators'', {\it J. Logic and Computation} 1(3) (1991), 305-330.
\bibitem[Sto77]{Stockmeyer}  L.~Stockmeyer, ``The Polynomial-Time 
     Hierarchy,'' {\it Theoretical Comp. Sci.} { 3} (1977), 1-22.
\bibitem[SV84]{SV}  L.~Stockmeyer and U.~Vishkin, ``Simulation of Parallel
    Random Access Machines by Circuits,''  {\it SIAM J. of Comp.} { 13}, 
    No. 2 (1984), 409-422.
\bibitem[Str94]{straubing}H.~Straubing, {\it Finite Automata, Formal Logic,
and Circuit Complexity,} 1994, Birkh\"auser.
\bibitem[Sze88]{Robert} R.~Szelepcs\'enyi, ``The Method of 
    Forced Enumeration for Nondeterministic Automata,'' {\it Acta 
    Informatica} { 26} (1988), 279-284.
\bibitem[Tar36]{Tarski-semantics}  A.~Tarksi, ``Der Wahrheitsbegriff in den
Formalisierten Sprachen,'' {\it Studia Philosophica 1} (1936).
\bibitem[Tar55]{Tarski-Knaster} A.~Tarksi,
``A Lattice-Theoretical Fixpoint Theorem and its Applications,''
{\it Pacific. J. Math.}, 55 (1955), 285-309.
\bibitem[Tho86]{Thomas} S.~Thomas, ``Theories With Finitely Many Models,'' {\it J. Symbolic
    Logic,} { 51}, No. 2 (1986), 374-376.
\bibitem{Thomas} Thomas, Wolfgang, ``An Application of The
Ehrenfeucht-Fra\"{\i}ss\'e Game in Formal Language 
Theory,'' {\it Bull. Soc. Math. France, Mem., 16 (1984), 11-21.
\bibitem[Tra50]{Trahtenbrot} B.~Trahtenbrot, ``The Impossibility of an
Algorithm for the Decision Problem for Finite Domains,'' {\it Doklady
Academii Nauk SSSR}, n.s., vol 70 (1950), 569-572 (in Russian).
\bibitem[Tur84]{Turan}G.~Tur\'an, ``On the Definability of Properites of
Finite Graphs,'' {\it Discrete Math. 49} (1984), 291-302.
\bibitem[TPP97]{Powers} A.~Turk, S.~Probst, and G.~Powers, ``Verification
 of a Chemical Process Leak Test Procedure,'' in {\it Computer Aided
 Verification, 9th International Conf.}, O.~Grumberg, ed. 1997, Springer, 84-94.
\bibitem[Tys97]{Tyszk}J.~Tyszkiewicz, ``The Kolmogorov Expression
Complexity of Logics,'' \ic 135(2) (1997), 113-136.
\bibitem[Vaa99]J.~V\"a\"an\"anen, ed., {\it Generalized Quantifiers and
 Computation,'' Ninth European Summer School in Logic, Language, and
 Information, 1997, Springer LNCS 1754.
\bibitem[Val82]{Valiant}  L.~Valiant, ``Reducibility By Algebraic
Projections,''  
  {\it L'En\-seigne\-ment math\'e\-ma\-tique,} { 28}, 3-4 (1982), 253-68.
\bibitem[vD94]{vanDalen}D.~van Dalen, {\it Logic and Structure, Third
   Edition,} 1994, Springer-Verlag.
\bibitem[vH]{vH}J.~van Heijenoort, {\it From Frege to G\"odel: A Source
Book in Mathematical Logic, 1879 - 1931} 1967, Harvard University Press.
\bibitem[Var82]{Vardi}  M.Y.~Vardi, ``Complexity of Relational Query 
    Languages,'' {\it 14th Symposium on Theory of Computation} (1982), 137-146.
\bibitem[Wei76]{Weisfeiler} B.~Weisfeiler, ed., {\it On Construction and 
    Identification of Graphs,} Lecture Notes in Mathematics 558, Springer,
    1976.
\bibitem[Wra76]{Wrathall} C.~Wrathall, ``Complete Sets and the Polynomial
    Hierarchy,'' {\it Theoret. Comp. Sci.} { 3} (1976).
\bibitem[Yao85]{Yao}  A.~Yao ,``Separating the Polynomial-Time
    Hierarchy by Oracles,'' {\it 26th IEEE Symp. on 
    Foundations of Comp. Sci.} (1985), 1-10.
\end{thebibliography}
\cleardoublepage