Journal of Arti ial In telligen e Resear h 21 (2004) 287-317 Submitted 06/03; published 03/04 IDL-Expressions: A F ormalism for Represen ting and P arsing Finite Languages in Natural Language Pro essing Mark-Jan Nederhof markjan let.r ug.nl F a ulty of A rts, University of Gr oningen P.O. Dept. of Information Engine ering, University of Padua via Gr adenigo, 6/A I-35131 Padova, Italy Abstra t W e prop ose a formalism for represen tation of nite languages, referred to as the lass of IDL-expr essions, whi h om bines on epts that w ere only onsidered in isolation in existing formalisms. The suggested appli ations are in natural language pro essing, more sp e i ally in surfa e natural language generation and in ma hine translation, where a sen ten e is obtained b y rst generating a large set of andidate sen ten es, represen ted in a ompa t w a y, and then ltering su h a set through a parser. W e study sev eral formal prop erties of IDL-expressions and ompare this new formalism with more ...

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.