On the complexity of regular-grammars with integer attributes
Regular grammars with attributes overcome some limitations of classical regular grammars, sensibly enhancing their expressiveness. However, the addition of attributes increases the complexity of this formalism leading to intractability in the general case. In this paper, we consider regular grammars with attributes ranging over integers, providing an in-depth complexity analysis. We identify relevant fragments of tractable attribute grammars, where complexity and expressiveness are well balanced. In particular, we study the complexity of the classical problem of deciding whether a string belongs to the language generated by any attribute grammar from a given class C (call it PARSE(vertical bar C vertical bar)). We consider deterministic and ambiguous regular grammars, attributes specified by arithmetic expressions over {vertical bar vertical bar, +, -, divided by, %, *), and a possible restriction on the attributes composition (that we call strict composition). Deterministic regular grammars with attributes computed by arithmetic expressions over {vertical bar vertical bar, +. -, divided by, %} are P-complete. If the way to compose expressions is strict, they can be parsed in 1, and they remain tractable even if multiplication is allowed. Problem PARsE(vertical bar C vertical bar) becomes NP-complete for general regular grammars over {vertical bar vertical bar, -, divided by, %, *} with strict composition and for grammars over {vertical bar vertical bar, +, -, divided by, %} with unrestricted attribute composition. Finally, we show that even in the most general case the problem is in polynomial space. (C) (2)010 Elsevier Inc. All rights reserved.
attribute grammars computational complexity models of computation