Complexity characterizations of attribute grammar languages
type: Item
instance of: scholarly article
title: Complexity characterizations of attribute grammar languages
zbMATH Open document ID: 0672.68035
DOI: 10.1016/0890-5401(88)90025-9
author: Sophocles Efremidis
author: Christos Papadimitriou
author: Martha Sideri
published in: Information and Computation
publication date: 1988-01-01T00:00:00Z
review text: Die Autoren beantworten folgende Frage: Welche Obermenge der kontextfreien Sprachen können attributierte Grammatiken (Knuth '68) erzeugen, die solchen Restriktionen wie z.B. Einschränkungen der Attributwerte, endliche Anzahl von Attributen, etc. (Milton '77) unterliegen. Es werden die attributierten Grammatiken untersucht, deren Skelett eine kontextfreie azyklische Grammatik ist. Die Funktionen der Prädikate dieser Grammatiken sind in polynomieller Zeit berechenbar und vergrößern konstant die Ausgabelänge. Es wird gezeigt, daß die Klasse \({\mathcal A}^ p\) der von solchen Grammatiken generierten Sprachen mit der Klasse EXPTIME der von Turing-Maschinen in \(2^{cn}\) (c Konstante) akzeptierten Sprachen übereinstimmt. Außerdem wird bewiesen, daß die Klasse \({\mathcal A}^ p_ s\) der Sprachen, deren ``sparse trees'' in polynomieller Zeit berechenbar sind, ``gleich'' NP ist.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 03D15
zbMATH DE Number: 4100623
zbMATH Keywords: attribute grammars
zbMATH Keywords: context free languages
zbMATH Keywords: language generators
zbMATH Keywords: context free grammars
zbMATH Keywords: expressive power of attribute grammars
MaRDI profile type: Publication
full work available at URL: 0890-5401(88)90025-9
OpenAlex ID: W1971958814
cites work: The Complexity of Languages Generated by Attribute Grammars
cites work: The intrinsically exponential complexity of the circularity problem for attribute grammars
cites work: Semantics of context-free languages
description: scientific article; zbMATH DE number 4100623