Complexity characterizations of attribute grammar languages (Q1120290)

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.