Open AccessCircularity Testing of Attribute Grammars Requires Exponential Time: A Simpler Proof
Author(s) -
Neil D. Jones
Publication year - 1980
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v9i107.6522
Subject(s) - rule based machine translation , computer science , constant (computer programming) , exponential function , discrete mathematics , mathematics , algorithm , programming language , artificial intelligence , mathematical analysis
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.