# convolution

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

Let $x_{1}x_{2}\ldots x_{|x|},y_{1}y_{2}\ldots y_{|y|},z_{1}z_{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 $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

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

Title convolution Convolution1 2013-03-22 14:16:51 2013-03-22 14:16:51 mathcam (2727) mathcam (2727) 10 mathcam (2727) Definition msc 68Q45 msc 68Q70 msc 68R15 Language KleeneStar