---
abstract: '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 ${\mathord{\it 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.'
author:
- 'Leen Torenvliet[^1]'
- 'Marten Trautwein[^2]'
date: |
    *University of Amsterdam\
    Department of Mathematics and Computer Science\
    Plantage Muidergracht 24\
    1018 TV Amsterdam*
title: 'A Note on the Complexity of Restricted Attribute-Value Grammars'
---

\[section\] \[thm\][Corollary]{}

\[thm\][Lemma]{}

Introduction
============

Although a universal feature theory does not exist, there is a general understanding of its objects. The objects of feature theories are abstract linguistic objects, e.g., an object “sentence,” an object “masculine third person singular,” an object “verb,” an object “noun phrase.” These abstract objects have properties like “tense,” “number,” “predicate,” “subject.” The values of these properties are either atomic, like “present” and “singular,” or abstract 