Circularity Testing of Attribute Grammars Requires Exponential Time: A Simpler Proof

Resumé

Jazayeri, Ogden and Rounds have shown that the high time complexity of Knuth's algorithm for testing attribute grammars for circularity is no accident. It was proved that there is a constant c>0 such that any deterministic Turing Machine which correctly tests for circularity must run for more than 2 ^(cn/log n) steps on infinitely many attribute grammars (AGs) (the size of an AG is the number of symbols required to write it down). The proof was rather complex; the purpose of this note is to provide a simpler one.