IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Equality of Streams is a Π02-Complete Problem

Show simple item record

Bookmark or cite this item: http://hdl.handle.net/2142/11190

Files in this item

File Description Format
PDF Equality of Streams is a Π02-Complete Problem.pdf (172KB) (no description provided) PDF
Title: Equality of Streams is a Π02-Complete Problem
Author(s): Rosu, Grigore
Subject(s): computer science
Abstract: This paper gives a precise characterization for the complexity of the problem of proving equal two streams defined with a finite number of equations: Π02. Since the Π02 class includes properly both the recursively enumerable and the co-recursively enumerable classes, this result implies that one can find no mechanical procedure to say when two streams are equal, as well as no procedure to say when two streams are not equal. In particular, there is no complete proof system for equality of streams and no complete system for dis-equality of streams.
Issue Date: 2006-04
Genre: Technical Report
Type: Text
URI: http://hdl.handle.net/2142/11190
Other Identifier(s): UIUCDCS-R-2006-2708
Rights Information: You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS: 2009-04-21
 

This item appears in the following Collection(s)

Show simple item record

Item Statistics

  • Total Downloads: 123
  • Downloads this Month: 2
  • Downloads Today: 0

Browse

My Account

Information

Access Key