Publikation
IDL-Expressions: A Compact Representation for Finite Languages in Generation Systems
Mark-Jan Nederhof; Giorgio Satta
In: Gerhard Jäger; Paola Monachesi; Gerald Penn; Shuly Wintner (Hrsg.). Proceedings of the 7th Conference on Formal Grammars (FG2002). Conference on Formal Grammar (FG), Trento, Italy, Pages 125-136, 2002.
Zusammenfassung
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.