{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:40:02Z","timestamp":1750246802209,"version":"3.41.0"},"reference-count":6,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[1995,3,1]],"date-time":"1995-03-01T00:00:00Z","timestamp":794016000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Program. Lang. Syst."],"published-print":{"date-parts":[[1995,3]]},"abstract":"<jats:p>\n            Although the circularity test problem for\n            <jats:italic>attribute grammars<\/jats:italic>\n            (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.\n          <\/jats:p>","DOI":"10.1145\/201059.201064","type":"journal-article","created":{"date-parts":[[2002,10,7]],"date-time":"2002-10-07T13:52:47Z","timestamp":1033998767000},"page":"228-232","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A worst case of circularity test algorithms for attribute grammars"],"prefix":"10.1145","volume":"17","author":[{"given":"Pei-Chi","family":"Wu","sequence":"first","affiliation":[{"name":"National Chiao Tung University"}]},{"given":"Feng-Jian","family":"Wang","sequence":"additional","affiliation":[{"name":"National Chiao Tung University"}]}],"member":"320","published-online":{"date-parts":[[1995,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/BF00264616","article-title":"Speeding up circularity tests for attribute grammars","volume":"21","author":"DERANSART P.","year":"1984","unstructured":"DERANSART , P. , JOURDAN , M. , AND LORHO , B. 1984 . Speeding up circularity tests for attribute grammars . Acta Informatica 21 , 375 - 391 . DERANSART, P., JOURDAN, M., AND LORHO, B. 1984. Speeding up circularity tests for attribute grammars. Acta Informatica 21,375-391.","journal-title":"Acta Informatica"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/58562.77393"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/322276.322283"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/361227.361231"},{"issue":"2","key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF01692511","article-title":"Semantics of context-free languages","volume":"2","author":"KNUTH D.E.","year":"1968","unstructured":"KNUTH , D.E. 1968 . Semantics of context-free languages . Math. Syst. Theory 2 , 2 , 127 - 145 . Correction: Mathematical Systems Theory, Vol. 5, No. 1, 1971, pp. 95-96. KNUTH, D.E. 1968. Semantics of context-free languages. Math. Syst. Theory 2, 2, 127-145. Correction: Mathematical Systems Theory, Vol. 5, No. 1, 1971, pp. 95-96.","journal-title":"Math. Syst. Theory"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1007\/BF00288969","article-title":"Testing attribute grammars for circularity","volume":"17","author":"RAIHA K.-J.","year":"1982","unstructured":"RAIHA , K.-J. AND SAARINEN , M. 1982 . Testing attribute grammars for circularity . Acta Informatica 17 , 185 - 192 . RAIHA, K.-J. AND SAARINEN, M. 1982. Testing attribute grammars for circularity. Acta Informatica 17, 185-192.","journal-title":"Acta Informatica"}],"container-title":["ACM Transactions on Programming Languages and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/201059.201064","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/201059.201064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:06:24Z","timestamp":1750244784000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/201059.201064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,3]]},"references-count":6,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1995,3]]}},"alternative-id":["10.1145\/201059.201064"],"URL":"https:\/\/doi.org\/10.1145\/201059.201064","relation":{},"ISSN":["0164-0925","1558-4593"],"issn-type":[{"type":"print","value":"0164-0925"},{"type":"electronic","value":"1558-4593"}],"subject":[],"published":{"date-parts":[[1995,3]]},"assertion":[{"value":"1995-03-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}