Convolution (computer science)

From Wikipedia, the free encyclopedia

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

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

Let x1x2... x|x|, y1y2... y|y|, z1z2... z|z|, ... be n words over ∑*. Let \ell denote the maximum length.

The convolution of these words is

(x_1,y_1,\ldots)(x_2,y_2,\ldots)\ldots(x_\ell,y_\ell,\ldots)

where for any index i > |w|, the wi 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 ⋆ ...

[edit] Example

The convolution of and, fish, be is

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


This article incorporates material from convolution on PlanetMath, which is licensed under the GFDL.

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.