Between Finite State and Prolog: Constraint-Based Automata for Efficient Recognition of Phrases

This note describes a new type of automaton that has been developed at CIS Munich for efficient recognition of phrases in large German corpora. The concept of a constraint-based automaton is tailored to sets of phrases where grammaticality depends on morphological agreement conditions. It incorporates features from three sides: traditional finite state techniques, methods from constraint programming, and, on the implementation side, technology from large-scale electronic dictionaries. We describe the main ideas behind the concept, and we give some experimental results that compare the performance of constraint based automata with Prolog. 1 Introduction In computational linguistics, efficient recognition of phrases is an important prerequisite for many ambitious goals, such as, e.g., automated extraction of terminology, part of speech disambiguation, and automated translation. If one wants to recognize a certain well-defined set of phrases, the question of which type of computational d..