By

This thesis is concerned with the use of a logical language for specifying mappings between strings of symbols; specifically, the regular relations, those which can be com-puted by finite-state transducers. Because of their efficiency and flexibility, regular relations and finite-state transducers are widely used in Natural Language Process-ing (NLP) for tasks such as grapheme-to-phoneme conversion, morphological analysis and generation, and shallow syntactic parsing. By exploiting logical representations for finite-state transductions, the technique advocated in this thesis combines efficient processing with the advantages of declarative specification, thus taking a step in the direction of providing finite-state NLP with the best of both worlds. Previous work has demonstrated how all sets of strings recognized by finite-state automata can be described in monadic second-order logic. A formula of this logic describing a set can be automatically compiled into the finite-state automaton recog-nizing that set. Although this compilation is extremely inefficient in the theoretical worst case, recent work has shown that it can function quite efficiently for a range o