Finite state automata (FSA) are ubiquitous in computer science. Two of the most important algorithms for FSA processing are the conversion of a non-deterministic finite automaton (NFA) to a deterministic finite automaton (DFA), and then the production of the unique minimal DFA for the original NFA. We exhibit a parallel disk-based algorithm that uses a cluster of 29 commodity computers to produce an intermediate DFA with almost two billion states and then continues by producing the corresponding unique minimal DFA with less than 800,000 states. The largest previous such computation in the literature was carried out on a 512-processor CM-5 supercomputer in 1996. That computation produced an intermediate DFA with 525,000 states and an unreported number of states for the corresponding minimal DFA. The work is used to provide strong experimental evidence satisfying a conjecture on a series of token passing networks. The conjecture concerns stack sortable permutations for a finite stack and a 3-buffer. The origins of this problem lie in the work on restricted permutations begun by Knuth and Tarjan in the late 1960s. The parallel disk-based computation is also compared with both a single-threaded and multi-threaded RAM-based implementation using a 16-core 128 GB large shared memory computer.
Finite state machines are also an important tool in natural language processing, and have been used for a wide variety of problems in computational linguistics. In a work presenting new applications of finite state automata to natural language processing @cite_32 , Mohri cites a number of examples, including: lexical analysis @cite_29 ; morphology and phonology @cite_31 ; syntax @cite_24 @cite_28 ; text-to-speech synthesis @cite_6 ; and speech recognition @cite_18 @cite_25 . Speech recognition, in particular, can benefit from the use of very large automata. @cite_16 , Mohri predicted:
@cite_18 @cite_28 @cite_29 @cite_32 @cite_6 @cite_24 @cite_31 @cite_16 @cite_25
2051846017 2007624857 1794686686 1971927919 2125529971 2612304886
INTEX is a text processor; it is usually used to parse corpora of several megabytes. It includes several built-in large coverage dictionaries and grammars represented by graphs; the user may add his her own dictionaries and grammars. These tools are applied to texts in order to locate lexical and syntactic patterns, remove ambiguities, and tag words. INTEX builds concordances and indexes of all types of patterns; it is used by linguists to analyse corpora, but can also be viewed as an information retrieval system. We describe new applications of the theory of automata to natural language processing: the representation of very large scale dictionaries and the indexation of natural language texts. They are based on new algorithms that we introduce and describe in detail. In particular, we give pseudocodes for the determinisation of string to string transducers, the deterministic union of p-subsequential string to string transducers, and the indexation by automata. We report on several experiments illustrating the applications. Local grammars can be represented in a very convenient way by automata. This paper describes and illustrates an efficient algorithm for the application of local grammars put in this form to lemmatized texts. A source of potential systematic errors in information retrieval is identified and discussed. These errors occur when base form reduction is applied with a (necessarily) finite dictionary. Formal methods for avoiding this error source are presented, along with some practical complexities met in its implementation. Finite-machines have been used in various domains of natural language processing. We consider here the use of a type of transducer that supports very efficient programs: sequential transducers. We recall classical theorems and give new ones characterizing sequential string-to-string transducers. Transducers that outpur weights also play an important role in language and speech processing. We give a specific study of string-to-weight transducers, including algorithms for determinizing and minizizing these transducers very efficiently, and characterizations of the transducers admitting determinization and the corresponding algorithms. Some applications of these algorithms in speech recognition are described and illustrated.