- 1959: Quick sort invented by Tony Hoare
- 1964: Heap sort and heap data structure
- 1965: Schützenberger's theorem ˡ
- On finite monoids having only trivial subgroups - Marcel
Paul Schützenberger (1965)
- Every aperiodic language can be described via star-free languages ˡ
- 1971: Cook-Levin theorem
- (Boolean SAT is NP-complete)