Two heads are better than two tapes.
On the completeness of object-creating database transformation languages.
Semiring-based constraint satisfaction and optimization.
Dynamic word problems.
Decomposition of tautologies into regular formulas and strong completeness of connection-graph resolution.
Evaluating uniform expressions within two steps of minimum parallel time.