Y by
I don't mean to add more versions of just for fun. The motivation is to make more symmetric. For example, we know that and are quite different.
One version is , where b stands for Bidirectional, and in the process we are allowed to insert a symbol to the beginning of the sequence as long as is avoided and the required sparsity is still preserved.
Another version is , where i stands for Insertion: we can insert any symbol anywhere with the same constraints.
Both these versions can have variant that only respects sparsity, and the process terminates whenever is present.
One version is , where b stands for Bidirectional, and in the process we are allowed to insert a symbol to the beginning of the sequence as long as is avoided and the required sparsity is still preserved.
Another version is , where i stands for Insertion: we can insert any symbol anywhere with the same constraints.
Both these versions can have variant that only respects sparsity, and the process terminates whenever is present.