A Worst Case of Circularity Test Algorithms for Attribute Grammars

Pei Chi Wu; Feng-Jian Wang

doi:10.1145/201059.201064

A Worst Case of Circularity Test Algorithms for Attribute Grammars

Pei Chi Wu, Feng-Jian Wang

Department of Computer Science

Research output: Contribution to journal › Article › peer-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 language	English
Pages (from-to)	228-232
Number of pages	5
Journal	ACM Transactions on Programming Languages and Systems (TOPLAS)
Volume	17
Issue number	2
DOIs	https://doi.org/10.1145/201059.201064
State	Published - Mar 1995

Keywords

Attribute grammars
circularity test
dependency graphs

Access to Document

10.1145/201059.201064

Cite this

@article{6370287329c14de581f70ca8cfcb2c74,

title = "A Worst Case of Circularity Test Algorithms for Attribute Grammars",

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.",

keywords = "Attribute grammars, circularity test, dependency graphs",

author = "Wu, {Pei Chi} and Feng-Jian Wang",

year = "1995",

month = mar,

doi = "10.1145/201059.201064",

language = "English",

volume = "17",

pages = "228--232",

journal = "ACM Transactions on Programming Languages and Systems",

issn = "0164-0925",

publisher = "Association for Computing Machinery (ACM)",

number = "2",

}

TY - JOUR

T1 - A Worst Case of Circularity Test Algorithms for Attribute Grammars

AU - Wu, Pei Chi

AU - Wang, Feng-Jian

PY - 1995/3

Y1 - 1995/3

N2 - 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.

AB - 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.

KW - Attribute grammars

KW - circularity test

KW - dependency graphs

UR - http://www.scopus.com/inward/record.url?scp=0029273220&partnerID=8YFLogxK

U2 - 10.1145/201059.201064

DO - 10.1145/201059.201064

M3 - Article

AN - SCOPUS:0029273220

SN - 0164-0925

VL - 17

SP - 228

EP - 232

JO - ACM Transactions on Programming Languages and Systems

JF - ACM Transactions on Programming Languages and Systems

IS - 2

ER -

A Worst Case of Circularity Test Algorithms for Attribute Grammars

Abstract

Keywords

Access to Document

Other files and links

Cite this