|
|
|
Viewing Version
2
of
'convolution'
|
[ view 'convolution'
|
back to history
]
| Title of object: |
convolution |
| Canonical Name: |
Convolution2 |
| Type: |
Definition |
| Created on: |
2004-03-29 07:49:58 |
| Modified on: |
2004-03-29 07:59:07 |
| Classification: |
msc:68Q45, msc:68Q70, msc:68R15 |
| Keywords: |
words, strings |
Preamble:
% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here |
Content:
Let $\Sigma$ be an alphabet, $\#$ a symbol not in $\Sigma$.
Let $w_1,\ldots,w_m$ be words in $\Sigma^*$, $w_i=w_{i_1}w_{i_2}\ldots w_{i_{n_i}}$, $w_{i_j}\in\Sigma$. Let $l$ denote the maximum of the $n_i$.
The \emph{convolution} of these words is
$$(w_{1_1},\ldots,w_{m_1})(w_{1_2},\ldots,w_{m_2})\ldots(w_{1_l},\ldots,w_{m_l})$$where for $j>n_i$, $w_{i_j}=\#$. This is a new word in $((\Sigma\cup\{\#\})^n)^*$.
The convolution of $w_1,\ldots,w_m$ is sometimes denoted conv($w_1,\ldots,w_m$), or $w_1\star w_2\star\ldots\star w_m$ |
|
|
|
|
|
