Let $\Sigma$ be an alphabet, $\#$ a symbol not in $\Sigma$ .

Let $x_1x_2\ldots x_{|x|},y_1y_2\ldots y_{|y|},z_1z_2\ldots z_{|z|},\ldots$ be $n$ words over $\Sigma^*$ . Let $l$ denote the maximum length.

The convolution of these words is $$(x_1,y_1,\ldots)(x_2,y_2,\ldots)\ldots(x_l,y_l,\ldots)$$ where for any index $i>|w|$ , the $w_i$ is $\#$ . This is a new word in $((\Sigma\cup\{\#\})^n)^*$ .

The convolution of $x,y,z,\ldots$ is sometimes denoted conv($x,y,z,\ldots$ ), or $x\star y\star z\star\ldots$

Example

The convolution of $and, fish, be$ is $$(a,f,b)(n,i,e)(d,s,\#)(\#,h,\#)$$

Notes