A WORST-CASE OF CIRCULARITY TEST ALGORITHMS FOR ATTRIBUTE GRAMMARS
| dc.citation.epage | 232 | en_US |
| dc.citation.issue | 2 | en_US |
| dc.citation.spage | 228 | en_US |
| dc.citation.volume | 17 | en_US |
| dc.citation.woscount | 0 | |
| dc.contributor.author | WU, PC | en_US |
| dc.contributor.author | WANG, FJ | en_US |
| dc.contributor.department | 交大名義發表 | zh_TW |
| dc.contributor.department | 資訊工程學系 | zh_TW |
| dc.contributor.department | National Chiao Tung University | en_US |
| dc.contributor.department | Department of Computer Science | en_US |
| dc.date.accessioned | 2014-12-08T15:03:30Z | |
| dc.date.available | 2014-12-08T15:03:30Z | |
| dc.date.issued | 1995-03-01 | en_US |
| dc.description.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. | en_US |
| dc.identifier.doi | 10.1145/201059.201064 | en_US |
| dc.identifier.issn | 0164-0925 | en_US |
| dc.identifier.journal | ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1145/201059.201064 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/2038 | |
| dc.identifier.wosnumber | WOS:A1995RE61200004 | |
| dc.language.iso | en_US | en_US |
| dc.subject | ALGORITHMS | en_US |
| dc.subject | LANGUAGES | en_US |
| dc.subject | THEORY | en_US |
| dc.subject | ATTRIBUTE GRAMMARS | en_US |
| dc.subject | CIRCULARITY TEST | en_US |
| dc.subject | DEPENDENCY GRAPHS | en_US |
| dc.title | A WORST-CASE OF CIRCULARITY TEST ALGORITHMS FOR ATTRIBUTE GRAMMARS | en_US |
| dc.type | Note | en_US |