On the Complexity of the Circularity Test for Attribute Grammars

Abstract

It is shown that both the upper and the lower bounds on the time complexity of the circularity test for Knuth's attribute grammars are exponential functions of the size of the grammar description. This result implies the "intractability" of the circularity test in the sense that the implementation of a general algorithm is not feasible. Another significance of this result is that this is one of the first problems actually arising in practice which has been proven to be of exponential time complexity.