References

  1. Manindra Agrawal (2001): The First-Order Isomorphism Theorem. In: FST TCS '01: Proc. of the 21st Conference on Foundations of Software Technology and Theoretical Computer Science LNCS 2245. Springer-Verlag, London, UK, pp. 70–82, doi:10.1007/3-540-45294-X_7.
  2. Manindra Agrawal (2011): The Isomorphism Conjecture for constant depth reductions. Journal of Computer and System Sciences 77(1), pp. 3–13, doi:10.1016/j.jcss.2010.06.003.
  3. Eric Allender (2012): Investigations Concerning the Structure of Complete Sets. In: Workshop on Complexity and Logic.
  4. Eric Allender & Michal Koucký (2010): Amplifying lower bounds by means of self-reducibility. Journal of the ACM 57, pp. 14:1–14:36, doi:10.1145/1706591.1706594.
  5. Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta & Sambuddha Roy (2009): Planar and Grid Graph Reachability Problems. Theory of Computing Systems 45(4), pp. 675–723, doi:10.1007/s00224-009-9172-z.
  6. Carme Álvarez & Birgit Jenner (1993): A very hard log-space counting class. Theoretical Computer Science 107(1), pp. 3–30, doi:10.1016/0304-3975(93)90252-O.
  7. Sanjeev Arora & Boaz Barak (2009): Computational Complexity: A Modern Approach 978-0-511-53381-5. Cambridge University Press, doi:10.1017/CBO9780511804090.
  8. David A. Mix Barrington, Neil Immerman & Howard Straubing (1990): On Uniformity within NC^1. Journal of Computer and System Sciences 41(3), pp. 274–306, doi:10.1016/0022-0000(90)90022-D.
  9. Ronald V. Book & Ker-I Ko (1988): On Sets Truth-Table Reducible to Sparse Sets. SIAM Journal of Computing 17(5), pp. 903–919, doi:10.1137/0217056.
  10. Harry Buhrman, Edith Hemaspaandra & Luc Longpre (1995): SPARSE Reduces Conjunctively to TALLY. SIAM Journal of Computing 24, pp. 673–681, doi:10.1137/0224044.
  11. Ashok K. Chandra, Larry J. Stockmeyer & Uzi Vishkin (1984): Constant Depth Reducibility. SIAM Journal of Computing 13(2), pp. 423–439, doi:10.1137/0213028.
  12. Merrick L. Furst, James B. Saxe & Michael Sipser (1984): Parity, circuits and the polynomial-time hierarchy. Theory of Computing Systems (formerly Mathematical Systems Theory) 17(1), pp. 13–27, doi:10.1007/BF01744431.
  13. Leslie M. Goldschlager (1977): The monotone and planar circuit value problems are log space complete for P. SIGACT News 9(2), pp. 25–29, doi:10.1145/1008354.1008356.
  14. Raymand Greenlaw, H. James Hoover & Walter L. Ruzzo (1995): Limits to parallel computation: P-completeness Theory. Oxford University Press, New York, Oxford.
  15. Kristoffer Arnsfelt Hansen & Michal Koucký (2010): A New Characterization of ACC^0 and Probabilistic CC^0. Computational Complexity 19(2), pp. 211–234, doi:10.1007/s00037-010-0287-z.
  16. Neil Immerman (1987): Languages that capture complexity classes. SIAM Journal of Computing 16(4), pp. 760–778, doi:10.1137/0216051.
  17. Neil Immerman (1988): Nondeterministic Space is Closed Under Complementation. SIAM Journal of Computing 17(5), pp. 935–938, doi:10.1137/0217058.
  18. Neil Immerman (1999): Descriptive Complexity. Springer, doi:10.1007/978-1-4612-0539-5.
  19. Ker-I Ko (1989): Distinguishing conjunctive and disjunctive reducibilities by sparse sets. Information and Computation 81(1), pp. 62–87, doi:10.1016/0890-5401(89)90029-1.
  20. Richard E. Ladner, Nancy A. Lynch & Alan L. Selman (1975): A comparison of polynomial time reducibilities. Theoretical Computer Science 1(2), pp. 103–123, doi:10.1016/0304-3975(75)90016-X.
  21. Niall Murphy & Damien Woods (2010): Uniformity conditions in natural computing. In: The 16th International Conference on DNA Computing and Molecular Programming (DNA 16), Preproceedings, pp. 109–120. HKUST, Hong Kong, China.
  22. Christos H. Papadimitriou (1993): Computational Complexity. Addison Wesley.
  23. Mario J. Pérez-Jiménez, Agustín Riscos-Núñez, Alvaro RomeroJiménez & Damien Woods (2009): Handbook of Membrane systems, chapter 12: Complexity – Membrane Division, Membrane Creation. Oxford University Press.
  24. Gheorghe Păun (2005): Further twenty six open problems in membrane computing. In: Proceedings of the Third Brainstorming Week on Membrane Computing, Sevilla (Spain). Fénix Editoria, pp. 249–262.
  25. Róbert Szelepcsényi (1988): The Method of Forced Enumeration for Nondeterministic Automata. Acta Informatica 26(3), pp. 279–284, doi:10.1007/BF00299636.
  26. Heribert Vollmer (1999): Introduction to Circuit Complexity: A Uniform Approach. Springer-Verlag New York, Inc., Secaucus, NJ, USA, doi:10.1007/978-3-662-03927-4.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org