DFKI-LT - IDL-Expressions: A Compact Representation for Finite Languages in Generation Systems
IDL-Expressions: A Compact Representation for Finite Languages in Generation Systems
1 Proceedings of the 7th Conference on Formal Grammars (FG2002),
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