minicomplexity
 title Nondeterminism and the size of two-way finite automata William J. Sakoda, Michael F. Sipser Symposium on Theory of Computing 1978 275-286 complexity, asymptotics, and exact trade-offs; general alphabet; one-way, rotating, and two-way heads; deterministic and nondeterministic modes 1D is closed under $\leq_\text{h}$ 1N is closed under $\leq_\text{h}$ 2D is closed under $\leq_\text{h}$ 2N is closed under $\leq_\text{h}$ co-1D $\subseteq$ 1D co-1N $\nsupseteq$ 1N compact one-way liveness $\notin$ co-1N one-way liveness $\in$ 21D one-way liveness $\in$ 1N one-way liveness $\notin$ 1D one-way liveness $\notin$ co-1N one-way liveness is hard for 1N under $\leq^\text{t}_\text{h}$ separability is hard for 1N under $\leq^\text{t}_\text{h}$ two-way liveness $\in$ 21D two-way liveness $\in$ 2N two-way liveness is hard for 2N under $\leq^\text{t}_\text{h}$ 10.1145/800133.804357