On the complexity of stream equality. Issue 2 (20th January 2014)

• Record Type: Journal Article
• Authors: ENDRULLIS, JÖRG; HENDRIKS, DIMITRI; BAKHSHI, RENA; ROŞU, GRIGORE
• Is Part Of: Journal of functional programming. Volume 24:Issue 2/3(2014)
• Page Start: 166
• Page End: 217
• Publication Date: 2014-01-20
• Subjects: Functional programming (Computer science) -- Periodicals
• DOI: 10.1017/S0956796813000324
• Languages: English
• ISSNs: 0956-7968

Abstract

Abstract: We study the complexity of deciding the equality of streams specified by systems of equations. There are several notions of stream models in the literature, each generating a different semantics of stream equality. We pinpoint the complexity of each of these notions in the arithmetical or analytical hierarchy. Their complexity ranges from low levels of the arithmetical hierarchy such as Π 0 2 for the most relaxed stream models, to levels of the analytical hierarchy such as Π 1 1 and up to subsuming the entire analytical hierarchy for more restrictive but natural stream models. Since all these classes properly include both the semi-decidable and co-semi-decidable classes, it follows that regardless of the stream semantics employed, there is no complete proof system or algorithm for determining equality or inequality of streams. We also discuss several related problems, such as the existence and uniqueness of stream solutions for systems of equations, as well as the equality of such solutions.