A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars
- 1 October 1981
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 28 (4) , 715-720
- https://doi.org/10.1145/322276.322283
Abstract
The recogmtion problem for alternating Turmg machines is reduced to the circularity problem for attnbute grammars, and thus an inherently exponential lower bound for the complexity of the circularity problem is derived Although the result is already known, the use of alternation allows a simpler constructionKeywords
This publication has 1 reference indexed in Scilit:
- The intrinsically exponential complexity of the circularity problem for attribute grammarsCommunications of the ACM, 1975