Paper: Anytime Algorithms For Speech Parsing?

ACL ID C94-2161
Title Anytime Algorithms For Speech Parsing?
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1994

This paper discusses to which extent the concept of "anytime algorithms" can be applied to parsing algo- rithms with feature unification. We first try to give a more precise definition of what an anytinm algorithm is. We arque that parsing algorithms have to be clas- sified as contract algorithms as opposed to (truly) it> terruptible algorithms. With the restriction that the transaction being active at the time an inl,errupt, is is- sued has to be COml)leted before the interrupt cart be executed, it is possible to provide a parser with linritcd anytime t)ehavior, which is in fact t)dng realized in our l)rototype.