A Note on the Complexity of Restricted Attribute-Value Grammars
| dc.creator | Torenvliet, Leen | |
| dc.creator | Trautwein, Marten | |
| dc.date | 1995-03-21 | |
| dc.date.accessioned | 2026-07-07T09:09:43Z | |
| dc.date.available | 2026-07-07T09:09:43Z | |
| dc.description | 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. | |
| dc.description | 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 from http://www.fwi.uva.nl/~mtrautwe/ | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9503021 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9503021 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/151137 | |
| dc.subject | Computation and Language | |
| dc.title | A Note on the Complexity of Restricted Attribute-Value Grammars | |
| dc.type | text |