GrammarProducts: Grammar products and higher-dimensional grammars

[ bioinformatics, formal-languages, gpl, library ] [ Propose Tags ]

An algebra of liner and context-free grammars.

This library provides the implementation of our theory of algebraic operations over linear and context-free grammars. Using algebraic operations, it is possible to construct complex dynamic programming algorithms from simpler "atomic" grammars.

Our most important contribution is the definition of a product of grammars which naturally leads to alignment-like algorithms on multiple tapes.

An efficient implementation of the resulting grammars is possible via the ADPfusion framework. The FormalGrammars library provides the required "Template Haskell" machinary.

Alternatively, the resulting grammars can also be pretty-printed in various ways (LaTeX, ANSI, Haskell module with signature and grammar).

Formal background can be found in two papers: @ Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler

Product Grammars for Alignment and Folding

submitted @


Christian Höner zu Siederdissen, Ivo L. Hofacker, and Peter F. Stadler

How to Multiply Dynamic Programming Algorithms

Brazilian Symposium on Bioinformatics (BSB 2013)

Lecture Notes in Bioinformatics 8213, Springer, Heidelberg
Change log changelog
Dependencies ADPfusion (>=0.2.0), ansi-wl-pprint, base (==4.*), bytestring, cmdargs (==0.10.*), containers, data-default, FormalGrammars (>=, HaTeX, lens, newtype, parsers, PrimitiveArray (>=, semigroups, transformers, trifecta [details]
License GPL-3.0-only
Copyright Christian Hoener zu Siederdissen, Ivo L. Hofacker, Peter F. Stadler, 2013
Author Christian Hoener zu Siederdissen, 2013
Category Formal Languages, Bioinformatics
Home page
Source repo head: git clone git://
Uploaded by ChristianHoener at Wed Dec 18 00:19:49 UTC 2013
Distributions NixOS:
Executables GrammarProductPP
Downloads 2625 total (37 in the last 30 days)
Rating (no votes yet) [estimated by rule of succession]
Your Rating
  • λ
  • λ
  • λ
Status Docs not available [build log]
Successful builds reported [all 8 reports]
Hackage Matrix CI


  • FormalLanguage
    • FormalLanguage.GrammarProduct
      • Op
        • FormalLanguage.GrammarProduct.Op.Add
        • FormalLanguage.GrammarProduct.Op.Chomsky
          • FormalLanguage.GrammarProduct.Op.Chomsky.Proof
        • FormalLanguage.GrammarProduct.Op.Common
        • FormalLanguage.GrammarProduct.Op.Greibach
          • FormalLanguage.GrammarProduct.Op.Greibach.Proof
        • FormalLanguage.GrammarProduct.Op.Linear
        • FormalLanguage.GrammarProduct.Op.Power
        • FormalLanguage.GrammarProduct.Op.Subtract
      • FormalLanguage.GrammarProduct.Parser


Maintainer's Corner

For package maintainers and hackage trustees