On the complexity of regular-grammars with integer attributes
type: Item
instance of: scholarly article
title: On the complexity of regular-grammars with integer attributes
zbMATH Open document ID: 1218.68093
published in: Journal of Computer and System Sciences
publication date: 2011-03-28T00:00:00Z
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.
Mathematics Subject Classification ID: 68Q42
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 5870853
zbMATH Keywords: regular grammars
zbMATH Keywords: context-free grammars
zbMATH Keywords: attribute grammars
zbMATH Keywords: computational complexity
zbMATH Keywords: models of computation
author: M. Manna
author: Francesco Scarcello
author: N. Leone
describes a project that uses: CONSTRUCTOR
describes a project that uses: GAG
MaRDI profile type: Publication
full work available at URL: j.jcss.2010.05.006
OpenAlex ID: W2037019297
cites work: Attribute grammars, applications and systems. International summer school SAGA, Prague, Czechoslovakia, June 4-13, 1991. Proceedings
cites work: Q3485882
cites work: On Relating Time and Space to Size and Depth
cites work: Q4131653
cites work: Division in logspace-uniform NC
cites work: Attribute grammars. Definitions, systems and bibliography
cites work: Relating logic programs and attribute grammars
cites work: Q4875865
cites work: Complexity characterizations of attribute grammar languages
cites work: Faster Integer Multiplication
cites work: Deterministic context free languages
cites work: The Hardest Context-Free Language
cites work: Uniform constant-depth threshold circuits for division and iterated multiplication.
cites work: Q3811706
cites work: GAG: a practical compiler generator
cites work: Semantics of context-free languages
cites work: Q4413598
cites work: Classes of languages and linear-bounded automata
cites work: Attributed translations
cites work: Q5180413
cites work: One application of real-valued interpretation of formal power series.
cites work: Q4473158
cites work: Attribute grammars for unranked trees as a query language for structured documents
cites work: Expressiveness of structured document query languages based on attribute grammars
cites work: Parsing regular grammars with finite lookahead
cites work: Q4298260
cites work: Q5526130
cites work: Tree-size bounded alternation
cites work: Fast multiplication of large numbers
cites work: Q5541340
cites work: Q4486016
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: Q3762226
DOI: 10.1016/J.JCSS.2010.05.006
description: scientific article; zbMATH DE number 5870853