Journal of the ACM Bibliography

Selected papers that cite this one

• S. Abiteboul, C. H. Papadimitriou, and V. Vianu. The power of reflective relational machines. In Proceedings, Ninth Annual IEEE Symposium on Logic in Computer Science, pages 230-240, Paris, France, 4-7 July 1994. IEEE Computer Society Press.

• Serge Abiteboul, Christos H. Papadimitriou, and V. Vianu. Reflective relational machines. Information and Computation, 143(2):110-136, 15 June 1998.

• Serge Abiteboul, Moshe Y. Vardi, and Victor Vianu. Fixpoint logics, relational machines, and computational complexity. Journal of the ACM, 44(1):30-56, January 1997.

• Eric Allender and Vivek Gore. A uniform circuit lower bound for the permanent. SIAM Journal on Computing, 23(5):1026-1049, October 1994.

• Rajeev Alur, Thomas A. Henzinger, and Orna Kupferman. Alternating-time temporal logic. In 38th Annual Symposium on Foundations of Computer Science, pages 100-109, Miami Beach, Florida, 20-22 October 1997. IEEE.

• R. Beigel and J. Goldsmith. Downard separation fails castastrophically for limited nondeterminism classes. SIAM Journal on Computing, 27(5):1420-1429, October 1998.

• J.-C. Birget. Two-way automata and length-preserving homomorphisms. Mathematical Systems Theory, 29(3):191-226, May/June 1996.

• Jean-Camille Birget. The state complexity of \overline{Sigma^* \overline{L}} and its connection with temporal logic. Information Processing Letters, 58(4):185-188, 27 May 1996.

• Andreas Blass, Yuri Gurevich, and Dexter Kozen. A zero-one law for logic with a fixed-point operator. Information and Control, 67(1-3):70-90, October/November/December 1985.

• Stephen Bloch. On parallel hierarchies and R^i_k. Annals of Pure and Applied Logic, 89(2-3):231-273, 8 December 1997.

• S. A. Bloch, J. F. Bruss, and J. Goldsmith. Sharply bounded alternation and quasilinear time. Theory of Computing Systems, 31(2):187-214, March/April 1998.

• Anthony J. Bonner and Tomasz Imielinski. Reusing and modifying rulebases by predicate substitution. Journal of Computer and System Sciences, 54(1):136-166, February 1997.

• Allan Borodin, Stephen A. Cook, Patrick W. Dymond, Walter L. Ruzzo, and Martin Tompa. Two applications of inductive counting for complementation problems. SIAM Journal on Computing, 18(3):559-578, June 1989.

• Liming Cai and Jianer Chen. On the amount of nondeterminism and the power of verifying. SIAM Journal on Computing, 26(3):733-750, June 1997.

• Liming Cai, Jianer Chen, Rodney Downey, and Michael Fellows. On the structure of parameterized problems in NP. Information and Computation, 123(1):38-49, 15 November 1995.

• Liming Cai, Jianer Chen, and Johan Håstad. Circuit bottom fan-in and computational power. SIAM Journal on Computing, 27(2):341-355, March 1998.

• Surajit Chaudhuri and Moshe Y. Vardi. On the equivalence of recursive and nonrecursive Datalog programs. Journal of Computer and System Sciences, 54(1):61-78, February 1997.

• P. Clote. Nondeterministic stack register machines. Theoretical Computer Science, 178(1-2):37-76, 30 May 1997.

• Anne Condon. Space-bounded probabilistic game automata. Journal of the ACM, 38(2):472-494, April 1991.

• Anne Condon. The complexity of stochastic games. Information and Computation, 96(2):203-224, February 1992.

• Anne Condon, Joan Feinberg, Carsten Lund, and Peter Shor. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, April 1997.

• Costas Courcoubetis and Mihalis Yannakakis. The complexity of probabilistic verification. Journal of the ACM, 42(4):857-907, July 1995.

• Carsten Damm and Markus Holzer. Inductive counting for width-restricted branching programs. Information and Computation, 130(1):91-99, 10 October 1996.

• C. Damm, M. Holzer, and P. Rossmanith. Experssing uniformity via oracles. Theory of Computing Systems, 30(4):355-366, July/August 1997.

• Doron Drusinsky and David Harel. On the power of bounded concurrency I: Finite automata. Journal of the ACM, 41(3):517-539, May 1994.

• Cynthia Dwork and Larry Stockmeyer. Finite state verifiers I: The power of interaction. Journal of the ACM, 39(4):800-828, October 1992.

• E. Allen Emerson, Tom Sadler, and Jai Srinivasan. Efficient temporal satisfiability. Journal of Logic and Computation, 2(2):173-210, May 1992.

• J. Engelfriet, T. Harju, A. Proskurowski, and G. Rozenberg. Characterization and complexity of uniformly nonprimitive labeled 2-structures. Theoretical Computer Science, 154(2):247-282, 5 February 1996.

• Viliam Geffert. A communication hierarchy of parallel computations. Theoretical Computer Science, 198(1-2):99-130, 30 May 1998.

• Noa Globerman and David Harel. Complexity results for two-way and multi-pebble automata and their logics. Theoretical Computer Science, 169(2):161-184, 5 December 1996.

• Jean Goubault. Rigid E-unifiability is DEXPTIME-complete. In Proceedings, Ninth Annual IEEE Symposium on Logic in Computer Science, pages 498-506, Paris, France, 4-7 July 1994. IEEE Computer Society Press.

• Etienne Grandjean. Complexity of the first-order theory of almost all finite structures. Information and Control, 57(2/3):180-204, May/June 1983.

• Adam J. Grove, Joseph Y. Halpern, and Daphne Koller. Asymptotic conditional probabilities: The unary case. SIAM Journal on Computing, 25(1):1-51, February 1996.

• S. Gupta. Alternating time versus deterministic time: A separation. Mathematical Systems Theory, 29(6):661-672, November/December 1996.

• W. G. Handley. Deterministic summation modulo B_n, the semigroup of binary relations on {0, 1, ..., n-1}. Theoretical Computer Science, 172(1-2):135-174, 10 February 1997.

• U. Hertrampf, H. Vollmer, and K. W. Wagner. On balanced versus unbalanced computation trees. Mathematical Systems Theory, 29(4):411-421, July/August 1996.

• Tirza Hirst and David Harel. On the power of bounded concurrency II: Pushdown automata. Journal of the ACM, 41(3):540-554, May 1994.

• Oscar H. Ibarra, Nicholas Q. Tran, and Tao Yang. On the parallel complexity of loops. Theoretical Computer Science, 179(1-2):381-395, 1 June 1997.

• Akira Ito, Katsushi Inoue, Itsuo Takanami, and Hiroshi Taniguchi. Two-dimensional alternating Turing machines with only universal states. Information and Control, 55(1-3):193-221, October/November/December 1982.

• Kazuo Iwama and Chuzo Iwamoto. A canonical form of vector machines. Information and Computation, 141(1):37-65, 25 February 1998.

• Birgit Jenner, Pierre McKenzie, and Denis Thérien. Logspace and logtime leaf languages. Information and Computation, 129(1):21-33, 25 August 1996.

• R. Kannan. Circuit-size lower bounds and non-reducibility to sparse sets. Information and Control, 55(1-3):40-56, October/November/December 1982.

• A. J. Kfoury, J. Tiuryn, and P. Urzyczyn. An analysis of ML typability. Journal of the ACM, 41(2):368-398, March 1994.

• Johannes Köbler and Thomas Thierauf. Complexity-restricted advice functions. SIAM Journal on Computing, 23(2):261-275, April 1994.

• Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Fast algorithms for finding randomized strategies in game trees. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 750-759, Montréal, Québec, Canada, 23-25 May 1994.

• C. Lautemann, T. Schwentick, and I. A. Stewart. Positive versions of polynomial time. Accepted for publication in Information and Computation. Final manuscript received for publication May 17, 1998.

• Ngoc-Minh Lê On determining optimal strategies in pursuit games in the plane. Theoretical Computer Science, 197(1-2):203-234, 15 May 1998. Mathematical Games.

• Mark Levene and George Loizou. Null inclusion dependencies in relational databases. Information and Computation, 136(2):67-108, 1 August 1997.

• Richard J. Lipton and Neal E. Young. Simple strategies for large zero-sum games with applications to complexity theory. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 734-740, Montréal, Québec, Canada, 23-25 May 1994.

• M. Li\'skiewicz. On the power of 1-tape off-line ATMs running in a bounded number of reversals. Mathematical Systems Theory, 28(4):329-339, July/August 1995.

• David R. Luginbuhl and Michael C. Loui. Hierarchies and space measures for pointer machines. Information and Computation, 104(2):253-270, June 1993.

• Ioan I. Macarie and Mitsunori Ogihara. Properties of probabilistic pushdown automata. Theoretical Computer Science, 207(1):117-130, 28 October 1998.

• Martín Matamala. Alternation on cellular automata. Theoretical Computer Science, 180(1-2):229-241, 10 June 1997.

• Alain J. Mayer and Larry J. Stockmeyer. The complexity of PDL with interleaving. Theoretical Computer Science, 161(1-2):109-122, 15 July 1996.

• G. L. McColm. Pebble games and subroutines in least fixed point logic. Information and Computation, 122(2):201-220, 1 November 1995.

• Carlo Mereghetti and Giovanni Pighizzini. Optimal simulations between unary automata. In 15th Annual Symposium on Theoretical Aspects of Computer Science, volume 1373 of Lecture Notes in Computer Science, pages 139-149, Paris France, 25-27 February 1998. Springer.

• Ron van der Meyden. The complexity of querying indefinite data about linearly ordered domains. Journal of Computer and System Sciences, 54(1):113-135, February 1997.

• Ron van der Meyden. Common knowledge and update in finite environments. Information and Computation, 140(2):115-157, 1 February 1998.

• Toshimi Minoura. Deadlock avoidance revisited. Journal of the ACM, 29(4):1023-1048, October 1982.

• Sarah E. Mocas. Separating classes in the exponential-time hierarchy from classes in PH. Theoretical Computer Science, 158(1-2):221-231, 20 May 1996.

• Rolf Niedermeier and Peter Rossmanith. Unambiguous computations and locally definable acceptance types. Theoretical Computer Science, 194(1-2):137-161, 10 March 1998.

• Rolf Niedermeier and Peter Rossmanith. Unambiguous auxiliary pushdown automata and semi-unbounded fan-in circuits. Information and Computation, 118(2):227-245, 1 May 1995.

• Kenneth W. Regan. Linear time and memory-efficient computation. SIAM Journal on Computing, 25(1):133-168, February 1996.

• Kenneth W. Regan and Heribert Vollmer. Gap-languages and log-time complexity classes. Theoretical Computer Science, 188(1-2):101-116, 30 November 1997.

• J. M. Robson. Alternation with restrictions on looping. Information and Control, 67(1-3):2-11, October/November/December 1985.

• Konstantin Skodinis and Egon Wanke. Emptiness problems of eNCE graph languages. Journal of Computer and System Sciences, 51(3):472-485, December 1995.

• Iain A. Stewart. Logical description of monotone NP problems. Journal of Logic and Computation, 4(4):337-357, August 1994.

• Jacobo Torán. Complexity classes defined by counting quantifiers. Journal of the ACM, 38(3):753-774, July 1991.

• Moshe Y. Vardi and Pierre Wolper. Reasoning about infinite computations. Information and Computation, 115(1):1-37, 15 November 1994.

• H. Venkateswaran and Martin Tompa. A new pebble game that characterizes parallel complexity classes. SIAM Journal on Computing, 18(3):533-549, June 1989.

• Hiroaki Yamamoto. On the power of alternation on reversal-bounded alternating Turing machines with a restriction. Theoretical Computer Science, 180(1-2):139-154, 10 June 1997.

Shortcuts: