A WORST-CASE OF CIRCULARITY TEST ALGORITHMS FOR ATTRIBUTE GRAMMARS

Authors
WU PC WANG FJ
Citation
Pc. Wu et Fj. Wang, A WORST-CASE OF CIRCULARITY TEST ALGORITHMS FOR ATTRIBUTE GRAMMARS, ACM transactions on programming languages and systems, 17(2), 1995, pp. 228-232
Citations number
7
Categorie Soggetti
Computer Sciences","Computer Science Software Graphycs Programming
Journal title
ACM transactions on programming languages and systems → ACNP
ISSN journal
01640925
Volume
17
Issue
2
Year of publication
1995
Pages
228 - 232
Database
ISI
SICI code
0164-0925(1995)17:2<228:AWOCTA>2.0.ZU;2-F
Abstract
Although the circularity test problem for attribute grammars (AGs) has been proven to be intrinsically exponential, to date, a worst case fo r the existing circularity test algorithms has yet to be presented. Th is note presents a worst-case AG in which the number of incomparable d ependency graphs induced at the root is exponential. The worst case ca n help to clarify the complexity of the problem.