Is there a standard (common) notation for the following operation on binary strings?

Question

Typically, we use the notation $S = \{0, 1\}^n$ to denote the set of all $n$-bit strings. Suppose that I wanted to extract a subset of the strings where certain bits have some fixed values. For example, I could try defining $S' = \{s= s_n\ldots s_1 \in S : s_2 = 1, s_4=0, s_n = 1 \}$ to denote the set of $n$-bit strings where $s_2$, $s_4$ and $s_n$ have the specified values.

Given that I am going to need to define many such subsets, it would be useful to have some better notation.... say $S_{\{s_2 = 1, s_4 = 0, s_n = 1\}}$, though this doesn't look very appealing. For those perhaps more familiar with the literature than I am, is there a set of notation that is typically used to denote such subsets? If not, what might be a compact and appealing way to denote such a subset?

Answer 1

There are pattern languages [1].

A pattern is a string over a terminal alphabet $\Sigma$ and an (infinite) variable alphabet $V = \{x_i \mid i \in \mathbb{N} \}$. Let $p = \alpha_1 x_{i_1} \alpha_2 \dots x_{i_k} \alpha_{k_1}$ be a pattern with $\alpha_i \in \Sigma^*$ for $i \in [1..k+1]$ and $x_j \in V^*$ for $j \in \{i_1, \dots, i_k\}$; its language is defined as

$\qquad\displaystyle L(p) = \{ \alpha_1 \beta_{i_1} \alpha_2 \dots \beta_{i_k} \alpha_{k+1} \mid \beta_{i_1}, \dots, \beta_{i_k} \in \Sigma^* \}$.

Note that the $i_j$ need not be pairwise distinct in general -- that is $L(x_1x_1) = \{ww \mid w \in \Sigma^*\}$ -- but one can make that restriction.

This is stronger than what you need; you want to restrict the language of possible replacements to individual symbols, and you want the variables to be independent (i.e. the $i_j$ to be pairwise distinct). It is easy to adapt the definition:

A bit-pattern is a string over a terminal alphabet $\Sigma$ and a wildcard $\star$. Let $p = \alpha_1 \star \alpha_2 \dots \star \alpha_{k_1}$ be a pattern with $\alpha_i \in \Sigma^*$ for $i \in [1..k+1]$; its language is defined as

$\qquad\displaystyle L(p) = \{ \alpha_1 x_1 \alpha_2 \dots x_k \alpha_{k+1} \mid x_1, \dots, x_k \in \Sigma \}$.

This is so straight-forward and the concept of wildcards is so wide-spread that, actually, I don't think you even need a reference; just define whatever you need. If you do find a reference it does not hurt to cite it, of course.

---

1. Polynomial time inference of extended regular pattern languages by T. Shinohara (1982)

Answer 2

What Raphael calls bit-pattern here has been treated extensively for general alphabets under the name partial word mainly in combinatorics on words. Look for the work of Francine Blanchet-Sadri and co-authors.

What you are looking for would be called the set of all full words compatible with a given partial word. In my example from above, the partial word would be _0_11 where "_" represents the "hole" as they call it.

You always have to spell out the entire string of length n in this; no compact notation.

Answer 3

I do not think that there is a standard notation for this. A more compact notation would be taking the two decimal numbers that

1. have the bits that you want and all others zero
2. have ones exactly on the bits you want.

This way you could represent any variant with two numbers.

Example for n=5 and S{s2=1,s4=0,sn=1}: first number 00011 = 3; second number 01011 = 11. So S{3;11}. For fixed n, this would give a unique representation for each possible mask that you want. Anf for large n with many selected bits it would be much smaller, though less direct to understand.

Taking HEX numbers would be a bit more readable because every digit woudl correspond to three bits.