Although the circularity test problem for attribute grammars (AGs) has been proven to be intrinsically exponential, to date, a worst case for the existing circularity test algorithms has yet to be presented. This note presents a worst-case AG in which the number of incomparable dependency graphs induced at the root is exponential. The worst case can help to clarify the complexity of the problem.
|頁（從 - 到）||228-232|
|期刊||ACM Transactions on Programming Languages and Systems (TOPLAS)|
|出版狀態||Published - 3月 1995|