Equality of Streams is a Π02-Complete Problem

Permalink

https://hdl.handle.net/2142/11190

Title: Equality of Streams is a Π02-Complete Problem
Author(s): Rosu, Grigore
Issue Date: 2006-04
Keyword(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.
Type of Resource: text
Permalink: http://hdl.handle.net/2142/11190
Copyright and License 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).