Paper: A Polynomial-Order Algorithm For Optimal Phrase Sequence Selection From A Phrase Lattice And Its Parallel Layered Implementation

ACL ID C90-2054
Title A Polynomial-Order Algorithm For Optimal Phrase Sequence Selection From A Phrase Lattice And Its Parallel Layered Implementation
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1990
Authors

This paper deals with a problem of select- ing an optimal phrase sequence from a phrase lattice, which is often encountered in language processing such as word processing and post-processing for speech recognition. The problem is formulated as one of combina- torial optimization, and a polynomial order algorithm is derived. This algorithm finds an optimal phrase sequence and its dependen- cy structure simultaneously, and is there- fore particularly suited for an interface between speech recognition and various language processing. What the algorithm does is numerical optimization rather than sym- bolic operation unlike conventional pars- ers. A parallel and layered structure to implement the algorithm is also presented, Although the language taken up here is Japa- nese, the algorithm can b...