  We propose a formalism for representation of finite languages, referred to as
the class of IDL-expressions, which combines concepts that were only considered
in isolation in existing formalisms. The suggested applications are in natural
language processing, more specifically in surface natural language generation
and in machine translation, where a sentence is obtained by first generating a
large set of candidate sentences, represented in a compact way, and then by
filtering such a set through a parser. We study several formal properties of
IDL-expressions and compare this new formalism with more standard ones. We also
present a novel parsing algorithm for IDL-expressions and prove a non-trivial
upper bound on its time complexity.
