minicomplexity
equal ends
 Given a binary string, check that its $h$-long prefix and $h$-long suffix are identical.
 For every $h\geq 1$, equal ends$h$ (or just eqe$h$) is defined over the binary alphabet $\{\mathtt0,\mathtt1\}$. Its instances are all binary strings of length $\geq 2h$. An instance is positive if it is of the form $xwx$ where $|x|=h$. Otherwise, the instance is negative. E.g., $\mathtt{1100011000}$ and $\mathtt{11000101010101011000}$ are positive instances of eqe$5$, whereas $\mathtt{1100011100}$ and $\mathtt{11000101010101011100}$ are negative instances. (Note that strings like $\mathtt{110001100}$ are not long enough to be instances of the problem.)
 Introduced by Seiferas 1973, as a problem in 2D which requires $\ge2^h$ states on a single-pass 2DFA. The name “equal ends” is suggested by this site. huh? See short equal ends for the restriction where the input must be short, and equality for a related problem.
 – no record –
 – no record –