Assessing Complexity Results in Feature Theories

Details Assessing Complexity Results in Feature Theories Assessing Complexity Results in Feature Theories

1995-03-21

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

Computer Science

Computation and Language

16 pages, includes 3 Postscript figures, uses epsf.sty, also available by (1) anonymous ftp at ftp://ftp.fwi.uva.nl/pub/theo

Scientific paper

In this paper, we assess the complexity results of formalisms that describe the feature theories used in computational linguistics. We show that from these complexity results no immediate conclusions can be drawn about the complexity of the recognition problem of unification grammars using these feature theories. On the one hand, the complexity of feature theories does not provide an upper bound for the complexity of such unification grammars. On the other hand, the complexity of feature theories need not provide a lower bound. Therefore, we argue for formalisms that describe actual unification grammars instead of feature theories. Thus the complexity results of these formalisms judge upon the hardness of unification grammars in computational linguistics.

Affiliated with

Also associated with

No associations

Rating

Assessing Complexity Results in Feature Theories 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 Assessing Complexity Results in Feature Theories, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Assessing Complexity Results in Feature Theories will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-347141