Generalized Convolution and Efficient Language Recognition

Abstract

Convolution is a broadly useful operation with applications including signal processing, machine learning, probability, optics, polynomial multiplication, and efficient parsing. Usually, however, this operation is understood and implemented in more specialized forms, hiding commonalities and limiting usefulness. This paper formulates convolution in the common algebraic framework of semirings and semimodules and populates that framework with various representation types. One of those types is the grand abstract template and itself generalizes to the free semimodule monad. Other representations serve varied uses and performance trade-offs, with implementations calculated from simple and regular specifications.

Of particular interest is Brzozowski’s method for regular expression matching. Uncovering the method’s essence frees it from syntactic manipulations, while generalizing from boolean to weighted membership (such as multisets and probability distributions) and from sets to n-ary relations. The classic trie data structure then provides an elegant and efficient alternative to syntax.

Pleasantly, polynomial arithmetic requires no additional implementation effort, works correctly with a variety of representations, and handles multivariate polynomials and power series with ease. Image convolution also falls out as a special case.

Links

• Extended version (with proofs and other additional details) on arXiv.org.
• Extended version with latest corrections (2019-04-17).
• GitHub repo with Haskell and LaTeX source code.
• Symbolic and Automatic Differentiation of Languages

BibTeX

Extended version (with proofs) on arXiv:

@article{Elliott2019-convolution-extended,
  author  = {Conal Elliott},
  title   = {Generalized convolution and efficient language recognition (extended version)},
  journal = {CoRR},
  mon     = mar,
  year    = {2019},
  volume  = {abs/1903.10677},
  url     = {http://conal.net/papers/convolution/}
}

Errata

• Version of March 25, 2019:
  • Figure 5, first word should be “class” (Ed Kmett).
  • Section 9, second paragraph: “Cofree ((->) Char N)” should be “Cofree ((->) Char) N”
  • Figure 3, second instance should be LeftSemimodule, not Semiring.