TY - GEN

T1 - Equality of streams is a ∏20-complete problem

AU - Roşu, Grigore

PY - 2006/12/1

Y1 - 2006/12/1

N2 - This paper gives a precise characterization for the complexity of the problem of proving equal two streams defined with a finite number of equations: ∏20. Since the ∏20 class includes properly both the recursively enumerable and the co-recursively enumerable classes, this result implies that neither the set of pairs of equal streams nor the set of pairs of unequal streams is recursively enumerable. Consequently, one can find no algorithm for determining equality of streams, as well as no algorithm for determining inequality of streams. In particular, there is no complete proof system for equality of streams and no complete system for inequality of streams.

AB - This paper gives a precise characterization for the complexity of the problem of proving equal two streams defined with a finite number of equations: ∏20. Since the ∏20 class includes properly both the recursively enumerable and the co-recursively enumerable classes, this result implies that neither the set of pairs of equal streams nor the set of pairs of unequal streams is recursively enumerable. Consequently, one can find no algorithm for determining equality of streams, as well as no algorithm for determining inequality of streams. In particular, there is no complete proof system for equality of streams and no complete system for inequality of streams.

KW - Algebraic specification

KW - Infinite structures

KW - Streams

UR - http://www.scopus.com/inward/record.url?scp=34247185928&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=34247185928&partnerID=8YFLogxK

U2 - 10.1145/1159803.1159827

DO - 10.1145/1159803.1159827

M3 - Conference contribution

AN - SCOPUS:34247185928

SN - 1595933093

SN - 9781595933096

T3 - Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP

SP - 184

EP - 191

BT - ICFP'06 - Proceedings of the Eleventh ACM SIGPLAN International Conference on Functional Programming

T2 - ICFP'06 - Eleventh ACM SIGPLAN International Conference on Functional Programming

Y2 - 16 September 2006 through 21 September 2006

ER -