Paper Info
Title
On exponential-time completeness of the circularity problem for attribute grammars
Abstract
Attribute 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 shown that the problem is EXPTIME-complete. This paper 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.
Year
DOI
Venue
2000
10.1145/963778.963783
ACM Transactions on Programming Languages and Systems (TOPLAS)
Keywords
DocType
Volume
exponential-time completeness,turing machine,difficult problem,ag circularity problem,automata theory,existing complexity proof,acceptance problem,defining semantics,formal technique,attribute grammar,circularity problem,computational complexity,programming language
Journal
26
Issue
ISSN
Citations 
1
0164-0925
0
PageRank 
References 
Authors
0.34
8
1
Name
Order
Citations
PageRank
Pei-Chi Wu14513.18