On the Complexity of Stream Equality

J. Endrullis, R.D.A. Hendriks, R.R. Bakhshi, G. Rosu

Research output: Contribution to JournalArticleAcademicpeer-review


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 Π
Original languageEnglish
JournalJournal of Functional Programming
Publication statusAccepted/In press - 2014


Dive into the research topics of 'On the Complexity of Stream Equality'. Together they form a unique fingerprint.

Cite this