A Worst Case of Circularity Test Algorithms for Attribute Grammars

Pei Chi Wu, Feng-Jian Wang

Research output: Contribution to journalArticlepeer-review

Abstract

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)
Volume17
Issue number2
DOIs
StatePublished - Mar 1995

Keywords

  • Attribute grammars
  • circularity test
  • dependency graphs

Fingerprint

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

Cite this