On the complexity of regular-grammars with integer attributes (Q632805)

An attribute grammar is a quadruple \(\mathit{AG} = (G, \mathit{Attr}, \mathit{Func}, \mathit{Pred})\) where \(G\) is a regular (context-free) grammar; \(\mathit{Attr}\) is a set of integer attributes associated with the nonterminals of \(G\); \(\mathit{Func}\) is a set of functions associated with the production rules of \(G\), assigning values to attributes by means of arithmetic expressions over the set \(S\) of operators of absolute value, addition, subtraction, integer division, modulo reduction, multiplication; \(\mathit{Pred}\) is a set of predicates, associated with the production rules of \(G\), cheking values of attributes. A predicate is a Boolean combination of comparison predicates of the form \(E_1\odot E_2\), where \(\odot\) is one of the signs in \(\{<,\leq,=,>,\geq,\neq\}\), and \(E_1,E_2\) are arithmetic expressions over \(S\). The language \(L(AG)\) generated by \(AG\) is the set of all strings derived by some valid parse tree for \(AG\). It is shown that PARSE is tractable for the following classes of integer attribute grammars: (i) deterministic regular strict grammars with arithmetic expressions over \(S_1\) (which is \(S\) without multiplication); (ii) general (possibly ambiguous) regular strict grammars with arithmetic expressions over \(S_1\); (iii) deterministic regular grammars with arithmetic expressions over \(S_1\) without the strict-restriction; (iv) deterministic regular strict grammars with arithmetic operators from \(S\). In particular, PARSE is \textbf{L}-complete in case (i); \textbf{NL}-complete in case (ii); \textbf{P}-complete in cases (iii) and (iv). The authors employ \(AG\) as a system for ontology-based information extraction used in real-word applications.