minicomplexity
iterated length
 Given a unary string, check that its length is a nonzero multiple of $h$.
 For every $h\geq 1$, iterated length$h$ (or just ilen$h$) is defined over the unary alphabet $\{\mathtt0\}$. Its instances are all unary strings. An instance is positive if its length is $\lambda h$, for some $\lambda\geq1$; otherwise, the instance is negative. E.g., the two shortest positive instances of ilen$5$ are $\mathtt{00000}$ and $\mathtt{0000000000}$.
 Introduced by Ott 1964, as a problem of 1D against which the optimal 1NFA is no smaller than the optimal 1DFA. (Deviating from that definition, we insist that $\lambda\neq0$ so that length becomes the restriction of the problem to instances of length $\leq h$.) The name “iterated length” is suggested by this site. huh? See length for the variant where the length must be exactly $h$, and iterated long length for the variant where the length must be a multiple of $2^h$.
 – no record –
 – no record –
 – no record –