minicomplexity
ott separability
 Given a binary string, check that it can be split into substrings of the form $\mathtt1(\mathtt0{+}\mathtt1)^*\mathtt0$ or $\mathtt1((\mathtt0^*\mathtt1)^{h-1})^+$.
 For every $h\geq 1$, ott separability$h$ (or just ott$h$) is defined over the binary alphabet $\{\mathtt0,\mathtt1\}$. Its instances are all binary strings. A binary string is a block if (i) it starts with a $\mathtt1$, and (ii) if it also ends with a $\mathtt1$, then the number of $\mathtt1$s after the first one is a multiple of $h{-}1$. So, blocks ending with a $\mathtt0$ have the form $\mathtt1(\mathtt0{+}\mathtt1)^*\mathtt0$, while blocks ending with a $\mathtt1$ have the form $\mathtt1((\mathtt0^*\mathtt1)^{h-1})^+$. E.g., if $h=5$, then the strings $\mathtt{10}$, $\mathtt{1011011010110}$, $\mathtt{1011011}$, and $\mathtt{1011011010111}$ are blocks, whereas the strings $\mathtt{0011011}$, $\mathtt{101101}$, and $\mathtt{101101101011101}$ 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 ott$5$ $\mathtt{100010101011110111011011011}$ because it can be split into the substrings $\mathtt{1000}$   $\mathtt{10}$   $\mathtt{10}$   $\mathtt{101111011101}$   $\mathtt{1011011}$ which are all blocks. In contrast, the string $\mathtt{1000111011000111111}$ is a negative instance, because there is no way to split it into blocks.
 Introduced by Ott 1964, as a problem in 1N\1D which witnesses the exact value of the trade-off from 1NFAs to 1DFAs. Actually described only via the 1NFA that solves it, e.g., for $h=5$: A simplification was given by Meyer Fischer 1971(see hennie separability). The name “ott separability” is suggested by this site. huh? See moore separability and separability for other related problems.
 – no record –
 – no record –
 – no record –
 – no record –