DFKI-LT - IDL-Expressions: A Compact Representation for Finite Languages in Generation Systems

Mark-Jan Nederhof, Giorgio Satta
IDL-Expressions: A Compact Representation for Finite Languages in Generation Systems
in: Gerhard Jäger, Paola Monachesi, Gerald Penn, Shuly Wintner (eds.):
1 Proceedings of the 7th Conference on Formal Grammars (FG2002), Pages 125-136, Trento, Italy, o.A., 2002
 
We propose a representation for finite languages, called the class of IDLexpressions, which combines concepts that were only considered in isolation in previous representations. The suggested application is in generation systems where a sentence is obtained by first generating a large set of candidate sentences, represented in a compact way, and then filtering such a set through a parser. We study several formal properties of IDL-expressions, present a novel parsing algorithm for this representation and prove a non-trivial upper bound on its time complexity.
 
Files: BibTeX, Nederhof:2002:IEC.pdf