A Note on the Complexity of Restricted Attribute-Value Grammars

Details A Note on the Complexity of Restricted Attribute-Value Grammars A Note on the Complexity of Restricted Attribute-Value Grammars

1995-03-21

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

Computer Science

Computation and Language

18 pages, also available by (1) anonymous ftp at ftp://ftp.fwi.uva.nl/pub/theory/illc/researchReports/CT-95-02.ps.gz ; (2) WWW

Scientific paper

The recognition problem for attribute-value grammars (AVGs) was shown to be undecidable by Johnson in 1988. Therefore, the general form of AVGs is of no practical use. In this paper we study a very restricted form of AVG, for which the recognition problem is decidable (though still NP-complete), the R-AVG. We show that the R-AVG formalism captures all of the context free languages and more, and introduce a variation on the so-called `off-line parsability constraint', the `honest parsability constraint', which lets different types of R-AVG coincide precisely with well-known time complexity classes.

Affiliated with

Also associated with

No associations

Rating

A Note on the Complexity of Restricted Attribute-Value 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 A Note on the Complexity of Restricted Attribute-Value Grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Note on the Complexity of Restricted Attribute-Value Grammars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-347137