minicomplexity
hennie separability
 Given a binary string, check that it can be split into substrings of the form $\mathtt{1}(\mathtt{0}^*\mathtt{1})^{\lt h-1}\mathtt{0}^+$ or $\mathtt{1}(\mathtt{0}^*\mathtt{1})^{h-1}$.
 For every $h\geq 1$, hennie separability$h$ (or just hennie$h$) is defined over the binary alphabet $\{\mathtt0,\mathtt1\}$. Its instances are all binary strings. A binary string is a block if it starts with a $\mathtt1$, it contains $\leq h$ occurences of $\mathtt1$, and it ends with a $\mathtt1$ iff this number of occurences is exactly $h$. So, blocks ending with a $\mathtt0$ have the form $\mathtt1(\mathtt0^*\mathtt1)^{\lt h-1}\mathtt0^+$, while blocks ending with a $\mathtt1$ have the form $\mathtt1(\mathtt0^*\mathtt1)^{h-1}$. E.g., if $h=5$, then the strings $\mathtt{1011000}$, $\mathtt{10}$, $\mathtt{10000111001}$, and $\mathtt{11111}$ are blocks, whereas the strings $\mathtt{011111}$, $\mathtt{1000011001}$, and $\mathtt{100001110010}$ are not blocks. A binary string is a positive instance if it is a concatenation of blocks, i.e., if it can be split into blocks. If not, then it is a negative instance. E.g., the following string is a positive instance of hennie$5$ $\mathtt{1000 10 10 1010110001 11111}$ because it can be split into the substrings $\mathtt{1000}$   $\mathtt{10}$   $\mathtt{10}$   $\mathtt{1010110001}$   $\mathtt{11111}$ which are all blocks. In contrast, the string $\mathtt{100011101011000111111}$ is a negative instance, because there is no way to split it into blocks.
 Introduced by Meyer Fischer 1971, as a problem in 1N\1D which witnesses the exact value of the trade-off in the conversion from 1NFAs to 1DFAs. Actually described only via the 1NFA that solves it, e.g., for $h=5$: The case $h=4$ was an exercise in Frederick C. Hennie's book Finite-state models for logical machines (John Wiley and Sons, 1968). A very similar example was also given by Ott 1964 (see ott separability). The name “hennie separability” is suggested by this site. huh? See also moore separability and separability, for additional similar problems.
 – no record –
 – no record –
 – no record –
 – no record –