@InProceedings(pippenger,
 Author=      "Pippenger, N.",
 Title=	      "On simultaneous resource bounds",
 BookTitle=   "Proc. of 20th FOCS",
 Year=	      "1979",
 Pages=	      "307-311")

@Article{pippenger.fischer,
  author = 	 {N. Pippenger and M. Fischer},
  title = 	 {Relations among complexity measures},
  journal = 	 {Journal of the Association for Computing Machinery},
  year = 	 1979,
  volume =	 26,
  pages =	 {361-381}
}



@Article{tra61,
  author = 	 {B. A. Trakhtenbrot},
  title = 	 {Finite automata and logic of monadic predicates},
  journal = 	 {Doklady Akademii Nauk SSSR},
  year = 	 1961,
  volume =	 140,
  pages =	 {326-329},
  note =	 {In Russian.}
}

@Article{gule84,
  author = 	 {Y. Gurevich and H. Lewis},
  title = 	 {A logic for constant-depth circuits},
  journal = 	 {Information and Control},
  year = 	 1984,
  volume =	 61,
  pages =	 {65-74}
}

@InProceedings{agal96,
  author = 	 {M. Agrawal and E. Allender},
  title = 	 {An isomorphism theorem for circuit complexity},
  booktitle = 	 {Proceedings 11th Computational Complexity},
  year =	 1996,
  publisher =	 {IEEE Computer Society},
  pages =	 {2-11}
}

@InProceedings{heho90,
  author = 	 {L. A. Hemachandra and A. Hoene},
  title = 	 {On sets with efficient implicit membership tests},
  booktitle = 	 {5th Structure in Complexity Theory},
  year =	 1990,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {11-19}
}

@InProceedings{agalda97,
  author = 	 {M. Agrawal and E. Allender and S. Datta},
  title = 	 {On {TC$^0$}, {AC$^0$}, and arithmetic circuits},
  booktitle = 	 {Proceedings 12th Computational Complexity},
  year =	 1997,
  publisher =	 {IEEE Computer Society},
  pages =	 {134-148y}
}

@Book{mei86,
  author = 	 {C. Meinel},
  title = 	 {Modified Branching Programs and Their Computational Power},
  publisher = 	 {Springer Verlag},
  year = 	 1986,
  volume =	 370,
  series =	 {Lecture Notes in Computer Science},
  address =	 {Berlin Heidelberg}
}

@Article{lee59,
  author = 	 {C. Y. Lee},
  title = 	 {Representation of switching functions by binary decision programs},
  journal = 	 {Bell Systems Technical Journal},
  year = 	 1959,
  volume =	 38,
  pages =	 {985-999}
}

@InProceedings{agetal97,
  author = 	 {M. Agrawal and E. Allender and R. Impagliazzo and R. Pitassi and S. Rudich},
  title = 	 {Reducing the complexity of reductions},
  booktitle = 	 {Proceedings 29th Symposium on Theory of Computing},
  year =	 1997,
  publisher =	 {ACM Press},
  pages =	 {XXX-YYY}
}

@article{ajt83,
  author =       {M. Ajtai},
  journal =      {Annals of Pure and Applied Logic},
  pages =        {1-48},
  title =        {{$\Sigma^1_1$} formulae on finite structures},
  volume =       24,
  year =         1983
}

@InProceedings{albeog96,
  author = 	 {E. Allender and R. Beals and M. Ogihara},
  title = 	 {The complexity of matrix rank and feasible systems of linear equations (extended abstract)},
  booktitle = 	 {Proceedings 28th Symposium on Theory of Computing},
  year =	 1996,
  publisher =	 {ACM Press},
  pages =	 {161-167}
}

@InProceedings{algo90,
  author = 	 {E. Allender and V. Gore},
  title = 	 {On strong separations from {AC$^0$}},
  booktitle = 	 {Proceedings 8th Fundmentals of Computation Theory},
  volume =	 529,
  series =	 {Lecture Notes in Computer Science},
  year =	 1991,
  pages =	 {1-15},
  publisher =    {Springer Verlag}
}

@Article{algo91,
  author = 	 {E. Allender and V. Gore},
  title = 	 {Rudimentary reductions revisited},
  journal = 	 {Information Processing Letters},
  year = 	 1991,
  volume =	 40,
  pages =	 {89-95}
}

@Article{algo94,
  author = 	 {E. Allender and V. Gore},
  title = 	 {A uniform circuit lower bound for the permanent},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1994,
  volume =	 23,
  pages =	 {1026-49}
}

@Article{alhe94,
  author = 	 {E. Allender and U. Hertrampf},
  title = 	 {Depth reduction for circuits of unbounded fan-in},
  journal = 	 {Information \& Computation},
  year = 	 1994,
  volume =	 112,
  pages =	 {217-238}
}

@article{alje93,
  author =       {C. \`{A}lvarez and B. Jenner},
  journal =      {Theoretical Computer Science},
  pages =        {3-30},
  title =        {A Very Hard Log Space Counting Class},
  volume =       107,
  year =         1993
}

@Article{all89,
  author = 	 {E. Allender},
  title = 	 {P-uniform circuit complexity},
  journal = 	 {Journal of the Association for Computing Machinery},
  year = 	 1989,
  volume =	 36,
  pages =	 {912-928}
}

@InProceedings{all90,
  author = 	 {E. Allender},
  title = 	 {Oracles versus proof techniques that do not relativize},
  booktitle = 	 {Proceedings 1st International Symposium on Algorithms},
  volume =	 450,
  series =	 {Lecture Notes in Computer Science},
  year =	 1990,
  publisher =	 {Springer Verlag},
  pages =	 {39--52}
}

@Unpublished{all95,
  author = 	 {E. Allender},
  title = 	 {Combinatorial Methods in Complexity Theory},
  note = 	 {Lecture Notes, Rutgers University New Brunswick. Available on the internet at URL http://www.cs.rutgers.edu/$\sim$allender},
  year =	 1995
}

@InProceedings{all96,
  author = 	 {E. Allender},
  title = 	 {A note on uniform circuit lower bounds for the counting hierarchy},
  booktitle = 	 {Proceedings 2nd Computing and Combinatorics Conference},
  volume =	 1090,
  series =	 {Lecture Notes in Computer Science},
  year =	 1996,
  publisher =	 {Springer Verlag},
  pages =	 {127-135}
}

@InProceedings{all96b,
  author = 	 {E. Allender},
  title = 	 {Circuit complexity before the dawn of the new millenium},
  booktitle = 	 {Proceedings 16th Foundations of Software Technology and Theoretical Computer Science},
  volume =	 1180,
  series =	 {Lecture Notes in Computer Science},
  year =	 1996,
  publisher =	 {Springer Verlag},
  pages =	 {1--18}
}

@Article{alwa90,
  author = 	 {E. Allender and K. W. Wagner},
  title = 	 {Counting hierarchies: polynomial time and constant
		  depth circuits},
  journal = 	 {Bulleting of the EATCS},
  year = 	 1990,
  volume =	 40,
  pages =	 {182-194}
}

@InProceedings{amb86,
  author = 	 {K. Ambos-Spies},
  title = 	 {Randomness, relativizations, and polynomial reducibilities},
  booktitle = 	 {Proceedings 1st Structure in Complexity
		  Theory},
  volume =	 223,
  series =	 {Lecture Notes in Computer Science},
  year =	 1986,
  publisher =    {Springer Verlag},		  
  pages =	 {200-207}
}

@InProceedings{arlumo+92,
  author = 	 {S. Arora and C. Lund and R. Motwani and M. Sudan and
		  M. Szegedy},
  title = 	 {Proof verification and the intractability of
		  approximation problems},
  booktitle = 	 {Proceedings 33rd Symposium on the Foundations of
		  Computer Science},
  year =	 1992,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {14-23}
}

@Article{sud78,
  author = 	 {I. H. Sudborough},
  title = 	 {On the tape complexity of deterministic context-free languages},
  journal = 	 {Journal of the ACM},
  year = 	 1978,
  volume =	 25,
  pages =	 {405-414}
}

@PhdThesis{vin91,
  author = 	 {V. Vinay},
  title = 	 {Semi-Unboundedness and Complexity Classes},
  school = 	 {Department of Computer Science and Automation, Indian Institute of Science},
  year = 	 1991,
  address =	 {Bangalore, India}
}

@InProceedings{asbefuru91,
  author = 	 {J. Aspnes and R. Beigel and M. Furst and S. Rudich},
  title = 	 {The expressive power of voting polynomials},
  booktitle = 	 {Proceedings 23rd Symposium on Theory of Computing},
  year =	 1991,
  publisher =    {ACM Press},
  pages =	 {402-409}
}

@InProceedings{bab85,
  author = 	 {L. Babai},
  title = 	 {Trading group theory for randomness},
  booktitle = 	 {Proceedings 17th Symposium on Theory of Computing},
  year =	 1985,
  publisher =	 {ACM Press},
  pages =	 {421-429}
}

@Article{bab87,
  author = 	 {L. Babai},
  title = 	 {Random oracles separate {PSPACE} from the
		  polynomial-time hierarchy},
  journal = 	 {Information Processing Letters},
  year = 	 1987,
  volume =	 26,
  pages =	 {51-53}
}

@InProceedings{bab93,
  author = 	 {L. Babai},
  title = 	 {Transparent (holographic) proofs},
  booktitle = 	 {Proceedings 10th Symposium on Theoretical Aspects of Computer Science},
  volume =	 665,
  series =	 {Lecture Notes in Computer Science},
  year =	 1993,
  publisher =	 {Springer Verlag},
  pages =	 {525-534}
}

@Article{baberu94,
  author = 	 {D. A. Mix Barrington and R. Beigel and S. Rudich},
  title = 	 {Representing boolean functions as polynomials modulo composite numbers},
  journal = 	 {Computational Complexity},
  year = 	 1994,
  volume =	 4,
  pages =	 {367-382}
}

@Book{badiga90,
  author =       {J. L. Balc\'azar and J. D{\'\i}az and J. Gabarr\'o},
  publisher =    {Springer Verlag},
  title =        {Structural Complexity II},
  series =	 {Monographs on Theoretical Computer Science},
  year =         1990,
  address =      {Berlin Heidelberg}
}

@Book{badiga95,
  author =       {J. L. Balc\'azar and J. D{\'\i}az and J. Gabarr\'o},
  publisher =    {Springer Verlag},
  title =        {Structural Complexity I},
  series =	 {Texts in Theoretical Computer Science},
  year =         1995,
  edition =      {2nd},
  address =      {Berlin Heidelberg}
}

@InProceedings{bafolesz91,
  author = 	 {L. Babai and L Fortnow and L. A. Levin and M. Szegedy},
  title = 	 {Checking computations in polylogarithmic time},
  booktitle = 	 {Proceedings 23rd Symposium on Theory of Computing},
  year =	 1991,
  publisher =	 {ACM Press},
  pages =	 {21-32}
}

@InProceedings{bafolu90,
  author = 	 {L. Babai and L. Fortnow and C. Lund},
  title = 	 {Non-deterministic exponential time has two-prover interactive protocols},
  booktitle = 	 {Proceedings 31st Symposium on Foundations of Computer Science},
  year =	 1990,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {16-25}
}

@ARTICLE{bafolu91,
AUTHOR = "Babai, L. and L. Fortnow and C. Lund",
TITLE = "Non-deterministic Exponential Time has Two-Prover Interactive
Protocols",
journal = "Computational Complexity",
YEAR = "1991",
Volume = 1,
number = 1,
pages = "3-40"}

@Unpublished{bai97,
  author = 	 {H. Baier},
  title = 	 {Type-1 probabilistic bounded-error operators},
  note = 	 {Manuscript},
  year =	 1997
}

@InProceedings{baim94,
  author = 	 {D. A. Mix Barrington and N. Immerman},
  title = 	 {Time, hardware, and uniformity},
  booktitle = 	 {Proceedings 9th Structure in Complexity Theory},
  year =	 1994,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {176-185}
}

@Article{baimst90,
  author = 	 {D. A. Mix Barrington and N. Immerman and H. Straubing},
  title = 	 {On uniformity within {NC$^1$}},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1990,
  volume =	 41,
  pages =	 {274-306}
}



@InCollection{baloto92,
  author = 	 {J. L. Balc\'azar and A. Lozano and J. Tor\'an},
  title = 	 {The complexity of algorithmic problems on succinct instances},
  booktitle = 	 {Computer Science},
  publisher =	 {Plenum Press},
  year =	 1992,
  editor =	 {R. Baeza-Yates and U. Manber},
  address =	 {New York}
}

@Article{bar89,
  author = 	 {D. A. Mix Barrington},
  title = 	 {Bounded-width polynomial size branching programs recognize exactly those languages in {NC$^1$}},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1989,
  volume =	 38,
  pages =	 {150-164}
}

@InProceedings{bar92,
  author = 	 {D. A. Mix Barrington},
  title = 	 {Quasipolynomial size circuit classes},
  booktitle = 	 {Proceedings 7th Structure in Complexity Theory},
  year =	 1992,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {86-93}
}

@Article{bath88,
  author = 	 {D. A. Mix Barrington and D. Th\'erien},
  title = 	 {Finite monoids and the fine structure of {NC}$^1$},
  journal = 	 {Journal of the Association of Computing Machinery},
  year = 	 1988,
  volume =	 35,
  pages =	 {941-952}
}

@TechReport{bawa96,
  author = 	 {H. Baier and K. W. Wagner},
  title = 	 {The analytic polynomial-time hierarchy},
  institution =  {Institut f\"ur Informatik},
  year = 	 1996,
  number =	 {148},
  address =	 {Universit\"at W\"urzburg}
}

@TechReport{bawa97,
  author = 	 {H. Baier and K. W. Wagner},
  title = 	 {Bounding queries in the analytical polynomial-time hierarchy},
  institution =  {Institut f\"ur Informatik},
  year =	 1997,
  number =       178,
  address =	 {Universit\"at W\"urzburg}
}

@Article{bawa98,
  author = 	 {H. Baier and K. W. Wagner},
  title = 	 {The analytic polynomial-time hierarchy},
  journal =      {Mathematical Logic Quaterly},
  year = 	 1998,
  volume =       44,
  pages =        {529-544}
}

@Article{bawa98b,
  author = 	 {H. Baier and K. W. Wagner},
  title = 	 {Bounding queries in the analytical polynomial-time hierarchy},
  journal =      {Theoretical Computer Science},
  year = 	 1998,
  volume =       207,
  pages =        {89-104}
}

@InProceedings{bedrlemoth97,
  author = 	 {J. Berman and A. Drisko and F. Lemieux and C. Moore and D. Th\'erien},
  title = 	 {Circuits and expressions with non-associative gates},
  booktitle = 	 {Proceedings 12th Computational Complexity},
  year =	 1996,
  publisher =	 {IEEE Computer Society},
  pages =	 {193-203}
}

@Article{begi81,
  author = 	 {C. Bennett and J. Gill},
  title = 	 {Relative to a random oracle
		  {P$^A$ $\neq$ NP$^A$ $\neq$ coNP$^A$} with probability 1},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1981,
  volume =	 10,
  pages =	 {96-113}
}

@InProceedings{begihe90,
  author = 	 {R. Beigel and J. Gill and U. Hertrampf},
  title = 	 {Counting classes: thresholds, parity, mods, and fewness},
  booktitle = 	 {Proceedings 7th Symposium on Theoretical Aspects of
		  Computer Science},
  volume =	 415,
  series =	 {Lecture Notes in Computer Science},
  year =	 1990,
  publisher =	 {Springer Verlag},
  pages =	 {49-57}
}

@Article{begiso75,
  author = 	 {T. Baker and J. Gill and R. Solovay},
  title = 	 {Relativizations of the {P=NP} problem},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1975,
  volume =	 4,
  pages =	 {431-442}
}

@Article{beha77,
  author = 	 {L. Berman and J. Hartmanis},
  title = 	 {On isomorphism and density of {NP} and other
		  complete sets},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1977,
  volume =	 6,
  pages =	 {305-322}
}

@InProceedings{bei93,
  author = 	 {R. Beigel},
  title = 	 {The polynomial method in circuit complexity},
  booktitle = 	 {Proceedings 8th Structure in Complexity Theory},
  year =	 1993,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {82-95},
  note =	 {Revised version, 1995.}
}

@Article{bei94,
  author = 	 {R. Beigel},
  title = 	 {Perceptrons, {$\PP$}, and the polynomial hierarchy},
  journal = 	 {Computational Complexity},
  year = 	 1994,
  volume =	 4,
  pages =	 {339-349}
}

@Article{belemc93,
  author = 	 {F. B{\'e}dard and F. Lemieux and P. McKenzie},
  title = 	 {Extensions to {Barrington's} {M}-program model},
  journal = 	 {Theoretical Computer Science},
  year = 	 1993,
  volume =	 107,
  pages =	 {31-61}
}

@InProceedings{bemc92,
  author = 	 {M. Beaudry and P. McKenzie},
  title = 	 {Circuits, matrices, and nonassociative computation},
  booktitle = 	 {Proceedings 7th Structure in Complexity Theory},
  year =	 1992,
  publisher =	 {IEEE Computer Society},
  pages =	 {94-106}
}

@Book{ber79,
  author = 	 {J. Berstel},
  title = 	 {Transductions and Context-Free Languages},
  publisher = 	 {Teubner},
  year = 	 1979,
  volume =	 38,
  series =	 {Leitf\"aden der angewandten Mathematik und Mechanik LAMM}
}

@InProceedings{beresp91,
  author = 	 {R. Beigel and N. Reingold and D. Spielman},
  title = 	 {{PP} is closed under intersection},
  booktitle = 	 {Proceedings 23rd Symposium on Theory of Computing},
  year =	 1991,
  publisher =	 {ACM Press},
  pages =	 {1-9}
}

@InProceedings{beresp91b,
  author = 	 {R. Beigel and N. Reingold and D. Spielman},
  title = 	 {The perceptron strikes back},
  booktitle = 	 {Proceedings 6th Structure in Complexity Theory},
  year =	 1991,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {286-291}
}

@Article{beta94,
  author = 	 {R. Beigel and J. Tarui},
  title = 	 {On {ACC}},
  journal = 	 {Computational Complexity},
  year = 	 1994,
  volume =	 4,
  pages =	 {350-366},
  note =	 {Special issue on circuit complexity}
}

@InProceedings{beul97,
  author = 	 {C. Berg and S. Ulfberg},
  title = 	 {A lower bound for perceptrons and an oracle separation of the {$\PP^{\PH}$} hierarchy},
  booktitle = 	 {Proceedings 12th Conference on Computational Complexity},
  year =	 1997,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {165-172}
}

@Article{blgu82,
  author = 	 {A. Blass and Y. Gurevich},
  title = 	 {On the unique satisfiability problem},
  journal = 	 {Information and Control},
  year = 	 1982,
  volume =	 82,
  pages =	 {80-88}
}

@Article{blgu86,
  author = 	 {A.Blass and Y. Gurevich},
  title = 	 {Henkin quantifiers and complete problems},
  journal = 	 {Annals of Pure and Applied Logic},
  year = 	 1986,
  volume =	 32,
  pages =	 {1-16}
}

@Article{blu84,
  author = 	 {N. Blum},
  title = 	 {A {B}oolean function requiring $3n$ network size},
  journal = 	 {Theoretical Computer Science},
  year = 	 1984,
  volume =	 36,
  pages =	 {59-70}
}

@Article{bocl92,
  author = 	 {M. Ben-Or and R. Cleve},
  title = 	 {Computing algebraic formulas using a constant number of registers},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1992,
  volume =	 21,
  pages =	 {54-58}
}

@Book{bocr94,
  author = 	 {D. P. Bovet and P. Crescenzi},
  title = 	 {Introduction to the Theory of Complexity},
  publisher = 	 {Prentice Hall},
  address =      {London},
  year = 	 1994,
  series =	 {International Series in Computer Science},
}

@InProceedings{bocrsi91,
  author = 	 {D. P. Bovet and P. Crescenzi and R. Silvestri},
  title = 	 {Complexity classes and sparse oracles},
  booktitle = 	 {Proceedings 6th Structure in Complexity Theory},
  year =	 1991,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {102-108}
}

@Article{bocrsi92,
  author = 	 {D. P. Bovet and P. Crescenzi and R. Silvestri},
  title = 	 {A uniform approach to define complexity classes},
  journal = 	 {Theoretical Computer Science},
  year = 	 1992,
  volume =       104,
  pages =        {263-283} 
}

@article{boetal89,
  author =       {A. Borodin and S. A. Cook and P. W. Dymond and W. L. Ruzzo and M. Tompa},
  title =        {{Two} applications of inductive counting for complementation problems},
  journal =      {SIAM Journal on Computing},
  pages =        {559--578},
  volume =       18,
  year =         1989,
  note =         {See Erratum in SIAM J. Comput.~18, 1283}
}

@TechReport{bokust96,
  author = 	 {B. Borchert and D. Kuske and F. Stephan},
  title = 	 {On existentially first-order definable languages and their relation to {NP}},
  institution =  {Institut f\"ur Algebra, Technische Universit\"at Dresden},
  year = 	 1996,
  number =	 {MATH-AL-11-1996}
}

@Article{bola96,
  author = 	 {B. Borchert and A. Lozano},
  title = 	 {Succinct Circuit Representations and 
Leaf Language Classes are Basically the Same Concept},
  journal = 	 {Information Processing Letters},
  year = 	 2996,
  volume =	 58,
  pages =	 {211-215}
}

@Article{bolo96,
  author = 	 {B. Borchert and A. Lozano},
  title = 	 {Succinct circuit representations and leaf language
                  classes are basically the same concept},
  journal = 	 {Information Processing Letters},
  year = 	 1996,
  volume =	 58,
  pages =	 {211-215}
}

@Article{bolose84,
  author = 	 {R. V. Book and T. Long and A. Selman},
  title = 	 {Quantitative relativizations of complexity classes},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1984,
  volume =	 13,
  pages =	 {461-487}
}

@Article{boluma95,
  author = 	 {R. V. Book and J. Lutz and D. Martin},
  title = 	 {The global power of additional queries to random oracles},
  journal = 	 {Information and Computation},
  year = 	 1995,
  volume =	 120,
  pages =	 {49-54}
}

@InProceedings{boluta91,
  author = 	 {R. V. Book and J. Lutz and S. Tang},
  title = 	 {Additional queries to random and pseudorandom oracles},
  booktitle = 	 {Proceedings 17th International Colloquium on
		  Automata, Languages and Programming},
  volume =	 443,
  series =	 {Lecture Notes in Computer Science},
  year =	 1991,
  publisher =	 {Springer Verlag},
  pages =	 {283-293}
}

@Article{boluwa94,
  author = 	 {R. V. Book and J. Lutz and K. W. Wagner},
  title = 	 {An observation on probability versus randomness with
		  applications to complexity classes},
  journal = 	 {Mathematical Systems},
  year = 	 1994,
  volume =	 27,
  pages =	 {201-209}
}

@Article{boma96,
  author = 	 {R. V. Book and E. Mayordomo},
  title = 	 {On the robustness of {Almost-{\cal R}}},
  journal = 	 {R.A.I.R.O. Informatique Th\'eoretique et Applications},
  year = 	 1996,
  note =	 {To appear.}
}

@Article{boo74,
  author = 	 {R. V. Book},
  title = 	 {Tally languages and complexity classes},
  journal = 	 {Information and Control},
  year = 	 1974,
  volume =	 26,
  pages =	 {186-194}
}

@Article{boo81,
  author = 	 {R. V. Book},
  title = 	 {Bounded query machines: On {NP} and {PSPACE}},
  journal = 	 {Theoretical Computer Science},
  year = 	 1981,
  volume =	 15,
  pages =	 {27-39}
}

@InCollection{boo89,
  author = 	 {R. V. Book},
  title = 	 {Restricted relativizations of complexity classes},
  booktitle = 	 {Computational Complexity Theory},
  publisher =	 {American Mathematical Society},
  year =	 1989,
  editor =	 {J. Hartmanis},
  volume =	 38,
  series =	 {Proceedings Symposia in Applied Mathematics},
  pages =	 {47-74}
}

@Article{boo91a,
  author = 	 {R. V. Book},
  title = 	 {On random oracle separations},
  journal = 	 {Information Processing Letters},
  year = 	 1991,
  volume =	 39,
  pages =	 {7-10}
}

@Article{boo91b,
  author = 	 {R. V. Book},
  title = 	 {Some observations on separating complexity classes},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1991,
  volume =	 20,
  pages =	 {246-258}
}

@InProceedings{boo93,
  author =       {R. V. Book},
  title =        {Relativizing complexity classes with random oracles},
  booktitle =    {Proceedings 4th International Symposium on
                  Algorithms and Computation},
  volume =       {762},
  series =       {Springer Lecture Notes in Computer Science},
  year =         1993,
  pages =        {250--258}
}

@Article{boo94a,
  author = 	 {R. V. Book},
  title = 	 {On languages reducible to algorithmically random languages},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1994,
  volume =	 23,
  pages =	 {1275-1282}
}

@Article{boo94b,
  author = 	 {R. V. Book},
  title = 	 {On collapsing the polynomial-time hierarchy},
  journal = 	 {Information Processing Letters},
  year = 	 1994,
  volume =	 52,
  pages =	 {235-237}
}

@Article{bor77,
  author = 	 {A. B. Borodin},
  title = 	 {On relating time and space to size and depth},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1977,
  volume =	 6,
  pages =	 {733-744}
}

@PhdThesis{bor94,
  author = 	 {B. Borchert},
  title = 	 {Predicate classes, promise classes, and the
acceptance power of regular languages},
  school = 	 {Naturwissenschaftlich-Mathematische Fakult\"at, Universit\"at Heidelberg},
  year = 	 1994
}		  
		  	  
@InProceedings{bor94b,
  author = 	 {B. Borchert},
  title = 	 {On the acceptance power of regular languages},
  booktitle =      {Proceedings 11th Symposium on Theoretical Aspects 
		  of Computer Science},
  volume =       775,
  pages =        {449-460},
  series =       {Lecture Notes in Computer Science},
  publisher =    {Springer Verlag},
  year =         1994
}

@InCollection{bosi90,
  author = 	 {R. B. Boppana and M. Sipser},
  title = 	 {The complexity of finite functions},
  booktitle = 	 {Handbook of Theoretical Computer Science},
  publisher = 	 {Elsevier},
  year = 	 1990,
  editor =	 {J. van Leeuwen},
  volume =	 {A},
  pages =	 {757-804}
}

@InProceedings{bosi97,
  author = 	 {B. Borchert and R. Silvestri},
  title = 	 {The general notion of a dot operator},
  booktitle = 	 {Proceedings 12th Conference on Computational Complexity},
  year =	 1997,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {26-44}
}

@InProceedings{bovowa96,
  author = 	 {R. V. Book and H. Vollmer and K. W. Wagner},
  title = 	 {On type-2 probabilistic quantifiers},
  booktitle = 	 {Proceedings 23rd International Colloquium on
		  Automata, Languages and Programming},
  volume =	 {1099},
  series =	 {Lecture Notes in Computer Science},
  publisher =    {Springer Verlag},
  year =	 1996,
  pages =	 {369-380}
}

@Article{bovowa98,
  author = 	 {R. V. Book and H. Vollmer and K. W. Wagner},
  title = 	 {Probabilistic Type 2 operators and {ALMOST}-classes},
  journal =      {Computational Complexity},
  year =         1998,
  volume =       7,
  pages =        {265-289}
}

@Article{becoho86,
  author = 	 {P. W. Beame and S. A. Cook and H. J. Hoover},
  title = 	 {Log depth circuits for division and related problems},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1986,
  volume =	 15,
  pages =	 {994-1003}
}

@Article{bowa96,
  author = 	 {R. V. Book and O. Watanabe},
  title = 	 {On random hard sets for {NP}},
  journal = 	 {Information and Computation},
  year = 	 1996,
  volume =	 125,
  pages =	 {70-76}
}

@Article{bowr81,
  author = 	 {R. V. Book and C. Wrathall},
  title = 	 {Bounded query machines: On {NP()} and {NPQUERY()}},
  journal = 	 {Theoretical Computer Science},
  year = 	 1981,
  volume =	 15,
  pages =	 {41-50}
}

@InProceedings{buni95,
  author = 	 {G. Buntrock and G. Niemann},
  title = 	 {On weak growing context-sensitive grammars},
  booktitle = 	 {Proceedings 2nd Latin American Symposium on
		  Theoretical Informatics},
  volume =	 911,
  series =	 {Springer Lecture Notes in Computer Science},
  year =	 1995,
  pages =	 {180-194}
}

@misc{bur89,
  author =       {H.-J. Burtschick},
  howpublished = {Diplomarbeit},
  school =       {TU - Berlin},   
  title =        {Vergleich von logarithmischer {P}latzbschr\"ankung 
		  und polynomieller {Z}eit\-beschr\"ankung f\"ur 
		  {K}onstruktionsprobleme und {B}elegmengen},
  year =         1989
}

@misc{bur92,
  author =       {H.-J. Burtschick},
  howpublished = {Unpublished Notes},
  key =          {sparta},
  title =        {{D}okumentation der Ergebnisse des Arbeitstreffens 
		  Komplexit{\"a}tstheorie in Georgenthal/{T}h{\"u}r.  
		  vom 24.2.1991-1.3.1991},
  year =         1992
}

@techreport{bur94,
  author =       {H.-J. Burtschick},
  institution =  {TU Berlin},
  number =       {94-39},
  title =        {Comparing counting classes for logspace, one-way 
		  logspace, logtime, and first-order},
  type =         {Forschungsberichte des Fachbereichs Informatik},
  year =         1995
}

@InProceedings{bur95,
  author =       "H.-J. Burtschick",
  title =        "Comparing Counting Classes for Logspace, One-Way
                 Logspace, and First-Order",
  booktitle =    "Proceedings 20th Symposium on Mathematical 
                 Foundations of Computer Science",
  pages =        "139-148",
  year =         "1995",
  note =         "Vol. 969 of {\it Lecture Notes in Computer Science},
                 Springer Verlag, Berlin",
}

@PhdThesis{bur96,
  author = 	 {H. J. Burtschick},
  title = 	 {Berechnungs- und Beschreibungskomplexit\"at von
                  Z\"ahl\-funktionen und Lindstr\"omquantoren},
  school = 	 {Fachbereich Informatik, TU-Berlin},
  year = 	 1996
}

@inproceedings{bus87,
  author =       {S. R. Buss},
  booktitle =    {Proceedings 19th Symposium on Theory of Computing},
  pages =        {123-131},
  title =        {The {B}oolean  formula value problem is in {ALOGTIME}},
  publisher =    {ACM Press},
  year =         1987
}

@Article{bus88,
  author = 	 {J. F. Buss},
  title = 	 {Relativized Alternation and Space-Bounded Computation},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1988,
  volume =	 36,
  pages =	 {351-278}
}

@TechReport{buvo96,
  author = 	 {H.-J. Burtschick and H. Vollmer},
  title = 	 {Lindstr\"om quantifiers and leaf language definability},
  institution =  {Electronic Colloquium on Computational Complexity},
  year = 	 1996,
  number =	 {96-005},
  note =	 {Submitted for publication}
}
@Article{cach95,
  author = 	 {L. Cai and J. Chen},
  title = 	 {On input read-modes of alternating Turing machines},
  journal = 	 {Theoretical Computer Science},
  year = 	 1995,
  volume =	 148,
  pages =	 {33-55}
}

@Article{cafu91,
  author = 	 {J.-Y. Cai and M. Furst},
  title = 	 {{PSPACE} survives constand-width bottlenecks},
  journal = 	 {International Journal of Foundations of Computer Science},
  year = 	 1991,
  volume =	 2,
  pages =	 {67-76}
}

@Article{caguha+88,
  author = 	 {J.-Y. Cai and T. Gundermann and J. Hartmanis and
                  L. A. Hemachandra and V. Sewelson and K. W. Wagner
                  and G. Wechsung},
  title = 	 {The Boolean hierarchy {I}: Structural Properties},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1988,
  volume =	 17,
  pages =	 {1232-1252}
}

@InProceedings{cahe86,
  author = 	 {J. Y. Cai and L. Hemachandra},
  title = 	 {The {B}oolean hierarchy: hardware over {NP}},
  booktitle = 	 {Proceedings 1st Structure in Complexity Theory},
  volume =	 223,
  series =	 {Lecture Notes in Computer Science},
  year =	 1986,
  publisher =	 {Springer Verlag},
  pages =	 {105-124.}
}

@InProceedings{cai87,
  author = 	 {J. Y. Cai},
  title = 	 {Probability one separation of the boolean hierarchy},
  booktitle = 	 {Proceedings 4th Symposium on Theoretical
		  Aspects of Computer Science},
  volume =	 38,
  series =	 {Lecture Notes in Computer Science},
  publisher =    {Springer Verlag},		  
  year =	 1987,
  pages =	 {148-158}
}

@Article{cai89,
  author = 	 {J. Y. Cai},
  title = 	 {With probability one, a random oracle separates
		  {PSPACE} from the polynomial-time hierarchy},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1989,
  volume =	 38,
  pages =	 {68-85}
}

@InProceedings{camcthvo96,
  author = 	 {H. Caussinus and P. McKenzie and D.
		  Th\'erien and H. Vollmer},
  title = 	 {Nondeterministic {NC$^1$} computation},
  booktitle = 	 {Proceedings 11th Computational Complexity},
  year =	 1996,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {12-21}
}

@Article{chchgo+94,
  author = 	 {R. Chang and B. Chor and O. Goldreich and J. Hartmanis and
		  J. Hastad and D. Ranjan and P. Rohatgi},
  title = 	 {The random oracle hypothesis is false},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1994,
  volume =	 49,
  pages =	 {24-39}
}

@Book{jac85,
  author = 	 {N. Jacobson},
  title = 	 {Basic Algebra},
  publisher = 	 {Freeman and Company},
  year = 	 1985,
  volume =	 {I},
  address =	 {New York}
}

@InProceedings{chkaro91,
  author = 	 {R. Chang and J. Kadin and P. Rohatgi},
  title = 	 {Connections between the complexity of unique
		  satisfiability and the threshold behaviour of
		  randomized reductions},
  booktitle = 	 {Proceedings 6th Structure in Complexity Theory},
  year =	 1991,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {255-269}
}

@Article{chkost81,
  author = 	 {A. K. Chandra and D. Kozen and L. J. Stockmeyer},
  title = 	 {Alternation},
  journal = 	 {Journal of the ACM},
  year = 	 1981,
  volume =	 28,
  pages =	 {114-133}
}

@Article{chstvi84,
  author = 	 {A. K. Chandra and L. Stockmeyer and U. Vishkin},
  title = 	 {Constant depth reducibility},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1984,
  volume =	 13,
  pages =	 {423-439}
}

@Book{clkr97,
  author = 	 {P. Clote and E. Kranakis},
  title = 	 {Boolean Functions and Computation Models},
  publisher = 	 {Springer Verlag},
  year = 	 1998,
  note =	 {To appear}
}

@inproceedings{cogr94,
  author =       {Kevin J. Compton and Erich Gr{\"a}del},
  booktitle =    {Proceedings 9th Structure in Complexity Theory},
  pages =        {255-266},
  title =        {{L}ogical {D}efinability of {C}ounting {F}unctions},
  year =         {1994}
}

@Article{CondonL95,
title={Interactive Proof Systems with Polynomially Bounded
Strategies},
author={Anne Condon and Richard Ladner},
pages={506--518},
journal=jcss,
year=1995,
month=jun,
volume=50,
number=3,
source={http://theory.lcs.mit.edu/~dmjones/hbp/jcss/jcss.bib}
}

@InProceedings{coo79,
  author = 	 {S. A. Cook},
  title = 	 {Deterministic {CFL}'s are accepted simultaneously in polynomial time and log squared space},
  booktitle = 	 {Proceedings 11th Theory of Computing},
  year =	 1979,
  publisher =	 {ACM Press},
  pages =	 {338-345}
}

@Article{coo85,
  author = 	 {S. A. Cook},
  title = 	 {A taxonomy of problems with fast parallel algorithms},
  journal = 	 {Information and Control},
  year = 	 1985,
  volume =	 64,
  pages =	 {2-22}
}

@TechReport{crhevowa95,
  author = 	 {K. Cronauer and U. Hertrampf and H. Vollmer and
		  K. W. Wagner},
  title = 	 {The chain method to separate counting classes},
  institution =  {Department of Computer Science},
  year = 	 1995,
  number =	 {A-95-20},
  address =	 {University L\"ubeck}
}

@Article{crhevowa97,
  author = 	 {K. Cronauer and U. Hertrampf and H. Vollmer and K. W. Wagner},
  title = 	 {The chain method to separate counting classes},
  journal = 	 {Theory of Computing Systems},
  year = 	 1997,
  note =	 {To appear}
}

@Unpublished{dabo96,
  author = 	 {Z. Dang and R.  V. Book},
  title = 	 {On characterizations of {Almost-$R_A$}},
  note =	 {Manuscript},
  year =	 1996
}

@Misc{dahoro94,
  author =	 {C. Damm and M. Holzer and P. Rossmanith},
  title =	 {Expressing uniformity via oracles},
  howpublished = {manuscript},
  year =	 94
}

@InCollection{ebb85,
  author = 	 {H.-D. Ebbinghaus},
  title = 	 {Extended logics: The general framework},
  booktitle = 	 {Model-Theoretic Logics},
  publisher =	 {Springer Verlag},
  year =	 1985,
  editor =	 {J. Barwise and S. Feferman},
  series =	 {Perspectives in Mathematical Logic},
  chapter =	 {II},
  pages =	 {25-76}
}

@Book{ebfl95,
  author = 	 {H.-D. Ebbinghaus and J. Flum},
  title = 	 {Finite Model Theory},
  publisher = 	 {Springer Verlag},
  year = 	 1995,
  address =      {Berlin Heidelberg}
}

@Book{ebflth94,
  author = 	 {H.-D. Ebbinghaus and J. Flum and W. Thomas},
  title = 	 {Mathematical Logic},
  publisher = 	 {Springer Verlag},
  year = 	 1994,
  address =      {Berlin Heidelberg},
  edition =	 {2nd}
}

@Book{eil76,
  author = 	 {S. Eilenberg},
  title = 	 {Automata, Languages, and Machines},
  publisher = 	 {Academic Press},
  year = 	 1976,
  volume =	 {B},
  address =	 {New York}
}

@inproceedings{fag74,
  author =       {R. Fagin},
  booktitle =    {Complexity of Computations},
  editor =       {R. Karp},
  pages =        {43-73},
  title =        {Generalized  first-order spectra and polynomial  
		  time recognizable sets},
  publisher =	 {American Mathematical Society},
  address =	 {Providence, RI},
  year =         1974
}

@Book{trba70,
  author = 	 {B. A. Trachtenbrot and J. M. Barsdin},
  title = 	 {Finite Automata. Behaviour and Synthesis},
  publisher = 	 {Mir},
  year = 	 1970,
  address =	 {Moscow},
  note =	 {In Russian.}
}

@InProceedings{bue62,
  author = 	 {J. R. B{\"u}chi},
  title = 	 {On a decision method in restricted second-order arithmetic},
  booktitle = 	 {Proceedings Logic, Methodology and Philosophy of Sciences 1960},
  year = 	 1962,
  publisher =	 {Stanford University Press},
  address =	 {Stanford, CA}
}

@Article{fefoku94,
  author = 	 {S. Fenner and L. Fortnow and S. Kurtz},
  title = 	 {Gap-definable counting classes},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1994,
  volume =	 48,
  pages =	 {116-148}
}

@InProceedings{fglss91,
  author = 	 {U. Feige and S. Goldwasser and L. Lov\'asz and S. Safra and M. Szegedy},
  title = 	 {Approximating clique is almost {NP}-complete},
  booktitle = 	 {Proceedings 32nd Symposium on Foundations of Computer Science},
  year =	 1991,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {2-12}
}

@article{fglss96,
Author = "U. Feige and S. Goldwasser and L. {Lov\'{a}sz} and S. Safra
and M. Szegedy",
title = "Interactive Proofs and the Hardness of Approximating Cliques",
journal = jacm,
volume = 43,
number = 2,
month = mar,
year = 1996,
pages = {268-292}}

@Unpublished{fis74,
  author = 	 {M. J. Fischer},
  title = 	 {Lectures on Network Complexity},
  note = 	 {Universit\"at Frankfurt/Main},
  year =	 1974
}

@Article{for94,
  author = 	 {L. Fortnow},
  title = 	 {The role of relativization in complexity theory},
  journal = 	 {Bulletin of the EATCS},
  year = 	 1994,
  volume =	 52,
  pages =	 {229-244}
}

@InCollection{for97,
  author = 	 {L. Fortnow},
  title = 	 {Counting Complexity},
  booktitle = 	 {Complexity Theory Retrospective II},
  publisher =	 {Springer Verlag},
  year =	 1997,
  editor =	 {A. Selmand and L. A. Hemaspaandra},
  address =	 {New York},
  pages =	 {81-107}
}


@string{tcs = {Theoretical Computer Science}}

@Article{FortnowL1993,
title={Interactive proof systems and alternating time--space
complexity},
author={Lance Fortnow and Carsten Lund},
pages={55--73},
journal=tcs,
year=1993,
month={24~} # may,
volume=113,
number=1,
source={http://theory.lcs.mit.edu/~dmjones/hbp/tcs/tcs.bib}
}

@Article{fosi88,
  author = 	 {L. Fortnow and M. Sipser},
  title = 	 {Are there interactive protocols for {coNP} languages?},
  journal = 	 {Information Processing Letters},
  year = 	 1988,
  volume =	 28,
  pages =	 {249-251}
}

@Article{fusasi84,
  author = 	 {M. Furst and J. B. Saxe and M. Sipser},
  title = 	 {Parity, circuits, and the polynomial-time hierarchy},
  journal = 	 {Mathematical Systems Theory},
  year = 	 1984,
  volume =	 17,
  pages =	 {13-27}
}

@Book{gajo79,
  author = 	 {M. R. Garey and D. S. Johnson},
  title = 	 {Computers and Intractability, A Guide to the Theory of NP-Completeness},
  publisher = 	 {Freeman},
  year = 	 1979,
  address =	 {New York}
}

@Article{gakrra95,
  author = 	 {W. I. Gasarch and M. W. Krentel and K. J. Rappoport},
  title = 	 {{OptP} as the normal behaviour of {NP}-complete problems},
  journal = 	 {Mathematical Systems Theory},
  year = 	 1995,
  volume =	 28,
  pages =	 {487-514}
}

@InCollection{gat93,
  author = 	 {J. von zur Gathen},
  title = 	 {Parallel linear algebra},
  booktitle = 	 {Synthesis of Parallel Algorithms},
  publisher =	 {Morgan Kaufmann},
  year =	 1993,
  editor =	 {J. H. Reif},
  pages =	 {573-617}
}

@Article{gil77,
  author = 	 {J. Gill},
  title = 	 {Computational complexity of probabilistic complexity
                  classes},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1977,
  volume =	 6,
  pages =	 {675-695}
}

@Book{gisp93,
  title = 	 {Lectures on Parallel Computation},
  publisher = 	 {Cambridge University Press},
  year = 	 1993,
  editor =	 {A. Gibbons and P. Spirakis},
  volume =	 4,
  series =	 {Cambridge International Series on Parallel Computation},
  address =	 {Cambridge}
}

@Unpublished{glwe97,
  author = 	 {C. Gla{\ss}er and G. Wechsung},
  title = 	 {Relativizing function classes},
  note = 	 {Manuscript},
  year =	 1997
}

@InCollection{gol97,
  author = 	 {O. Goldreich},
  title = 	 {A taxonomy of proof systems},
  booktitle = 	 {Complexity Theory Retrospective II},
  publisher =	 {Springer Verlag},
  year =	 1997,
  editor =	 {L. A. Hemaspaandra and A. L. Selman},
  pages =	 {109-134}
}

@Article{gopa86,
  author = 	 {L. M. Goldschlager and I. Parberry},
  title = 	 {On the construction of parallel computers from various bases of boolean functions},
  journal = 	 {Theoretical Computer Science},
  year = 	 1986,
  volume =	 43,
  pages =	 {43-58}
}

@TechReport{got95,
  author = 	 {G. Gottlob},
  title = 	 {Relativized logspace and generalized quantifiers
		  over finite structures},
  institution =  {Institut for Information Systems, Vienna University
		  of Technology},
  year = 	 {1995},
  number =	 {CD-TR-95/76},
  note =         {An extended abstract appeared in the proceedings of
		  the 10th Symposium on Logic in Computer Science, 1995.}
}

@Article{got95b,
  author = 	 {G. Gottlob},
  title = 	 {{NP} trees and {Carnap's} modal logic},
  journal = 	 {Journal of the Association for Computing Machinery},
  year = 	 1995,
  volume =	 42,
  pages =	 {421-457}
}

@article{gra92,
  author =       {Erich Gr{\"{a}}del},
  journal =      {Theoretical {C}omputer {S}cience},
  number =       101,
  pages =        {35-57},
  title =        {Capturing complexity classes by fragments of 
		  second-order logic},
  year =         1992
}

@Article{gre91,
  author = 	 {F. Green},
  title = 	 {An oracle separating {$\pari\P$} from {$\PP^{\PH}$}},
  journal = 	 {Information Processing Letters},
  year = 	 1991,
  volume =	 37,
  pages =	 {149-153}
}

@Article{gre93,
  author = 	 {F. Green},
  title = 	 {On the power of deterministic reductions to {C$_=$P}},
  journal = 	 {Mathematical Systems Theory},
  year = 	 1993,
  volume =	 26,
  pages =	 {215-234}
}

@Book{grhoru95,
  author = 	 {R. Greenlaw and H. J. Hoover and W. L. Ruzzo},
  title = 	 {Limits to Parallel Computation: P-Completeness Theory},
  publisher = 	 {Oxford University Press},
  year = 	 1995,
  address =	 {New York}
}

@Article{grkorescto95,
  author = 	 {F. Green and J. K\"obler and K. Regan and T. Schwentick and J. Tor\'an},
  title = 	 {The power of the middle bit of a \#{P} function},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1995,
  volume =	 50,
  pages =	 {456-467}
}

@InCollection{hachch+93,
  author = 	 {J. Hartmanis and R. Chang and S. Chari and D. Ranjan
		  and P. Rohatgi},
  title = 	 {Relativization: a revisionistic retrospective},
  booktitle =    {Current Trends in Theoretical Computer Science},
  publisher = 	 {World Scientific},
  year = 	 1993,
  editor =	 {G. Rozenberg and A. Salomaa},
  pages =	 {537-547}
}

@InProceedings{hachraro90,
  author = 	 {J. Hartmanis and R. Chang and D. Ranjan and P. Rohatgi},
  title = 	 {Structural complexity theory: recent surprises},
  booktitle = 	 {Proceedings 2nd Scandinavian Workshop on Algorithm Theory},
  volume =	 447,
  series =	 {Lecture Notes in Computer Science},
  year =	 1990,
  publisher =	 {Springer Verlag},
  pages =	 {1-12}
}

@inproceedings{haim78,
  author =       {J. Hartmanis and N. Immerman and S. Mahaney},
  booktitle =    {Proc. 19th IEEE Symp. Foundations of Computer Science},
  pages =        {65 - 71},
  publisher =    {IEEE Computer Society Press},
  title =        {One-way log-tape reductions},
  year =         {1978}
}

@InProceedings{has86,
  author = 	 {J. H{\aa}stad},
  title = 	 {Almost optimal lower bounds for small depth circuits},
  booktitle = 	 {Procedings 18th Symposium on Theory of Computing},
  year =	 1986,
  publisher =	 {IEEE Computer Society},
  pages =	 {6-20}
}

@Book{has88,
  author = 	 {J. H{\aa}stad},
  title = 	 {Computational Limitations of Small Depth Circuits},
  publisher = 	 {MIT Press},
  year = 	 1988,
  address =	 {Cambridge}
}

@Book{hawr54,
  author = 	 {G. H. Hardy and E. M. Wright},
  title = 	 {An Introduction to the Theory of Numbers},
  publisher = 	 {Oxford University Press},
  year = 	 1954,
  edition =	 {3rd}
}

@InProceedings{helascvowa93,
  author = 	 {U. Hertrampf and C. Lautemann and T. Schwentick and
		  H. Vollmer and K. W. Wagner},
  title = 	 {On the power of polynomial time bit-reductions},
  booktitle = 	 {Proceedings 8th Structure in Complexity Theory},
  year =	 1993,
  pages =	 {200-207}
}

@TechReport{heog94,
  author = 	 {L. Hemaspaandra and M. Ogihara},
  title = 	 {Universally serializable computation},
  institution =  {Department of Computer Science, University of Rochester},
  year = 	 1994,
  number =	 {TR-520}
}

@TechReport{her95,
  author = 	 {U. Hertrampf},
  title = 	 {Regular leaf-languages and (non-) regular tree shapes},
  institution =  {Institut f\"ur Mathematik und Informatik,
		  Medizinische Universit\"at zu L\"ubeck},
  year = 	 1995,
  number =	 {A-95-21}
}

@InProceedings{her95b,
  author = 	 {U. Hertrampf},
  title = 	 {Classes of bounded counting type and their inclusion
		  relations},
  booktitle = 	 {Proceedings 12th Symposium on Theoretical Aspects of
		  Computer Science},
  volume =	 900,
  series =	 {Lecture Notes in Computer Science},
  year =	 1995,
  publisher =	 {Springer Verlag},
  pages =	 {60-70}
}

@TechReport{her96,
  author = 	 {U. Hertrampf},
  title = 	 {Acceptance by transformation monoids (with an
                  application to local self reductions)},
  institution =  {Fachbereich Informatik, Universit\"at Stuttgart},
  year = 	 1996
}

@InProceedings{her97,
  author = 	 {U. Hertrampf},
  title = 	 {Acceptance by transformation monoids (with an application to local self reductions)},
  booktitle = 	 {Proceedings 12th Conference on Computational Complexity},
  year =	 1997,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {213-224}
}

@InProceedings{her97b,
  author = 	 {U. Hertrampf},
  title = 	 {Polynomial Time Machines Equipped with Word Problems
                  over Algebraic Structures as their Acceptance Criteria},
  booktitle = 	 {Proceedings 11th Fundamentals of Computation Theory},
  volume =	 {1279},
  series =	 {Lecture Notes in Computer Science},
  year =	 1997,
  publisher =	 {Springer Verlag},
  pages =	 {233-244}
}

@article{hevo95,
  author =       {L. Hemaspaandra and H. Vollmer},
  journal =      {Complexity Theory Column 8, ACM SIGACT-Newsletter},
  number =       1,
  pages =        {2-13},
  title =        {The satanic notations: counting classes beyond {\#}{P} 
		  and other definitional adventures},
  volume =       26,
  year =         1995
}

@InProceedings{hevowa95,
  author = 	 {U. Hertrampf and H. Vollmer and K. W. Wagner},
  title = 	 {On the power of number-theoretic operations with
		  respect to counting},
  booktitle = 	 {Proceedings 10th Structure in Complexity Theory},
  year =	 1995,
  pages =        {299-314}
}

@Article{hevowa96,
  author = 	 {U. Hertrampf and H. Vollmer and K. W. Wagner},
  title = 	 {On balanced vs.~unbalanced computation trees},
  journal = 	 {Mathematical Systems Theory},
  volume =       29,
  year =         1996,
  pages =        {411-421}
}

@InProceedings{hewe97,
  author = 	 {H. Hempel and G. Wechsung},
  title = 	 {The operators min and max on the polynomial time hierarchy},
  booktitle = 	 {Proceedings 14th Symposium on Theoretical Aspects of Computer Science},
  year =         1997,
  series =	 {Lecture Notes in Computer Science},
  volume =       1200,
  publisher =    {Springer Verlag},
  pages =        {93-104}
}

@Article{hop84,
  author = 	 {J. E. Hopcroft},
  title = 	 {Turing machines},
  journal = 	 {Scientific American},
  year = 	 1984,
  month =	 {May},
  volume =       5,
  pages =	 {86-98}
}

@InCollection{hoprst95,
  author = 	 {S. Hougardy and H.-J. Pr\"omel and A. Steger},
  title = 	 {Probabilistically checkable proofs and their consequences for approximation algorithms},
  booktitle = 	 {Trends in Discrete Mathematics},
  publisher =	 {North Holland},
  year =	 1995,
  editor =	 {W. Deubner and H.-J. Pr\"omel and B. Voigt},
  volume =	 9,
  series =	 {Topics in Discrete Mathematics},
  pages =	 {175-223}
}

@article{houl69,
  author =       {J. E. Hopcroft and J. D. Ullman},
  journal =      {Journal of the {ACM}},
  number =       {1},
  pages =        {168-177},
  title =        {{S}ome {R}esults on {T}ape-{B}ounded {T}uring {M}achines},
  volume =       {16},
  year =         {1969}
}

@Book{houl79,
  author = 	 {H. E. Hopcroft and J. D. Ullman},
  title = 	 {Introduction to Automata Theory, Languages, and Computation},
  publisher = 	 {Addison-Wesley},
  address =      {Reading, MA},
  year = 	 1979
}

@Book{hro97,
  author = 	 {J. Hromkovi\v{c}},
  title = 	 {Communication Complexity and Parallel Computing},
  publisher = 	 {Springer Verlag},
  year = 	 1997,
  series =	 {Texts in Theoretical Computer Science},
  address =      {Berlin Heidelberg}
}

@Article{iba71,
  author = 	 {O. H. Ibarra},
  title = 	 {Characterizations of some tape and time classes of
		  Turing machines in terms of multihead and auxiliary
		  stack automata},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1971,
  volume =	 5,
  pages =	 {88-117}
}

@Article{imla95,
  author = 	 {N. Immernan and S. Landau},
  title = 	 {The complexity of iterated multiplication},
  journal = 	 {Information and Computation},
  year = 	 1995,
  volume =	 116,
  pages =	 {103-116}
}

@InCollection{imm89b,
  author = 	 {N. Immerman},
  title = 	 {Descriptive and Computational Complexity},
  booktitle = 	 {Computational Complexity Theory},
  publisher =	 {American Mathematical Society},
  year =	 1989,
  editor =	 {J. Hartmanis},
  volume =	 38,
  series =	 {Proceedings of Symposia in Applied Mathematics},
  address =	 {Providence, RI},
  pages =	 {75-91}
}

@Article{imm87,
  author = 	 {N. Immerman},
  title = 	 {Languages that capture complexity classes},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1987,
  volume =	 16,
  pages =	 {760-778}
}

@InProceedings{imm88,
  author = 	 {N. Immerman},
  title = 	 {Nondeterministic space is closed under complementation},
  booktitle = 	 {3rd Ann. Conf. Structure in Complexity Theory},
  year =	 1988,
  pages =	 {112-115}
}

@Article{imm89,
  author = 	 {N. Immerman},
  title = 	 {Expressibility and parallel complexity},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1989,
  volume =	 18,
  pages =	 {625-638}
}

@Article{imm88b,
  author = 	 {N. Immerman},
  title = 	 {Nondeterministic space is closed under complementation},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1988,
  volume =	 17,
  pages =	 {935-938}
}

@Article{jemcth96,
  author =       {B. Jenner and P. McKenzie and D. Th\'erien},
  title =        {Logspace and logtime leaf languages},
  year =         1996,
  journal =      {Information \& Computation},
  volume =       129,
  pages =        {21-33}
}


@Article{jeto95,
  author = 	 {B. Jenner and J. Tor{\'a}n},
  title = 	 {Computing functions with parallel queries to {NP}},
  journal = 	 {Theoretical Computer Science},
  year = 	 1995,
  volume =	 141,
  pages =	 {175-193}
}

@InCollection{joh90,
  author = 	 {D. S. Johnson},
  title = 	 {A catalog of complexity classes},
  booktitle = 	 {Handbook of Theoretical Computer Science},
  publisher = 	 {Elsevier},
  year = 	 1990,
  editor =	 {J. van Leeuwen},
  volume =	 {A},
  pages =	 {67-161}
}

@Article{jose74,
  author = 	 {N. D. Jones and A. L. Selman},
  title = 	 {Turing machines and the spectra of first-order
		  formulas},
  journal = 	 {Journal of Symbolic Logic},
  year = 	 1974,
  volume =	 39
}

@Article{sze87,
  author = 	 {R. Szelepcs\'enyi},
  title = 	 {The method of forcing for nondeterministic automata},
  journal = 	 {Bulletin of the European Association for Theoretical Computer Science},
  year = 	 1987,
  volume =	 33,
  pages =	 {96-100}
}

@article{sze88,
author = "R. Szelepcs\'{e}nyi",
title = "The Method of Forced Enumeration for Nondeterministic Automata",
journal = "Acta Informatica",
volume = 26,
pages = "279-284",
year = 1988}
  
@Article{jon75,
  author = 	 {N. D. Jones},
  title = 	 {Space-bounded reducibility among combinatorial problems},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1975,
  volume =	 15,
  pages =	 {68-85}
}

@Article{kali82,
  author = 	 {R. Karp and R. Lipton},
  title = 	 {Turing machines that take advice},
  journal = 	 {L'enseignement math\'ematique},
  year = 	 1982,
  volume =	 28,
  pages =	 {191-209}
}

@Book{hapu93,
  author = 	 {P. H{\'a}jek and P. Pudl{\'a}k},
  title = 	 {Metamathematics of First-Order Arithmetic},
  publisher = 	 {Springer Verlag},
  year = 	 1993,
  series =	 {Perspectives in Mathematical Logic},
  address =	 {Berlin Heidelberg}
}

@Book{smo91,
  author = 	 {C. Smory{\'n}ski},
  title = 	 {Logical Number Theory I},
  publisher = 	 {Springer Verlag},
  year = 	 1991
}

@InProceedings{kami94,
  author = 	 {S. M. Kautz and P. B. Miltersen},
  title = 	 {Relative to a random oracle, {NP} is not small},
  booktitle = 	 {Proceedings 9th Structure in Complexity Theory},
  year =	 1994,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {162-174}
}

@PhdThesis{kau91,
  author = 	 {S. Kautz},
  title = 	 {Degrees of random sets},
  school = 	 {Cornell University},
  year = 	 1991
}

@Book{knuI97,
  author = 	 {D. E. Knuth},
  title = 	 {The Art of Computer Programming Vol.~I: Fundamental Algorithms},
  publisher = 	 {Addison-Wesley},
  year = 	 1997,
  edition =	 {3rd}
}



@Article{ko89,
  author = 	 {K.-I. Ko},
  title = 	 {Relativized Polynomial Time Hierarchies Having Exactly $k$ Levels},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1989,
  volume =	 18,
  pages =	 {392-408}
}

@PhdThesis{koe89,
  title = 	 {{S}trukturelle {K}omplexit\"at von {A}nzahlproblemen},
  author = 	 {J. K{\"o}bler},
  school = 	 {Universit\"at Stuttgart, Fakult\"at f\"ur Informatik},
  year = 	 1989
}



@Unpublished{koe89-dt,
  author = 	 {J. K{\"o}bler},
  title = 	 {{S}trukturelle {K}omplexit\"at von {A}nzahlproblemen},
  note = 	 {Dissertation, Universit\"at Stuttgart, Fakult\"at f\"ur Informatik},
  year = 	 1989
}

@MastersThesis{kos96,
  author = 	 {S. Kosub},
  title = 	 {Clustermaschinen},
  school = 	 {Fakult\"at f\"ur Mathematik und Informatik},
  year = 	 1996,
  address =	 {Friedrich-Schiller-Universit\"at Jena}
}

@TechReport{kos97,
  author = 	 {S. Kosub},
  title = 	 {On cluster machines and function classes},
  institution =  {Institut f\"ur Informatik, Universit\"at W\"urzburg},
  year = 	 1997,
  number =	 172
}

@Article{koscto89,
  author = 	 {J. K\"obler and U. Sch\"oning and J. Tor\'an},
  title = 	 {On counting and approximation},
  journal = 	 {Acta Informatica},
  year = 	 1989,
  volume =	 26,
  pages =	 {363-379}
}

@TechReport{koscvo97,
  author = 	 {S. Kosub and H. Schmitz and H. Vollmer},
  title = 	 {Uniformly defining complexity classes of functions},
  institution =  {Institut f\"ur Informatik, Universit\"at W\"urzburg},
  number =       183,
  year = 	 1997
}

@Article{kre88,
  author = 	 {M. W. Krentel},
  title = 	 {The complexity of optimization functions},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1988,
  volume =	 36,
  pages =	 {490-509}
}

@Article{kre92,
  author = 	 {M. W. Krentel},
  title = 	 {Generalizations of {OptP} to the polynomial hierarchy},
  journal = 	 {Theoretical Computer Science},
  year = 	 1992,
  volume =	 97,
  pages =	 {183-198}
}

@Article{kumaro95,
  author = 	 {S. A. Kurtz and S. R. Mahaney and J. S. Royer},
  title = 	 {The isomorphism conjecture fails relative to a
		  random oracle},
  journal = 	 {Journal of the ACM},
  year = 	 1995,
  volume =	 42,
  pages =	 {401-420}
}

@Article{kur83,
  author = 	 {S. Kurtz},
  title = 	 {On the random oracle hypothesis},
  journal = 	 {Information and Control},
  year = 	 1983,
  volume =	 57,
  pages =	 {40-47}
}

@inproceedings{lan86,
  author =       {K. J. Lange},
  booktitle =    {Proceedings 12th Symposium on Mathematical Foundations 
		  of Computer Science},
  pages =        {518-526},
  publisher =    {Springer Verlag},
  series =       {Lecture Notes in Computer Science},
  title =        {Two characterizations of the logarithmic 
		  alternation hierarchy},
  volume =       233,
  year =         1986
}

@InProceedings{lascth94,
  author = 	 {C. Lautemann and T. Schwentick and D. Th\'erien},
  title = 	 {Logics for context-free languages},
  booktitle = 	 {8th Computer Science Logic, Selected Papers},
  editor =	 {L. Pacholski and J. Tiuryn},
  volume =	 933,
  series =	 {Lecture Notes in Computer Science},
  year =	 1994,
  publisher =	 {Springer Verlag},
  pages =	 {205-216}
}

@article{lau83,
  author =       {C. Lautemann},
  journal =      {Information Processing Letters},
  pages =        {215-217},
  title =        {{BPP} and the polynomial hierarchy},
  volume =       17,
  year =         1983
}

@article{lei89,
  author =       {Daniel Leivant},
  journal =      {Journal of Computer and System Sciences},
  pages =        {51-83},
  title =        {Descriptive {C}haracterizations of {C}omputational 
		  {C}omplexity},
  volume =       39,
  year =         1989
}

@Article{lin66,
  author = 	 "P. Lindstr{\"o}m",
  title = 	 "First order predicate logic with generalized quantifiers",
  journal =	 "Theoria",
  year =	 1966,
  volume =	 32,
  pages =	 "186-195"
}
		  
@InProceedings{lin92,
  author = 	 {S. Lindell},
  title = 	 {A purely logical characterization of circuit uniformity},
  booktitle = 	 {Proceedings 7th Structure in Complexity Theory},
  year =	 1992,
  pages =	 {185-192}
}
		  
@Misc{lin94,
  author =	 {S. Lindell},
  howpublished = {manuscript},
  year =	 1994,
  note =	 {e-mail communication by Kenneth W. Regan}
}		  
		  
@Book{livi93,
  author = 	 {M. Li and P. Vit\'anyi},
  title = 	 {An Introduction to Kolmogorov Complexity and its
		  Applications},
  publisher = 	 {Springer Verlag},
  year = 	 1993,
  series =	 {Texts and Monographs in Computer Science},
  address =	 {New York}
}

@Article{lup58,
  author = 	 {O. B. Lupanov},
  title = 	 {A method of circuit synthesis},
  journal = 	 {Izvestia V.U.Z. Radiofizika},
  year = 	 1958,
  volume =	 1,
  pages =	 {120-140}
}

@Article{lut92,
  author = 	 {J. Lutz},
  title = 	 {On independent random oracles},
  journal = 	 {Theoretical Computer Science},
  year = 	 1992,
  volume =	 92,
  pages =	 {301-307}
}

@Article{lut93a,
  author = 	 {J. Lutz},
  title = 	 {A pseudorandom oracle characterization of {BPP}},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1992,
  volume =	 22,
  pages =	 {???}
}

@InProceedings{lut93b,
  author = 	 {J. Lutz},
  title = 	 {The quantitative structure of exponential time},
  booktitle = 	 {Proceedings 8th Structure in Complexity Theory},
  year =	 1993,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {158-175}
}

@inproceedings{lyn90,
  author =       {J. F. Lynch},
  booktitle =    {5th Ann. Conf. Structure in Complexity Theory},
  journal =      {Proc. 5th Structure in Complexity Conf.},
  pages =        {210-222},
  title =        {The {Q}uantifier {S}tructure of {S}entences that 
		  {C}haracterize {N}ondeterministic {T}ime {C}omplexity},
  year = 1990
}

@InProceedings{mapn93,
  author = 	 {J. A. Makowsky and Y. B. Pnueli},
  title = 	 {Oracles and quantifiers},
  booktitle = 	 {Computer Science Logic},
  volume =	 832,
  series =	 {Lecture Notes in Computer Science},
  year =	 1993,
  publisher =	 {Springer Verlag},
  pages =	 {189-222}
}

@InProceedings{mapn94,
  author = 	 {J. A. Makowsky and Y. B. Pnueli},
  title = 	 {Logics capturing relativized complexity classes uniform},
  booktitle = 	 {Logic and Computational Complexity},
  editor =	 {D. Leivant},
  volume =	 1995,
  series =	 {Lecture Notes in Computer Science},
  year =	 1994,
  publisher =	 {Springer Verlag}
}

@Article{mar66,
  author = 	 {P. Martin-L\"of},
  title = 	 {The definition of random sequences},
  journal = 	 {Information and Control},
  year = 	 1966,
  volume =	 9,
  pages =	 {602-619}
}

@InProceedings{math93,
  author = 	 {A. Maciel and T. Th\'erien},
  title = 	 {Threshold circuits for iterated multiplication: using {$\ACn$} for free},
  booktitle = 	 {Proceedings 10th Symposium on Theoretical Aspects of Computer Science},
  volume =	 665,
  series =	 {Lecture Notes in Computer Science},
  year =	 1993,
  publisher =	 {Springer Verlag},
  pages =	 {545-554}
}

@Book{mcpa71,
  author = 	 {R. McNaughton and S. Papert},
  title = 	 {Counter-Free Automata},
  publisher = 	 {MIT Press},
  year = 	 1971
}

@Book{meco81,
  author = 	 {C. Mead and L. Conway},
  title = 	 {Introduction to VLSI Systems},
  publisher = 	 {Addison-Wesley},
  year = 	 1981,
  address =	 {Reading, MA}
}

@inproceedings{meh82,
  author =       {K. Mehlhorn and E. M. Schmidt},
  booktitle =    {Proceedings 14th Symposium on Theory of Computing},
  pages =        {330-337},
  title =        {Las Vegas is better than Determinism in VLSI and 
		  Distributed Computing},
  year =         1982
}

@InProceedings{mest72,
  author = 	 {A. R. Meyer and L. J. Stockmeyer},
  title = 	 {The equivalence problem for regular expressions with
		  squaring requires exponential time},
  booktitle = 	 {Proceedings 13th Symposium on Switching and Automata
		  Theory},
  year =	 1972,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {125-129}
}

@InProceedings{mewa95,
  author = 	 {W. Merkle and Y. Wang},
  title = 	 {Separations by random oracles and ``{A}lmost''
		  classes for generalized reducibilities},
  booktitle = 	 {Proceedings 20th Symposium on Mathematical
		  Foundations of Computer Science},
  volume =	 969,
  series =	 {Lecture Notes in Computer Science},
  publisher =    {Springer Verlag},	  
  year =	 1995,
  pages =	 {179-190}
}

@Article{mil92,
  author = 	 {P. B. Miltersen},
  title = 	 {Circuit depth relative to a random oracle},
  journal = 	 {Information Processing Letters},
  year = 	 1992,
  volume =	 42,
  pages =	 {???}
}

@Book{mipa88,
  author = 	 {M. Minsky and S. A. Papert},
  title = 	 {Perceptrons},
  publisher = 	 {MIT Press},
  year = 	 1988,
  address =	 {Cambridge, MA},
  note =	 {Expanded edition. Originally published in 1969}
}

@Article{muve96,
  author = 	 {A. A. Muchnik and N. K. Vereshchagin},
  title = 	 {A general method to construct oracles realizing given relationships between complexity classes},
  journal = 	 {Theoretical Computer Science},
  year = 	 1996,
  volume =	 157,
  pages =	 {227-258}
}

@Article{nis93,
  author = 	 {N. Nisan},
  title = 	 {On read-once vs. multiple access to randomness in logspace},
  journal = 	 {Theoretical Computer Science},
  year = 	 1993,
  volume =	 107,
  pages =	 {135-144}
}

@Article{niwi94,
  author = 	 {N. Nisan and A. Wigderson},
  title = 	 {Hardness vs. randomness},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1994,
  volume =	 49,
  pages =	 {149-167}
}

@Article{oghe93,
  author = 	 {M. Ogiwara and L. Hemachandra},
  title = 	 {A complexity theory of feasible closure properties},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1993,
  volume =	 46,
  pages =	 {295-325}
}

@Article{ogi94,
  author = 	 {M. Ogihara},
  title = 	 {On serializable languages},
  journal = 	 {International Journal of Foundations of Computer Science},
  year = 	 1994,
  volume =	 5,
  pages =	 {303-318}
}

@InProceedings{orp83,
  author = 	 {P. Orponen},
  title = 	 {Complexity classes of alternating machines with oracles},
  booktitle = 	 {Proceedings 10th International Colloquium on
		  Automata, Languages and Programming},
  volume =	 154,
  series =	 {Lecture Notes in Computer Science},
  year =	 1983,
  publisher =	 {Springer Verlag},
  pages =	 {573-584}
}

@book{pap94,
  author =       {C. H. Papadimitriou},
  publisher =    {Addison-Wesley},
  address =      {Reading, MA},
  title =        {Computational Complexity},
  year =         1994
}

@InProceedings{paza83,
  author = 	 {C. H. Papadimitriou and S. Zachos},
  title = 	 {Two remarks on the power of counting},
  booktitle = 	 {Proceedings 6th GI Conference on Theoretical
		  Computer Science},
  volume =	 145,
  series =	 {Lecture Notes in Computer Science},
  year =	 1983,
  publisher =	 {Springer Verlag},
  pages =	 {269-275}
}


@InProceedings{pip79,
  author = 	 {N. Pippenger},
  title = 	 {On simultaneous resource bounds},
  booktitle = 	 {Proceedings 20th Symposium on Foundations of Computer Science},
  year =	 1979,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {307-311}
}

@TechReport{rasa95,
  author = 	 {J. Radhakrishnan and S. Saluja},
  title = 	 {Interactive Proof Systems},
  institution =  {Tata Institute of Fundamental Research},
  year = 	 1995,
  number =	 {TCS-95/4},
  address =	 {Bombay},
  note =         {Lecture Notes}		  
}



@Article{raz85,
  author = 	 {A. A. Razborov},
  title = 	 {Lower bounds on the monotone complexity of some boolean functions},
  journal = 	 {Doklady Akademii Nauk SSSR},
  year = 	 1985,
  volume =	 281,
  pages =	 {798-801},
  note =	 {English translation in Soviet Math. Doklady 31 (1985), 354--357}
}

@Article{raz87,
  author =       {A. A. Razborov},
  title = 	 {Lower bounds on the size of bounded depth networks over a complete basis with logical addition},
  journal = 	 {Matematicheskie Zametki},
  year = 	 1987,
  volume =	 41,
  pages =	 {598-607},
  note =	 {In Russian. English translation in {\em Mathematical Notes of the Academy of Sciences of the USSR\/} 41:333--338, 1987}
}



@InCollection{reg97,
  author = 	 {K. Regan},
  title = 	 {Polynomials and combinatorial definitions of languages},
  booktitle = 	 {Complexity Theory Retrospective II},
  publisher =	 {Springer Verlag},
  year =	 1997,
  editor =	 {L. A. Hemaspaandra and A. L. Selman},
  pages =	 {261-293}
}

@Unpublished{reg93,
  author = 	 {K. Regan},
  title = 	 {Log-time {ATMs} and first-order logic},
  note = 	 {Unpublished manuscript},
  year =	 1993
}

@Article{rero95,
  author = 	 {K. W. Regan and J. S. Royer},
  title = 	 {On closure properties of bounded two-sided error
		  complexity classes},
  journal = 	 {Mathematical Systems Theory},
  year = 	 1995,
  volume =	 28,
  pages =	 {229-243}
}		  
		  
@Article{revo97,
  author = 	 {K. Regan and H. Vollmer},
  title = 	 {Gap-languages and log-time complexity classes},
  journal = 	 {Theoretical Computer Science},
  year = 	 1997,
  volume =	 188,
  pages =        {101-116}
}


@Book{rog67,
  author = 	 {H. {Rogers Jr.}},
  title = 	 {Theory of Recursive Functions and Effective Computability},
  publisher = 	 {McGraw-Hill},
  year = 	 1967,
  address =	 {New York}
}

@Book{rosaI97,
  title = 	 {Handbook of Formal Languages},
  publisher = 	 {Springer Verlag},
  year = 	 1997,
  editor =	 {R. Rozenberg and A. Salomaa},
  volume =	 {I}
}

@Article{ruz80,
  author = 	 {W. L. Ruzzo},
  title = 	 {Tree-size bounded alternation},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1980,
  volume =	 21,
  pages =	 {218-235}
}

@Article{ruz81,
  author = 	 {W. L. Ruzzo},
  title = 	 {On uniform circuit complexity},
  journal = 	 {Journal of Computer and Systems Sciences},
  year = 	 1981,
  volume =	 21,
  pages =	 {365-383}
}

@inproceedings{sasuth92,
  author =       {S. Saluja and K. V. Subrahmanyam and M. N. Thakur},
  booktitle =    {Proceedings 7th Structure in Complexity Theory},
  title =        {Descriptive Complexity of \#{P} Functions},
  year =         1992
}

@Book{sav76,
  author = 	 {J. E. Savage},
  title = 	 {The Complexity of Computing},
  publisher = 	 {John Wily},
  year = 	 1976,
  address =	 {New York}
}

@Article{sch74,
  author = 	 {C. P. Schnorr},
  title = 	 {Zwei lineare untere {S}chranken f\"ur die {K}omplexit\"at {B}oolescher {F}unktionen},
  journal = 	 {Computing},
  year = 	 1974,
  volume =	 13,
  pages =	 {155-171}
}

@Article{sch76,
  author = 	 {C. P. Schnorr},
  title = 	 {The network complexity and the Turing machine complexity of finite functions},
  journal = 	 {Acta Informatica},
  year = 	 1976,
  volume =	 7,
  pages =	 {95-107}
}

@Book{sch86,
  author = 	 {U. Sch{\"o}ning},
  title = 	 {Complexity and Structure},
  publisher = 	 {Springer Verlag},
  address =      {Berlin Heidelberg},
  year = 	 1986,
  volume =	 211,
  series =	 {Lecture Notes in Computer Science}
}

@Article{sch89,
  author = 	 {U. Sch\"oning},
  title = 	 {Probabilistic complexity classes and lowness},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1989,
  volume =	 39,
  pages =	 {84-100}
}

@book{sch92,
  author =       {U. {Sch}{\"o}ning},
  publisher =    {{BI} {W}issenschaftsverlag},
  title =        {{T}heoretische {I}nformatik kurz gefasst},
  year =         {1992}
}

@Book{sch95,
  author = 	 {U. Sch{\"o}ning},
  title = 	 {Perlen der {T}heoretischen {I}nformatik},
  publisher = 	 {BI-Wis\-sen\-schafts\-ver\-lag},
  year = 	 1995,
  address =	 {Mannheim}
}

@MastersThesis{sch96,
  author = 	 {H. Schmitz},
  title = 	 {Nichtdeterministische {P}olynomialzeit-{B}erechnung von {F}unktionen},
  school = 	 {Institut f\"ur Informatik, Universit\"at W\"urzburg},
  year = 	 1996
}

@Unpublished{scvo97,
  author = 	 {T. Schwentick and H. Vollmer},
  title = 	 {Logical characterizations of classes between {CFL} and
                  {LOGCFL}},
  year =         1996,
  note = 	 {Manuscript}
}	  	  
		  
@TechReport{scwa97,
  author = 	 {H. Schmitz and K. Wagner},
  title = 	 {A note on parallel vs.~adaptive queries when computing functions},
  institution =  {Institut f\"ur Informatik, Universit\"at W\"urzburg},
  year = 	 1997,
  number =	 999
}		  
		  
@Article{sel94,
  author = 	 {A. Selman},
  title = 	 {A taxonomy on complexity classes of functions},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1994,
  volume =	 48,
  pages =	 {357-381}
}

@Article{sexubo83,
  author = 	 {A. L. Selman and M.-R. Xu and R. V. Book},
  title = 	 {Positive relativizations of complexity classes},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1983,
  volume =	 12,
  pages =	 {565-579}
}		  
		  
@Article{sha49,
  author = 	 {C. Shannon},
  title = 	 {The synthesis of two-terminal switching circuits},
  journal = 	 {Bell Systems Technical Journal},
  year = 	 1949,
  volume =	 28,
  pages =	 {59-98}
}

@Article{sha92,
  author = 	 {A. Shamir},
  title = 	 {{IP = PSPACE}},
  journal = 	 {Journal of the ACM},
  year = 	 1992,
  volume =	 39,
  pages =	 {869-877}
}

@InProceedings{sham90,
  author = 	 {A. Shamir},
  title = 	 {{IP = PSPACE}},
  booktitle = 	 {Proceedings 31st Symposium on Foundations of Computer Science},
  year =	 1990,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {11-15}
}

@PhdThesis{sim75,
  author = 	 {J. Simon},
  title = 	 {On Some Central Problems in Computational Complexity},
  school = 	 {Cornell University},
  year = 	 1975
}

@InProceedings{sip83,
  author = 	 {M. Sipser},
  title = 	 {A complexity theoretic approach to randomness},
  booktitle = 	 {Proceedings of the 15th Symposium on Theory of Computing},
  year =	 1983,
  pages =	 {330-335}
}

@InProceedings{sip83b,
  author = 	 {M. Sipser},
  title = 	 {Borel sets and circuit complexity},
  booktitle = 	 {Proceedings of the 15th Symposium on Theory of Computing},
  year =	 1983,
  publisher =	 {ACM Press},
  pages =	 {61-69}
}

@InProceedings{smo87,
  author = 	 {R. Smolensky},
  title = 	 {Algebraic methods in the theory of lower bounds for {Boolean} circuit complexity},
  booktitle = 	 {Proceedings 19th Symposium on Theory of Computing},
  year =	 1987,
  publisher =	 {ACM Press},
  pages =	 {77-82}
}



@Article{ste91,
  author = 	 {I. A. Stewart},
  title = 	 {Comparing the expressibility of languages formed
                  using {NP}-complete operators},
  journal = 	 {Journal of Logic and Computation},
  year = 	 1991,
  volume =	 1,
  pages =	 {305-330}
}

@Article{ste92,
  author = 	 {I. A. Stewart},
  title = 	 {Using the {H}amilton path operator to capture {NP}},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1992,
  volume =	 45,
  pages =	 {127-151}
}

@InProceedings{stme73,
  author =       "L. J. Stockmeyer and A. R. Meyer",
  title =        "Word Problems Requiring Exponential Time",
  pages =        {1-9},
  booktitle =    "Proceedings 5th ACM Symposium on the Theory of Computing",
  year =         1973
}

@Article{sto77,
  author = 	 {L. Stockmeyer},
  title = 	 {The polynomial-time hierarchy},
  journal = 	 {Theoretical Computer Science},
  year = 	 197,
  volume =	 3,
  pages =	 {1-22}
}

@book{str94,
  author =       {H. Straubing},
  publisher =    {Birkh{\"a}user},
  address =      {Boston},
  title =        {Finite Automata, Formal Logic, and Circuit Complexity},
  year =         1994
}

@Article{stvi84,
  author = 	 {L. Stockmeyer and U. Vishkin},
  title = 	 {Simulation of parallel random access machines by circuits},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1984,
  volume =	 13,
  pages =	 {409-422}
}

@Book{sud95,
  author = 	 {M. Sudan},
  title = 	 {Efficient Checking of Polynomials and Proofs and the
		  Hardness of Approximation Problems},
  publisher = 	 {Springer Verlag},
  year = 	 1995,
  volume =	 1001,
  series =	 {Lecture Notes in Computer Science}
}

@Article{tabo91,
  author = 	 {S. Tang and R. V. Book},
  title = 	 {Polynomial-time reducibilities and almost all oracle
		  sets},
  journal = 	 {Theoretical Computer Science},
  year = 	 1991,
  volume =	 81,
  pages =	 {201-209}
}

@Article{tar93,
  author = 	 {J. Tarui},
  title = 	 {Probabilistic polynomials, {AC$^0$} functions, and the polynomial hierarchy},
  journal = 	 {Theoretical Computer Science},
  year = 	 1993,
  volume =	 113,
  pages =	 {167-183}
}

@Article{tawa89,
  author = 	 {S. Tang and O. Watanabe},
  title = 	 {On tally relativizations of {BP}-complexity classes},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1989,
  volume =	 18,
  pages =	 {449-462}
}

@Article{the81,
  author = 	 {D. Th{\'e}rien},
  title = 	 {Classification of finite monoids: the language approach},
  journal = 	 {Theoretical Computer Science},
  year = 	 1981,
  volume =	 14,
  pages =	 {195-208}
}

@InCollection{tho90,
  author = 	 {W. Thomas},
  title = 	 {Automata on infinite objects},
  booktitle = 	 {Handbook of Theoretical Computer Science},
  publisher =	 {Elesevier},
  year =	 1990,
  editor =	 {J. van Leeuwen},
  volume =	 {B},
  address =	 {Amsterdam},
  pages =	 {133-191}
}

@InProceedings{tod90,
  author = 	 {S. Toda},
  title = 	 {The complexity of finding medians},
  booktitle = 	 {Proceedings 31st Symposium on Foundations of Computer Science},
  year =	 1990,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {778-787}
}

@Article{tod91,
  author = 	 {S. Toda},
  title = 	 {{PP} is as hard as the polynomial time hierarchy},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1991,
  volume =	 20,
  pages =	 {865-877}
}

@Article{toog92,
  author = 	 {S. Toda and M. Ogiwara},
  title = 	 {Counting classes are at least as hard as the
		  polynomial time hierarchy},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1992,
  volume =	 21,
  pages =	 {315-328}
}

@Article{tor91,
  author = 	 {J. Toran},
  title = 	 {Complexity classes defined by counting quantifiers},
  journal = 	 {Journal of the ACM},
  year = 	 1991,
  volume =	 38,
  pages =	 {753-774}
}

@InCollection{tor93,
  author = 	 {J. Tor\'an},
  title = 	 {{P}-completeness},
  pages =	 {177-196},
  booktitle = 	 {Lectures on Parallel Computation},
  publisher =	 {Cambridge University Press},
  year =	 1993,
  editor =	 {A. Gibbons and P. Spirakis},
  volume =	 4,
  series =	 {Cambridge International Series on Parallel Computation},
  address =	 {Cambridge}
}

@Article{towa92,
  author = 	 {S. Toda and O. Watanabe},
  title = 	 {Polynomial time 1-{T}uring reductions from {\#PH} to {\#P}},
  journal = 	 {Theoretical Computer Science},
  year = 	 1992,
  volume =	 100,
  pages =	 {205-221}
} 

@Unpublished{vaa94,
  author = 	 {J. V{\"a}{\"a}n\"anen},
  title = 	 {A short course on finite model theory},
  year =	 1994,
  note = 	 {Lecture Notes}
}

@Article{val76,
  author = 	 {L. G. Valiant},
  title = 	 {Relative complexity of checking and evaluation},
  journal = 	 {Information Processing Letters},
  year = 	 1976,
  volume =	 5,
  pages =	 {20-23}
}

@article{val79,
  author =       {L. G. Valiant},
  journal =      {{SIAM} Journal of Computing},
  number =       3,
  pages =        {411-421},
  title =        {The Complexity of enumeration and reliabilty Problems},
  volume =       8,
  year =         1979
}

@article{vava86,
  author =       {L. G. Valiant and V. V. Vazirani},
  journal =      {Theoretical Computer Science},
  volume =       47,
  pages =        {85-93},
  title =        {{NP} is as easy as detecting unique solutions},
  year =         1986
}

@InProceedings{vei96,
  author = 	 {H. Veith},
  title = 	 {Succinct representation, leaf languages, and
                  projection reductions},
  booktitle = 	 {Proceedings 10th Structure in Complexity Theory},
  year =	 1996,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {118-126}
}

@PhdThesis{ven86,
  author = 	 {H. Venkateswaran},
  title = 	 {Characterizations of Parallel Complexity Classes},
  school = 	 {Department of Computer Science, University of Washington},
  year = 	 1986
}

@Article{ven91,
  author = 	 {H. Venkateswaran},
  title = 	 {Properties that characterize {LOGCFL}},
  journal = 	 {Journal of Computer and System Sciences},
  year = 	 1991,
  volume =	 43,
  pages =	 {380-404}
}


@article{ver93a,
  author =       {N. K. Vereshchagin},
  title =        {Relativizable and non-relativizable theorems in the
		  polynomial theory of algorithms},
  journal =      {Izvestija Rossijskoj Akademii Nauk},
  pages =        {51-90},
  volume =       57,
  year =         1993,
  note =         {In Russian.}
}

@InProceedings{ver93b,
  author = 	 {N. K. Vereshchagin},
  title = 	 {Relationships between {NP}-sets, {Co-NP}-sets, and
		  {P}-sets relative to random oracles},
  booktitle = 	 {Proceedings 8th Structure in Complexity Theory},
  year =	 1993,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {132-138}
}

@InProceedings{vol90,
  author = 	 {H. Vollmer},
  title = 	 {The gap-language technique revisited},
  booktitle = 	 {4th Computer Science Logic, Selected Papers},
  volume =	 533,
  series =	 {Lecture Notes in Computer Science},
  year =	 1990,
  publisher =	 {Springer Verlag},
  pages =	 {389-399}
}

@phdthesis{vol94a,
  author =       {H. Vollmer},
  address =      {{I}nstitut f{\"u}r {I}nformatik, {G}ermany},
  school =       {{U}niversit{\"a}t {W}{\"u}rzburg},
  title =        {{K}omplexit{\"a}tsklassen von {F}unktionen},
  year =         1994
}

@Unpublished{vol94a-dt,
  author =       {H. Vollmer},
  title =        {{K}omplexit{\"a}tsklassen von {F}unktionen},
  year =         1994,
  note =         {{D}issertation, {U}niversit{\"a}t {W}{\"u}rzburg,
                  {I}nstitut f{\"u}r {I}nformatik},
}

@InProceedings{vol94b,
  author =       {H. Vollmer},
  booktitle =      {Proceedings 11th Symposium on Theoretical Aspects 
		  of Computer Science},
  volume =       775,
  pages =        {449-460},
  title =        {On different reducibility notions for function classes},
  series =       {Lecture Notes in Computer Science},
  publisher =    {Springer Verlag},
  year =         1994
}

@InProceedings{vol96,
  author = 	 {H. Vollmer},
  title = 	 {Relations among parallel and sequential computation models},
  booktitle = 	 {Proceedings 2nd Asian Computing Science Conference},
  volume =	 {1179},
  series =	 {Lecture Notes in Computer Science},
  year =	 1996,
  publisher =	 {Springer Verlag},
  pages =	 {23-32}
}

@TechReport{vol96b,
  author = 	 {H. Vollmer},
  title = 	 {Succinct inputs, {L}indstr\"om quantifiers, and a general complexity theoretic operator concept},
  institution =  {Institut f\"ur Informatik, Universit\"at W\"urzburg},
  year = 	 1996,
  number =	 158
}

@Article{vol97,
  author = 	 {H. Vollmer},
  title = 	 {Relating polynomial time to constant depth},
  journal =      {Theoretical Computer Science},
  year = 	 1998,
  note =         {To appear.}
}

@TechReport{vol97b,
  author = 	 {H. Vollmer},
  title = 	 {A generalized quantifier concept in computational complexity theory},
  institution =  {Institut f\"ur Informatik, Universit\"at W\"urzburg},
  year = 	 1997
}

@Article{vowa93,
  author = 	 {H. Vollmer and K. W. Wagner},
  title = 	 {The complexity of finding middle elements},
  journal = 	 {International Journal of Foundations of Computer Science},
  year = 	 1993,
  volume =	 4,
  pages =	 {293-307}
}

@Article{vowa95,
  author = 	 {H. Vollmer and K. W. Wagner},
  title = 	 {Complexity classes of optimization functions},
  journal = 	 {Information and Computation},
  year = 	 1995,
  volume =	 120,
  pages =	 {198-219}
}

@InCollection{vowa97,
  author = 	 {H. Vollmer and K. W. Wagner},
  title = 	 {Measure one results in computational complexity theory},
  booktitle = 	 {Advances in Algorithms, Languages, and Complexity},
  publisher =	 {Kluwer Academic Publishers},
  year =	 1997,
  editor =	 {D.-Z. Du and K.-I. Ko}
}

@InProceedings{vowa97b,
  author = 	 {H. Vollmer and K. W. Wagner},
  title = 	 {On operators of higher types},
  booktitle = 	 {Proceedings 12th Conference on Computational Complexity},
  year =	 {1997},
  publisher =	 {IEEE Computer Society Press},
  pages =	 {174-184}
}

@Book{vol99,
  author = 	 {H. Vollmer},
  title = 	 {Introduction to Circuit Complexity -- A Uniform Approach},
  publisher = 	 {Springer Verlag},
  year = 	 1999,
  series =	 {Texts in Theoretical Computer Science},
  address =      {Berlin Heidelberg}
}

@Article{wag86,
  author = 	 {K. W. Wagner},
  title = 	 {Some observations on the connection between counting
		  and recursion},
  journal = 	 {Theoretical Computer Science},
  year = 	 1986,
  volume =	 47,
  pages =	 {131-147}
}

@Article{wag86b,
  author = 	 {K. W. Wagner},
  title = 	 {The complexity of combinatorial problems with
		  succinct input representation},
  journal = 	 {Acta Informatica},
  year = 	 1986,
  volume =	 23,
  pages =	 {325-356}
}

@Article{wag87,
  author = 	 {K. W. Wagner},
  title = 	 {More complicated questions about maxima and minima, and some closures of {NP}},
  journal = 	 {Theoretical Computer Science},
  year = 	 1987,
  volume =	 51,
  pages =	 {53-80}
}

@Article{wag90,
  author = 	 {K. W. Wagner},
  title = 	 {Bounded query classes},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1990,
  volume =	 19,
  pages =	 {833-846}
}

@Book{wag94,
  author = 	 {K. W. Wagner},
  title = 	 {Einf\"uhrung in die Theoretische Informatik -- Grundlagen und Modelle},
  publisher = 	 {Springer Verlag},
  year = 	 1994,
  address =	 {Berlin Heidelberg}
}

@Book{wawe86,
  author = 	 {K. W. Wagner and G. Wechsung},
  title = 	 {Computational Complexity},
  publisher = 	 {VEB Verlag der Wissenschaften},
  year = 	 1986,
  address =	 {Berlin}
}

@Book{weg87,
  author = 	 {I. Wegener},
  title = 	 {The Complexity of Boolean Functions},
  publisher = 	 {B. G. Teubner \& John Wiley},
  year = 	 1987,
  series =	 {Wiley-Teubner series in computer science},
  address =      {Stuttgart}
}

@Article{wil87,
  author = 	 {C. Wilson},
  title = 	 {Relativized {NC}},
  journal = 	 {Mathematical Systems Theory},
  year = 	 1987,
  volume =	 20,
  pages =	 {13-29}
}

@Article{wil90,
  author = 	 {C. Wilson},
  title = 	 {On the decomposability of {NC} and {AC}},
  journal = 	 {SIAM Journal on Computing},
  year = 	 1990,
  volume =	 19,
  pages =	 {384-396}
}

@Article{wra77,
  author = 	 {C. Wrathall},
  title = 	 {Complete sets and the polynomial-time hierarchy},
  journal = 	 {Theoretical Computer Science},
  year = 	 1977,
  volume =	 3,
  pages =	 {23-33}
}


@InProceedings{yao85,
  author = 	 {A. C. C. Yao},
  title = 	 {Separating the polynomial-time hierarchy by oracles},
  booktitle = 	 {Proceedings 26th Foundations of Computer Science},
  year =	 1985,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {1-10}
}

@InProceedings{yao90,
  author = 	 {A. C. C. Yao},
  title = 	 {On {ACC} and threshold circuits},
  booktitle = 	 {Proceedings 31th Foundations of Computer Science},
  year =	 1990,
  publisher =	 {IEEE Computer Society Press},
  pages =	 {619-627}
}

@Unpublished{zwi95,
  author = 	 {U. Zwick},
  title = 	 {Boolean Circuit Complexity},
  note = 	 {Scribe Notes, Tel-Aviv University},
  year =	 1995
}


@string{jacm={Journal of the ACM}}

@Article{AroraS1998,
title={Probabilistic Checking of Proofs: A New Characterization
of~{NP}},
author={Sanjeev Arora and Shmuel Safra},
area={Formal Languages and Complexity Theory},
journal=jacm,
pages={70--122},
month=jan,
year=1998,
volume=45,
number=1,
keywords={Approximation algorithms, complexity hierarchies,
computations on polynomials and finite fields, error-correcting codes,
hardness of approximations, interactive computation, NP-completeness,
probabilistic computation, proof checking, reducibility and
completeness, trade-offs/relations among complexity measures},
general-terms={Algorithms, Theory, Verification},
cr-categories={F.1.2; F.1.3; F.2.1; F.2.2; F.4.1},
preliminary={focs::AroraS1992},
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}

@string{tcs = {Theoretical Computer Science}}

@Article{FortnowRS1994,
title={On the power of multi-prover interactive protocols},
author={Lance Fortnow and John Rompel and Michael Sipser},
journal=tcs,
pages={545--557},
month={21~} # nov,
year=1994,
volume=134,
number=2,
source={http://theory.lcs.mit.edu/~dmjones/hbp/tcs/tcs.bib}
}

@string{jacm={Journal of the ACM}}

@Article{LundFKN92,
title={Algebraic Methods for Interactive Proof Systems},
author={Carsten Lund and Lance Fortnow and Howard Karloff and Noam
Nisan},
area={Complexity Theory},
pages={859--868},
journal=jacm,
month=oct,
year=1992,
volume=39,
number=4,
source={http://theory.lcs.mit.edu/~jacm/jacm.bib}
}

@InProceedings{coli89,
  author = 	 {A. Condon and R. Lipton},
  title = 	 {On the complexity of space bounded interactive proofs},
  booktitle = 	 {Proceedings 30th Symposium on Foundations of Computer Science},
  pages =	 {462-467},
  year =	 1989,
  publisher =	 {IEEE Computer Society Press}
}