Equality of streams is a ∏ 2 0-complete problem

Research output: Contribution to journalArticlepeer-review

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: ∏ 2 0. Since the ∏ 2 0 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.

Original languageEnglish (US)
Pages (from-to)184-191
Number of pages8
JournalACM SIGPLAN Notices
Volume41
Issue number9
DOIs
StatePublished - Sep 1 2006

Keywords

  • Algebraic specification
  • Infinite structures
  • Streams

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Cite this