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.
Future releases will include more grammars, other graph parsing algorithms, a generally more efficient implementation and a better Dot/Graphviz interface.
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.
Richard.Moot@labri.fr Last modified: Mon Sep 22 15:10:24 CEST 2008