TR on Circularity Problem for Attribute Grammars

pcwu@csie.nctu.edu.tw (Pei-Chi Wu)
Wed, 12 Jan 1994 08:05:01 GMT

          From comp.compilers
Related articles
TR on Circularity Problem for Attribute Grammars pcwu@csie.nctu.edu.tw (1994-01-12)
| List of all articles for this month |
Newsgroups: comp.compilers
From: pcwu@csie.nctu.edu.tw (Pei-Chi Wu)
Keywords: attribute, report, FTP
Organization: Dep. Computer Sci. & Info Eng., Chiao Tung Univ., Taiwan, R.O.C
Date: Wed, 12 Jan 1994 08:05:01 GMT

Department of Computer Science and Information Engineering
National Chiao Tung University
Taiwan, Republic of China


Technical Report available via ftp service:


ftp site: ftp.csie.nctu.edu.tw (140.113.17.166)
directory: /papers/tech-report/1994
file: CSIE-94-1001.ps.Z


Please contact Pei-Chi Wu (pcwu@csie.nctu.edu.tw) for
any problem in retrieving report.


Regards,


    Pei-Chi Wu


-----
Report CSIE-94-1001
Title: Is Circularity Problem for Attribute Grammars Exponential-Time
Complete?
Authors: Pei-Chi Wu, Feng-Jian Wang
Keywords: complexity structure, exponential-space complete, alternating
Turing Machines.
ABSTRACT:
Although the circularity test problem for attribute grammars
has been proven to be intrinsically exponential, it is still unknown
whether the problem is EXPTIME-complete or EXPSPACE-complete. This
report addresses this open problem.


--

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.