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.

Title	convolution
Canonical name	Convolution1
Date of creation	2013-03-22 14:16:51
Last modified on	2013-03-22 14:16:51
Owner	mathcam (2727)
Last modified by	mathcam (2727)
Numerical id	10
Author	mathcam (2727)
Entry type	Definition
Classification	msc 68Q45
Classification	msc 68Q70
Classification	msc 68R15
Related topic	Language
Related topic	KleeneStar