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

資訊工程學系

研究成果: Article › 同行評審

摘要

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.

原文	English
頁（從 - 到）	228-232
頁數	5
期刊	ACM Transactions on Programming Languages and Systems (TOPLAS)
卷	17
發行號	2
DOIs	https://doi.org/10.1145/201059.201064
出版狀態	Published - 3月 1995

存取文件

10.1145/201059.201064

其它文件與鏈接

Link to publication in Scopus

引用此

@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 (TOPLAS)",

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 (TOPLAS)

JF - ACM Transactions on Programming Languages and Systems (TOPLAS)

IS - 2

ER -