1

ANGLUIN, D., AND VALIANT, L.G. 1979. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. Syst. Sci. 18, 155-193.

2

David A. Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC1, Journal of Computer and System Sciences, v.38 n.1, p.150-164, February 1989  [doi>10.1016/0022-0000(89)90037-8]

3

David A. Mix Barrington , Kevin Compton , Howard Straubing , Denis Thérien, Regular languages in NC1, Journal of Computer and System Sciences, v.44 n.3, p.478-499, June 1992  [doi>10.1016/0022-0000(92)90014-A]

4

David A. Mix Barrington , Denis Thérien, Finite monoids and the fine structure of NC1, Journal of the ACM (JACM), v.35 n.4, p.941-952, Oct. 1988  [doi>10.1145/48014.63138]

5

Ravi B. Boppana , Michael Sipser, The complexity of finite functions, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991

6

CHANDRA, A. K., FORTUNE, S., AND LIPTON, R. 1985. Unbounded fan-in circuits and associative functions. J. Comput. Syst. Sci. 30, 222-234.

7

COHEN, R. F., AND TAMASSIA, R. 1995. Dynamic expression trees and their applications. Algorithmica 13, 245-265.

8

FREDMAN, M. L. 1978. Observations on the complexity of generating quasi-Gray codes. SIAM J. Comput. 7, 134-146.

9

Michael L. Fredman, The Complexity of Maintaining an Array and Computing Its Partial Sums, Journal of the ACM (JACM), v.29 n.1, p.250-260, Jan. 1982  [doi>10.1145/322290.322305]

10

M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States  [doi>10.1145/73007.73040]

11

FURS7, M., SAXE, J., AND SIPSER, M. 1984. Parity, circuits and the polynomial time hierarchy. Math. Syst. Theory 17, 13-27.

12

Johan Håstad, Computational limitations of small-depth circuits, MIT Press, Cambridge, MA, 1987

13

KROHN, K., AND RHODES, J. 1965. Algebraic theory of machines. I. Prime decomposition theorem for finite semigroups and machines. Trans. Am. Math. Soc. 116, 450-464.

14

Peter Bro Miltersen , Sairam Subramanian , Jeffrey Scott Vitter , Roberto Tamassia, Complexity models for incremental computation, Theoretical Computer Science, v.130 n.1, p.203-236, Aug. 1, 1994  [doi>10.1016/0304-3975(94)90159-7]

15

VAN EMDE BOAS, P., KAAS, R., AND ZIJLSTRA, E. 1977. Design and implementation of an efficient priority queue. Math. Syst. Theory 10, 99-127.

16

Andrew C-C. Yao, Separating the polynomial-time hierarchy by oracles, Proc. 26th annual symposium on Foundations of computer science, p.1-10, October 1985, Portland, Oregon, United States

H. Buhrman , P. B. Miltersen , J. Radhakrishnan , S. Venkatesh, Are bitvectors optimal?, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.449-458, May 21-23, 2000, Portland, Oregon, United States

Stephen Alstrup , Thore Husfeldt , Theis Rauhe, Dynamic nested brackets, Information and Computation, v.193 n.2, p.75-83, 15 September 2004

Mihai Păatraşcu , Erik D. Demaine, Tight bounds for the partial-sums problem, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana

Mihai Patracu , Corina E. Tarnia, On dynamic bit-probe complexity, Theoretical Computer Science, v.380 n.1-2, p.127-142, June, 2007

Gudmund Skovbjerg Frandsen: colleagues

Peter Bro Miltersen: colleagues

Sven Skyum: colleagues