Equality of streams is a ∏20-complete problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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: ∏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.

Original languageEnglish (US)
Title of host publicationICFP'06 - Proceedings of the Eleventh ACM SIGPLAN International Conference on Functional Programming
Pages184-191
Number of pages8
DOIs
StatePublished - Dec 1 2006
EventICFP'06 - Eleventh ACM SIGPLAN International Conference on Functional Programming - Portland, OR, United States
Duration: Sep 16 2006Sep 21 2006

Publication series

NameProceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP
Volume2006

Other

OtherICFP'06 - Eleventh ACM SIGPLAN International Conference on Functional Programming
Country/TerritoryUnited States
CityPortland, OR
Period9/16/069/21/06

Keywords

  • Algebraic specification
  • Infinite structures
  • Streams

ASJC Scopus subject areas

  • Software

Cite this