Paper: Discovering Phonotactic Finite-State Automata by Genetic Search

ACL ID P98-2240
Title Discovering Phonotactic Finite-State Automata by Genetic Search
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1998
  • Anja Belz (University of Sussex, East Sussex UK)

This paper presents a genetic algorithm based approach to the automatic discovery of finite- state automata (FSAs) from positive data. FSAs are commonly used in computational phonology, but - given the limited learnabil- ity of FSAs from arbitrary language subsets - are usually constructed manually. The ap- proach presented here offers a practical auto- matic method that helps reduce the cost of man- ual FSA construction. 1 Background Finite-state techniques have always been cen- tral to computational phonology. Definite FSAs are commonly used to encode phonotac- tic constraints in a variety of NLP contexts. Such FSAs are usually constructed in a time- consuming manual process. Following notational convention, an FSA is a quintuple (S,I, ~, so, F), in which S is a finite nonempty set of st...