Let \(\mathrm{strip}\) be the partial map on binary strings defined by: \(\mathrm{strip}(\varepsilon )\) is undefined, and for a bit \(b\) and a string \(v\), \(\mathrm{strip}(bv) = b\, \mathrm{strip}(v)\) when \(\mathrm{strip}(v)\) is defined, while otherwise \(\mathrm{strip}(1v) = \varepsilon \) and \(\mathrm{strip}(0v)\) is undefined. Then for every \(k \in \mathbb {N}\), \(\mathrm{strip}(0^k)\) is undefined.

Let \(\mathrm{strip}\) be the partial map on binary strings defined by: \(\mathrm{strip}(\varepsilon )\) is undefined, and for a bit \(b\) and a string \(v\), \(\mathrm{strip}(bv) = b\, \mathrm{strip}(v)\) when \(\mathrm{strip}(v)\) is defined, while otherwise \(\mathrm{strip}(1v) = \varepsilon \) and \(\mathrm{strip}(0v)\) is undefined. Then for every binary string \(u\) (possibly empty, possibly containing \(1\)s) and every \(k \in \mathbb {N}\), \(\mathrm{strip}(u\, 1\, 0^k) = u\).

Let \(\mathrm{strip}\) be the partial map on binary strings defined by: \(\mathrm{strip}(\varepsilon )\) is undefined, and for a bit \(b\) and a string \(v\), \(\mathrm{strip}(bv) = b\, \mathrm{strip}(v)\) when \(\mathrm{strip}(v)\) is defined, while otherwise \(\mathrm{strip}(1v) = \varepsilon \) and \(\mathrm{strip}(0v)\) is undefined. Then for every binary string \(v\): \(\mathrm{strip}(v)\) is undefined if and only if \(v = 0^{|v|}\) consists only of zeros; and for every binary string \(u\), \(\mathrm{strip}(v) = u\) if and only if \(v = u\, 1\, 0^k\) for some \(k \in \mathbb {N}\).

For all \(C, c \in \mathbb {N}\), the map \(\mathbb {N} \to \mathbb {N}\) given by \(n \mapsto n + (C+1)(n+1)^c\) is strictly increasing (also when \(c = 0\)).

For all \(C, c, n \in \mathbb {N}\),

For \(C, c, m \in \mathbb {N}\) let \(\mathrm{split}_{C,c}(m)\) be the least \(n \le m\) with \(n + (C+1)(n+1)^c = m\), and undefined if there is none. Then for all \(C, c, m, n \in \mathbb {N}\), \(\mathrm{split}_{C,c}(m) = n\) if and only if \(n + (C+1)(n+1)^c = m\).

For \(C, c, m \in \mathbb {N}\) let \(\mathrm{split}_{C,c}(m)\) be the least \(n \le m\) with \(n + (C+1)(n+1)^c = m\), and undefined if there is none. Then for all \(C, c \in \mathbb {N}\), \(\mathrm{split}_{C,c}(0)\) is undefined.

Let \(C, c \in \mathbb {N}\) and \(V \subseteq \{ 0,1\} ^{*}\), write \(\langle x, u\rangle \) for the self-delimiting pair encoding of binary strings \(x\) and \(u\) (\(x\) with every bit doubled, then the separator \(01\), then \(u\)), and let \(V^{\mathrm{pair}}_{C,c}\) be the set of strings that the aligned pair parser decodes as a pair \((x, u)\) with \(|u| = C(|x|+1)^c\) and \(xu \in V\). Then for all binary strings \(x\) and \(u\), \(\langle x, u\rangle \in V^{\mathrm{pair}}_{C,c}\) if and only if \(|u| = C(|x|+1)^c\) and \(xu \in V\).

Let \(C, c \in \mathbb {N}\) and \(V \subseteq \{ 0,1\} ^{*}\). The aligned pair parser reads a binary string in two-bit blocks from the left, taking \(00\) and \(11\) as the bits \(0\) and \(1\) of a first component until the first block \(01\), after which the remaining suffix is the second component; it fails on every other string. Let \(V^{\mathrm{pair}}_{C,c}\) be the set of strings that this parser decodes as a pair \((x, u)\) with \(|u| = C(|x|+1)^c\) and \(xu \in V\). If \(y\) is a binary string on which the parser fails, then \(y \notin V^{\mathrm{pair}}_{C,c}\).

Let \(C, c \in \mathbb {N}\) and \(V \subseteq \{ 0,1\} ^{*}\), and let \(V^{\mathrm{pad}}_{C,c}\) be the set of binary strings \(y\) such that, for the least \(n\) with \(n + (C+1)(n+1)^c = |y|\) (which must exist), the suffix \(v\) of \(y\) after its first \(n\) bits contains a \(1\), and the prefix \(u\) of \(v\) preceding its last \(1\) satisfies \(|u| \le C(n+1)^c\) and \(\langle x, u\rangle \in V\), where \(x\) is the first \(n\) bits of \(y\) and \(\langle x, u\rangle \) is the self-delimiting pair encoding (\(x\) with every bit doubled, then \(01\), then \(u\)). If \(y\) is a binary string such that no \(n \le |y|\) satisfies \(n + (C+1)(n+1)^c = |y|\), then \(y \notin V^{\mathrm{pad}}_{C,c}\).

Let \(C, c \in \mathbb {N}\) and \(V \subseteq \{ 0,1\} ^{*}\), and let \(V^{\mathrm{pad}}_{C,c}\) be the set of binary strings \(y\) such that, for the least \(n\) with \(n + (C+1)(n+1)^c = |y|\) (which must exist), the suffix \(v\) of \(y\) after its first \(n\) bits contains a \(1\), and the prefix \(u\) of \(v\) preceding its last \(1\) satisfies \(|u| \le C(n+1)^c\) and \(\langle x, u\rangle \in V\), where \(x\) is the first \(n\) bits of \(y\) and \(\langle x, u\rangle \) is the self-delimiting pair encoding (\(x\) with every bit doubled, then \(01\), then \(u\)). Then for all binary strings \(x\) and \(v\) with \(|v| = (C+1)(|x|+1)^c\), the concatenation \(xv\) lies in \(V^{\mathrm{pad}}_{C,c}\) if and only if \(v\) contains a \(1\) and the prefix \(u\) of \(v\) preceding its last \(1\) satisfies \(|u| \le C(|x|+1)^c\) and \(\langle x, u\rangle \in V\).

Let \(C, c \in \mathbb {N}\) and \(V \subseteq \{ 0,1\} ^{*}\), and let \(V^{\mathrm{pad}}_{C,c}\) be the set of binary strings \(y\) such that, for the least \(n\) with \(n + (C+1)(n+1)^c = |y|\) (which must exist), the suffix \(v\) of \(y\) after its first \(n\) bits contains a \(1\), and the prefix \(u\) of \(v\) preceding its last \(1\) satisfies \(|u| \le C(n+1)^c\) and \(\langle x, u\rangle \in V\), where \(x\) is the first \(n\) bits of \(y\) and \(\langle x, u\rangle \) is the self-delimiting pair encoding (\(x\) with every bit doubled, then \(01\), then \(u\)). Then for every binary string \(x\) (even one containing \(1\)s), the string \(x\, 0^{(C+1)(|x|+1)^c}\) does not lie in \(V^{\mathrm{pad}}_{C,c}\).

Let \(C, c \in \mathbb {N}\) and \(V \subseteq \{ 0,1\} ^{*}\), and let \(V^{\mathrm{pad}}_{C,c}\) be the set of binary strings \(y\) such that, for the least \(n\) with \(n + (C+1)(n+1)^c = |y|\) (which must exist), the suffix \(v\) of \(y\) after its first \(n\) bits contains a \(1\), and the prefix \(u\) of \(v\) preceding its last \(1\) satisfies \(|u| \le C(n+1)^c\) and \(\langle x, u\rangle \in V\), where \(x\) is the first \(n\) bits of \(y\) and \(\langle x, u\rangle \) is the self-delimiting pair encoding (\(x\) with every bit doubled, then \(01\), then \(u\)). Let \(x, u\) be binary strings and \(k \in \mathbb {N}\) with \(|u\, 1\, 0^k| = (C+1)(|x|+1)^c\) and \(C(|x|+1)^c \lt |u|\). Then \(x\, u\, 1\, 0^k \notin V^{\mathrm{pad}}_{C,c}\).

Let \(C, c \in \mathbb {N}\) and \(V \subseteq \{ 0,1\} ^{*}\), and let \(V^{\mathrm{pad}}_{C,c}\) be the set of binary strings \(y\) such that, for the least \(n\) with \(n + (C+1)(n+1)^c = |y|\) (which must exist), the suffix \(v\) of \(y\) after its first \(n\) bits contains a \(1\), and the prefix \(u\) of \(v\) preceding its last \(1\) satisfies \(|u| \le C(n+1)^c\) and \(\langle x, u\rangle \in V\), where \(x\) is the first \(n\) bits of \(y\) and \(\langle x, u\rangle \) is the self-delimiting pair encoding (\(x\) with every bit doubled, then \(01\), then \(u\)). Then for every binary string \(x\), there exists \(v\) with \(|v| = (C+1)(|x|+1)^c\) and \(xv \in V^{\mathrm{pad}}_{C,c}\) if and only if there exists \(u\) with \(|u| \le C(|x|+1)^c\) and \(\langle x, u\rangle \in V\).

For \(D, e, m \in \mathbb {N}\) let \(\mathrm{solve}_{D,e}(m)\) be the least \(i \le m\) with \(i + D(i+1)^e = m\), undefined if there is none, and for \(C, c, m \in \mathbb {N}\) let \(\mathrm{split}_{C,c}(m)\) be the least \(n \le m\) with \(n + (C+1)(n+1)^c = m\), undefined if there is none. Then for all \(C, c \in \mathbb {N}\), the partial functions \(\mathrm{solve}_{C+1,c}\) and \(\mathrm{split}_{C,c}\) on \(\mathbb {N}\) are equal.

Let \(\mathrm{strip}\) be the partial map on binary strings defined by: \(\mathrm{strip}(\varepsilon )\) is undefined, and for a bit \(b\) and a string \(v\), \(\mathrm{strip}(bv) = b\, \mathrm{strip}(v)\) when \(\mathrm{strip}(v)\) is defined, while otherwise \(\mathrm{strip}(1v) = \varepsilon \) and \(\mathrm{strip}(0v)\) is undefined. Let \(\mathrm{last}(v)\) be computed by reversing \(v\), discarding the leading \(0\)s of the reversal, and, if a \(1\) remains, deleting it and returning the reversal of what follows it, while \(\mathrm{last}(v)\) is undefined if no \(1\) remains. Then \(\mathrm{last}\) and \(\mathrm{strip}\) are equal as partial maps on \(\{ 0,1\} ^{*}\).

For \(C, c \in \mathbb {N}\) let \(\beta _{C,c}(z)\), for a binary string \(z\), be the bit \(1\) if \(z = \langle a, b\rangle \) is a well-formed self-delimiting pair encoding (\(a\) with every bit doubled, then \(01\), then \(b\)) with \(|b| \le C(|a|+1)^c\), and the bit \(0\) otherwise. Then for all \(C, c \in \mathbb {N}\) the map sending \(z\) to the one-bit string \(\beta _{C,c}(z)\) is polynomial-time computable: some finite multi-tape Turing machine over the binary alphabet computes it within \(D(n+1)^d\) steps on every input of length \(n\), for some constants \(D, d \in \mathbb {N}\).

Let \(V \subseteq \{ 0,1\} ^{*}\) be a language in \(\mathsf{P}\), and let \(\mathbf{1}_V(x)\) be the bit \(1\) if \(x \in V\) and \(0\) otherwise. Then the map sending a binary string \(x\) to the one-bit string \(\mathbf{1}_V(x)\) is polynomial-time computable: some finite multi-tape Turing machine over the binary alphabet computes it within \(D(n+1)^d\) steps on every input of length \(n\), for some constants \(D, d \in \mathbb {N}\).

Let \(V \subseteq \{ 0,1\} ^{*}\) be a language and let \(\mathbf{1}_V(x)\) be the bit \(1\) if \(x \in V\) and \(0\) otherwise. If the map sending a binary string \(x\) to the one-bit string \(\mathbf{1}_V(x)\) is polynomial-time computable, i.e. some finite multi-tape Turing machine over the binary alphabet computes it within \(D(n+1)^d\) steps on every input of length \(n\) for some constants \(D, d\), then \(V \in \mathsf{P}\).

For a binary string \(z\), let \(\pi _1(z)\) and \(\pi _2(z)\) be the two components \(a\) and \(b\) when \(z = \langle a, b\rangle \) is a well-formed self-delimiting pair encoding (\(a\) with every bit doubled, then \(01\), then \(b\)), and let both be the empty string otherwise. Then for all \(C, c \in \mathbb {N}\), the map sending \(z\) to the one-bit string recording whether \(C(|\pi _1(z)|+1)^c \le |\pi _2(z)|\) is polynomial-time computable: some finite multi-tape Turing machine over the binary alphabet computes it within \(D(n+1)^d\) steps on every input of length \(n\), for some constants \(D, d \in \mathbb {N}\).

Let \(C, c \in \mathbb {N}\) and let \(V \subseteq \{ 0,1\} ^{*}\) be a language in \(\mathsf{P}\). Then the language of binary strings \(y\) that are well-formed self-delimiting pair encodings \(y = \langle x, u\rangle \) (\(x\) with every bit doubled, then the separator \(01\), then \(u\) verbatim) with \(|u| = C(|x|+1)^c\) and \(xu \in V\) also belongs to \(\mathsf{P}\).

Let \(C, c \in \mathbb {N}\) and let \(V \subseteq \{ 0,1\} ^{*}\) be a language in \(\mathsf{P}\). Consider the language \(V^{\mathrm{pad}}_{C,c}\) of binary strings \(y\) such that, for the least \(n\) with \(n + (C+1)(n+1)^c = |y|\) (which must exist), the suffix \(v\) of \(y\) after its first \(n\) bits contains a \(1\), and the prefix \(u\) of \(v\) preceding its last \(1\) satisfies \(|u| \le C(n+1)^c\) and \(\langle x, u\rangle \in V\), where \(x\) is the first \(n\) bits of \(y\) and \(\langle x, u\rangle \) is the self-delimiting pair encoding (\(x\) with every bit doubled, then \(01\), then \(u\)). Then \(V^{\mathrm{pad}}_{C,c} \in \mathsf{P}\).