A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars
Mehdi Jazayeri · Journal of the ACM · 1981
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 construction