A Counter-example for "A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars"
Dill, Jens M.
Jazayeri proposes a simpler construction for use in the proof by Jazayeri, Ogden, and Rounds that the circularity problem for attribute grammars has inherent exponential complexity. The simplification introduces a flaw that invalidates the proof. Correcting the flaw leaves the new construction only slightly simpler than the old.
computer science; technical report
Previously Published As