Preliminary versionA preliminary version of these results was presented in: Gudmond Skovbjerg Frandsen, Peter Bro Miltersen, and Sven Skyum. Dynamic word problems. In 34th Annual Symposium on Foundations of Computer Science, pages 470-479, Palo Alto, California, 3-5 November 1993. IEEE.
Selected papers that cite this one
- 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.
Selected references
- D. Angluin and L. G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. Journal of Computer and System Sciences, 18(2):155-193, April 1979.
- David A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC^1. Journal of Computer and System Sciences, 38(1):150-164, February 1989.
- David A. Mix Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. Regular languages in NC^1. Journal of Computer and System Sciences, 44(3):478-499, June 1992.
- David A. Mix Barrington and Denis Thérien. Finite monoids and the fine structure of NC^1. Journal of the ACM, 35(4):941-952, October 1988.
- Peter van Emde Boas, R. Kaas, and E. Zijlstra. Design and implementation of an efficient priority queue. Mathematical Systems Theory, 10:99-127, 1977.
- Ashok K. Chandra, Merrick L. Furst, and Richard J. Lipton. Multi-party protocols. In Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pages 94-99, Boston, Massachusetts, 25-27 April 1983.
- Robert F. Cohen and Roberto Tamassia. Dynamic expression trees and their applications (extended abstract). In Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 52-61, San Francisco, California, 28-30 January 1991.
- Michael L. Fredman. Observations on the complexity of generating quasi-Gray codes. SIAM Journal on Computing, 7(2):134-146, May 1978.
- Michael L. Fredman. The complexity of maintaining an array and computing its partial sums. Journal of the ACM, 29(1):250-260, January 1982.
- Michael L. Fredman and Michael E. Saks. The cell probe complexity of dynamic data structures. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pages 345-354, Seattle, Washington, 15-17 May 1989.
- Merrick Furst, James B. Saxe, and Michael Sipser. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17(1):13-27, April 1984.
- Peter Bro Miltersen, Sairam Subramanian, Jeffrey Scott Vitter, and Roberto Tamassia. Complexity models for incremental computation. Theoretical Computer Science, 130(1):203-236, 1 August 1994.
- Andrew Chi-Chih Yao. Separating the polynomial-time hierarchy by oracles (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, pages 1-10, Portland, Oregon, 21-23 October 1985. IEEE.