Published in Computational Phonology: First Meeting of the ACL
Special Interest Group in Computational Phonology, Proceedings
of the Workshop (1 July 1994), pages 59-70. Michael
MaxwellSummer Institute of Linguistics Abstract: A generate and
test algorithm is described which parses a surface form into one
or more lexical entries using linearly ordered phonological
rules. This algorithm avoids the exponential expansion of search
space which a naive parsing algorithm would face by encoding
into the form being parsed the ambiguities which arise during
parsing. The algorithm has been implemented and tested on real
language data, and its speed compares favorably with that of a
KIMMO-type parser. A generate and test algorithm is described
which uses linearly ordered phonological rules to parse a
surface form into one or more underlying (lexical) forms. Each
step of the derivation may be rendered visible during both
generation and test phases. The algorithm avoids an exponential
expansion of search space during the