Cornell University
Library
Cornell UniversityLibrary

eCommons

Help
Log In(current)
  1. Home
  2. Cornell Computing and Information Science
  3. Computer Science
  4. Computer Science Technical Reports
  5. A Counter-example for "A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars"

A Counter-example for "A Simpler Construction for Showing the Intrinsically Exponential Complexity of the Circularity Problem for Attribute Grammars"

File(s)
87-815.ps (128.38 KB)
87-815.pdf (399.74 KB)
Permanent Link(s)
https://hdl.handle.net/1813/6655
Collections
Computer Science Technical Reports
Author
Dill, Jens M.
Abstract

Jazayeri proposes a simpler construction for use in the proof by Jazayeri, Ogden, and Rounds that the circularity problem for attribute grammars has inherent exponential complexity. The simplification introduces a flaw that invalidates the proof. Correcting the flaw leaves the new construction only slightly simpler than the old.

Date Issued
1987-03
Publisher
Cornell University
Keywords
computer science
•
technical report
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR87-815
Type
technical report

Site Statistics | Help

About eCommons | Policies | Terms of use | Contact Us

copyright © 2002-2026 Cornell University Library | Privacy | Web Accessibility Assistance