標題: A WORST-CASE OF CIRCULARITY TEST ALGORITHMS FOR ATTRIBUTE GRAMMARS
作者: WU, PC
WANG, FJ
交大名義發表
資訊工程學系
National Chiao Tung University
Department of Computer Science
關鍵字: ALGORITHMS;LANGUAGES;THEORY;ATTRIBUTE GRAMMARS;CIRCULARITY TEST;DEPENDENCY GRAPHS
公開日期: 1-三月-1995
摘要: 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.
URI: http://dx.doi.org/10.1145/201059.201064
http://hdl.handle.net/11536/2038
ISSN: 0164-0925
DOI: 10.1145/201059.201064
期刊: ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS
Volume: 17
Issue: 2
起始頁: 228
結束頁: 232
顯示於類別:期刊論文


文件中的檔案:

  1. A1995RE61200004.pdf