minicomplexity
2D
 All problems that can be solved by 2DFAs of size polynomial in $h$.
 The class of families of problems $\mathcal L=(L_h)_{h\geq1}$ for which there exists a family of 2DFAs $\mathcal M=(M_h)_{h\geq1}$ and a polynomial $p$ such that every $M_h$ has at most $p(h)$ states and solves $L_h$.
 Introduced by Sakoda Sipser 1978, as the analog of  P  for 2FAs (in place of Turing machines) and for size (in place of time).
 – no record –
 – no record –
1D re-1D 2D/uny
1D re-1D 2D/uny co-1D rc-1D 1D/uny RD/uny SD/uny re-1D/uny re-RD/uny re-SD/uny re-2D/uny co-1D/uny rc-1D/uny
 – no record –
 – no record –
SD
SD RD re-RD re-SD
 – no record –
 – no record –