This is the website of the Hyperion hyperedge replacement parser. It it a first implementation of many of my ideas presented in my TAG+2008 paper and the slides of my talks in Bordeaux and Chieti.

Hyperion is written in XSB Prolog. The core parser is a very small and very general implementation of Clemens Lautemann's dynamic programming algorithm for parsing graphs using hyperedge replacement grammars.

This is a very early release of Hyperion, but I hope it will help the comprehesion of my results to see them in action.


The current Hyperion distribution containts a number of example grammars.

Future releases will include more grammars, other graph parsing algorithms, a generally more efficient implementation and a better Dot/Graphviz interface.


Hyperion is provided under the GNU Lesser General Public License and any download constitutes an agreement to the terms of this licence.

Download Hyperion!


Lautemann, C. (1990), The complexity of graph languages generated by hyperedge replacement, Acta Informatica 27(5), pp. 399-421.

This paper describes the graph parsing algorithm used by Hyperion and analyses its complexity. Two conditions for polynomial parsing are presented. Though we do not satisfy the conditions for componentwise derivations, the limited s-separability condition gives us a polynomial algorithm.

Moot, R. (2008), Lambek grammars, tree adjoining grammars and hyperedge replacement grammars, in C. Gardent & A. Sarkar, eds, `Proceedings of TAG+9, The ninth international workshop on tree adjoining grammars and related formalisms', pp. 65-72, (Proceedings Paper, Slides).

This paper and the corresponding slides present the embedding result between Tree Adjoining Grammars, Hyperedge Replacement Grammars of order 2, multimodal categorial grammars and the Lambek-Grishin calculus.

Moot, R. (2008), `Lambek Grammars and Hyperedge Replacement Grammars', invited talk at Fifty Years of the Syntactic Calculus, 10-11 July 2008, Chieti (Slides).

The slides of this invited talk are an extended version of my TAG+ talk, with more emphasis on parsing as done by Hyperion.

Moot, R. (2008), `Lambek Grammars and Hyperedge Replacement Grammars' (Draft Report).

This draft report spells out the correspondence between multimodal categorial grammars, the Lambek-Grishin calculus and second-order Hyperedge Replacement Grammars in more detail. It's work in progress and some parts are still incomplete, so please do not cite, but I'd welcome any comments you might have.

Last modified: Mon Sep 22 15:10:24 CEST 2008