\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