convolution

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

Let $x_1{x}_2\mathrm{\dots }{x}_{|x|},y_1{y}_2\mathrm{\dots }{y}_{|y|},z_1{z}_2\mathrm{\dots }{z}_{|z|},\mathrm{\dots }$ be $n$ words over ${\mathrm{\Sigma }}^{*}$. Let $l$ denote the maximum length.

The convolution of these words is

$$(x_1,y_1,\mathrm{\dots })(x_2,y_2,\mathrm{\dots })\mathrm{\dots }(x_l,y_l,\mathrm{\dots })$$

where for any $i>|w|$, the $w_i$ is $\mathrm{\#}$. This is a new word in ${({(\mathrm{\Sigma }\cup \{\mathrm{\#}\})}^n)}^{*}$.

The convolution of $x,y,z,\mathrm{\dots }$ is sometimes denoted conv($x,y,z,\mathrm{\dots }$), or $x\star y\star z\star \mathrm{\dots }$

Example

The convolution of $and,fish,be$ is

$$(a,f,b)(n,i,e)(d,s,\mathrm{\#})(\mathrm{\#},h,\mathrm{\#})$$

Notes

This definition bears no to the notion of convolution (http://planetmath.org/Convolution) of functions.