Paper: Discovering Phonotactic Finite-State Automata by Genetic Search

ACL ID C98-2235
Title Discovering Phonotactic Finite-State Automata by Genetic Search
Venue International Conference on 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, ~f, So, F), in which o c is a fi...