The intersection of Finite State Automata and Definite Clause Grammars

Details The intersection of Finite State Automata and Definite Clause Grammars The intersection of Finite State Automata and Definite Clause Grammars

1995-04-28

arxiv.org/abs/cmp-lg/9504026v1

Proceedings of the 33rd ACL. Boston 1995.

Computer Science

Computation and Language

7 pages. Requires pictexwd package. To appear in ACL 95

Scientific paper

Bernard Lang defines parsing as the calculation 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 concentrate 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 termination properties change drastically: we show that it is undecidable whether the intersection of a FSA and a DCG is empty (even if the DCG is off-line parsable). Furthermore we discuss approaches to cope with the problem.

Affiliated with

Also associated with

No associations

Rating

The intersection of Finite State Automata and Definite Clause Grammars does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The intersection of Finite State Automata and Definite Clause Grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The intersection of Finite State Automata and Definite Clause Grammars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-340573