Can I read Equality of streams is a Π0 over 2-complete problem on EtoBox?

Equality of streams is a Π0 over 2-complete problem by Grigore Roşu is a scholarly article available to read on EtoBox.

What is Equality of streams is a Π0 over 2-complete problem about?

This paper gives a precise characterization for the complexity of the problem of proving equal two streams defined with a finite number of equations: Π 0 2 . Since the Π 0 2 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.

Author

Grigore Roşu

Publisher

ACM

Published

2006

Language

EN