A Worst Case of Circularity Test Algorithms for Attribute Grammars

Pei Chi Wu, Feng-Jian Wang

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)228-232
Number of pages5
JournalACM Transactions on Programming Languages and Systems (TOPLAS)
Issue number2
StatePublished - Mar 1995


  • Attribute grammars
  • circularity test
  • dependency graphs


Dive into the research topics of 'A Worst Case of Circularity Test Algorithms for Attribute Grammars'. Together they form a unique fingerprint.

Cite this