On the complexity of regular-grammars with integer attributes

DOI10.1016/J.JCSS.2010.05.006MaRDI QIDQ632805zbMATH OpenOpenAlexFDO

Authors M. Manna, Francesco Scarcello, N. Leone

Publication date 28 March 2011

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2010.05.006

attribute grammars computational complexity context-free grammars models of computation regular grammars

Analysis of algorithms and problem complexity (68Q25) Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Review text

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.

Recommendations

Cites work

Cited in

(2)

Describes a project that uses

Uses Software

This page was built for publication: On the complexity of regular-grammars with integer attributes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q632805)