Vectorized finite state automata
András Kornai · 1999
. We present a technique of finite state parsing based on vectorization and describe the application of this technique to a well-known problem of natural language processing, that of extracting relational information from English text. We define Vectorized Finite State Automata, the theoretical model behind the applied system, and discuss their significance. 0 Introduction One of the persistent problems in building finite automata on the large scale required by actual applications is that the product and powerset constructions routinely used to implement intersection and nondeterminism can, in a few steps, increase the size of the state space beyond reasonable bounds. This paper will describe how to avoid this problem by structuring the state space as a (generalized) finite vector space. Section 1 of the paper introduces the problem by means of a highly artificial but simple example, informally presents the basic idea of Vectorized Finite State Automata (VFSA), and outlines the VFSA ...