Files in this item



application/pdfEquality 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
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)

Item Statistics