Journal of the ACM Bibliography
S.
Skyum and L. G.
Valiant. A complexity theory based on Boolean algebra. Journal
of the ACM, 32(2):484-502, April 1985.
[BibTeX entry]
Selected papers that cite this one
- Foto Afrati, Stavros S. Cosmadakis, and Mihalis Yannakakis. On Datalog vs
polynomial time. Journal of Computer and System
Sciences, 51(2):177-196, October 1995.
- Eric Allender, José Balcázar, and Neil Immerman. A first-order
isomorphism theorem. SIAM Journal on Computing,
26(2):557-567, April 1997.
- David A. Mix Barrington, Chi-Jen Lu, Peter Bro Miltersen, and Sven
Skyum. Searching
constant width mazes captures the AC^0 hierarchy. In
15th Annual Symposium on Theoretical Aspects of Computer
Science, volume 1373 of Lecture Notes in Computer
Science, pages 73-83, Paris France, 25-27 February 1998.
Springer.
- Beate Bollig and Ingo Wegener. Completeness and non-completeness
results with respect to read-once projections. Information and
Computation, 143(1):24-33, 25 May 1998.
- Peter Clote. A
note on the monotone complexity of 2-REF. Information
Processing Letters, 57(3):117-123, 12 February 1996.
- Gudmund S. Frandsen, Mark Valence, and David A. Mix Barrington. Some results on
uniform arithmetic circuit complexity. Mathematical Systems
Theory, 27(2):105-124, March/April 1994.
- David W. Juedes and Jack H. Lutz. Completeness and weak completeness
under polynomial-size circuits. Information and
Computation, 125(1):13-31, 25 February 1996.
- Ch. Meinel and A. Slobodová A reducibility concept
for problems defined in terms of ordered binary decision diagrams.
Theory of Computing Systems, 30(5):495-518,
September/October 1997.
- Noam Nisan and Amnon Ta-Shma. Symmetric Logspace is closed
under complement. In Proceedings of the Twenty-Seventh Annual
ACM Symposium on the Theory of Computing, pages 140-146, Las
Vegas, Nevada, 29 May-1 June 1995.
- Kenneth W. Regan and Heribert Vollmer. Gap-languages and log-time
complexity classes. Theoretical Computer Science,
188(1-2):101-116, 30 November 1997.
- Iain A. Stewart. Comparing the
expressibility of languages formed using NP-complete operators.
Journal of Logic and Computation, 1(3):305-330, May 1991.
- Iain A. Stewart. Logical description
of monotone NP problems. Journal of Logic and
Computation, 4(4):337-357, August 1994.
Shortcuts: