minicomplexity
short equal ends
 Given a short binary string, check that its $h$-long prefix and $h$-long suffix are identical.
 For every $h\geq 1$, short equal ends$h$ (or just srteqe$h$) is defined over the binary alphabet $\{\mathtt0,\mathtt1\}$. Its instances are all binary strings of length $2h$. An instance is positive if it is of the form $xx$. Otherwise, it is negative. E.g., $\mathtt{1100011000}$ is a positive instance of srteqe$5$, whereas $\mathtt{1100011100}$ is a negative instance. (Note that strings like $\mathtt{110001100}$ and $\mathtt{11000110001}$ are not appropriately long to be instances of the problem.)
 Introduced by Seiferas 1973, as a problem easy for single-pass 2DFAs but hard for 1NFAs. (The original definition included a delimiter between prefix and suffix, but this is not essential in this context.) The name “short equal ends” is suggested by this site. huh? See also equal ends, for the generalization to arbitrarily long inputs; and equality, for a related problem.
 – no record –
 – no record –