On Exponential-Time Completeness of the Circularity Problem for Attribute Grammars

Simple item page
dc.creatorWu, Pei-Chi
dc.date2000-10-10
dc.date.accessioned2026-07-07T03:16:37Z
dc.date.available2026-07-07T03:16:37Z
dc.descriptionAttribute grammars (AGs) are a formal technique for defining semantics of programming languages. Existing complexity proofs on the circularity problem of AGs are based on automata theory, such as writing pushdown acceptor and alternating Turing machines. They reduced the acceptance problems of above automata, which are exponential-time (EXPTIME) complete, to the AG circularity problem. These proofs thus show that the circularity problem is EXPTIME-hard, at least as hard as the most difficult problems in EXPTIME. However, none has given a proof for the EXPTIME-completeness of the problem. This paper first presents an alternating Turing machine for the circularity problem. The alternating Turing machine requires polynomial space. Thus, the circularity problem is in EXPTIME and is then EXPTIME-complete.
dc.description7 pages
dc.identifierhttps://arxiv.org/abs/cs/0010015
dc.identifierhttp://arxiv.org/abs/cs/0010015
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/30419
dc.subjectProgramming Languages
dc.subjectComputational Complexity
dc.subjectD.3.1; D.3.4; F.2.2; F.4.2
dc.titleOn Exponential-Time Completeness of the Circularity Problem for Attribute Grammars
dc.typetext

Files

Collections

arXiv