Paper: The Intersection Of Finite State Automata And Definite Clause Grammars

ACL ID P95-1022
Title The Intersection Of Finite State Automata And Definite Clause Grammars
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1995
Authors

Bernard Lang defines parsing as ~ cal- culation of the intersection of a FSA (the input) and a CFG. Viewing the input for parsing as a FSA rather than as a string combines well with some approaches in speech understanding systems, in which parsing takes a word lattice as input (rather than a word string). Furthermore, certain techniques for robust parsing can be modelled as finite state transducers. In this paper we investigate how we can generalize this approach for unification grammars. In particular we will concen- trate on how we might the calculation of the intersection of a FSA and a DCG. It is shown that existing parsing algorithms can be easily extended for FSA inputs. However, we also show that the termi- nation properties change drastically: we show that it is undecidable whether...