Convolution (computer science)

In computer science, specifically formal languages, a convolution is defined as follows:

Let ∑ be an alphabet, # a symbol not in ∑.

Let x₁x₂... x_|x|, y₁y₂... y_|y|, z₁z₂... z_|z|, ... be n words over ∑^*. 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, ... is sometimes denoted conv( x, y, z, ...), or x ⋆ y ⋆ z ⋆ ...

Example

The convolution of and, fish, be is

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

Last updated: 05-21-2005 23:38:41