minicomplexity
title Nondeterminism and the size of two-way finite automata
authors William J. Sakoda, Michael F. Sipser
meeting Symposium on Theory of Computing
year 1978
pages 275-286
topics complexity, asymptotics, and exact trade-offs; general alphabet; one-way, rotating, and two-way heads; deterministic and nondeterministic modes
features 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}$
doi 10.1145/800133.804357