Abstract
This talk will be based on the following forthcoming book: Finite-State Language Processing, edited by E. Roche and Y. Schabes, MIT Press (forthcoming 1997).Finite-state devices such as finite-sate automata, graphs and finite-sate transducers have been known since the emergence of computer science and are extensively used in areas as various as program compilation, hardware modeling or database management. In computational linguistics, although they were known for a long time, more powerful formalisms such as context-free grammars or unification grammars have been preferred. However, recent mathematical and algorithmic results in the field of finite-state technology have had a great impact on the representation of electronic dictionaries and natural language processing.In this talk I will speak about the problem of determinization of finite-state transducers and how this relates to parsing natural language sentences. Finite-state transducer determinization is more complex than the classical problem of determinizing finite-state automata and I will focus on the relation between determinization and factorization of finite-state functions through the little used concept of bimachine.