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

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

2000-10-10

arxiv.org/abs/cs/0010015v1

Computer Science

Programming Languages

7 pages

Scientific paper

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 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.

Affiliated with

Also associated with

No associations

Rating

On Exponential-Time Completeness of the Circularity Problem for Attribute Grammars does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Exponential-Time Completeness of the Circularity Problem for Attribute Grammars, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Exponential-Time Completeness of the Circularity Problem for Attribute Grammars will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-722612