Generation, recognition, and learning in finite state Optimality Theory

In this work I present a computational analysis of three fundamental problems in Optimality Theory (OT; Prince and Smolensky 1993): the generation of output forms, the recognition of input forms from surface forms, and the learning of phonological grammars.; Following Ellison (1994) I represent the constraints of OT with finite state machines that map input/output pairs to violations and represent the problem of optimization graph-theoretically as a shortest paths problem. I present and prove the correctness of algorithms for generation, recognition, and learning in the model I develop and provide some simple illustrative cases where these tasks can be done efficiently. Among the algorithms I present are methods for generating the set of non-harmonically-bounded output candidates for a given input and for recasting an entire grammar as a single finite state transducer that maps input forms directly to their optimal output counterparts.