minicomplexity
moore separability
 Given a binary string, check that it can be split into substrings of the form $\mathtt0^*\mathtt1((\mathtt0{+}\mathtt1)^{h-2}\mathtt1)^+$.
 For every $h\geq 1$, moore separability$h$ (or just moore$h$) is defined over the binary alphabet $\{\mathtt0,\mathtt1\}$. Its instances are all binary strings. A binary string is a block if it has the form $\mathtt0^*\mathtt1((\mathtt0{+}\mathtt1)^{h-2}\mathtt1)^+$, namely it starts with zero or more $\mathtt0$s, and continues with two or more $\mathtt1$s separated by substrings of length $h{-}2$. E.g., if $h=5$, then the strings $\mathtt{00101010001}$, $\mathtt{00010001}$, and $\mathtt{11111}$ are blocks. In contrast, the strings $\mathtt{0010010}$ and $\mathtt{111101111}$ 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 moore$5$ $\mathtt{001011101010111110011}$ because it can be split into the substrings $\mathtt{00101110101}$   $\mathtt{0111110011}$ which are both blocks. In contrast, the string $\mathtt{001011101010011110011}$ is a negative instance, because there is no way to split it into blocks.
 Introduced by Moore 1971 (also Moore 1969), 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$: (In Moore 1971, the single final state was $h{-}1$; here, we have changed it to $1$, to increase symmetry while preserving all essential properties.) The name “moore separability” is suggested by this site. huh? See ott separability, hennie separability, and separability for three related problems.
 – no record –
 – no record –
 – no record –
 – no record –