On the Complexity of Stream Equality

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

Research output: Contribution to JournalArticleAcademicpeer-review

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

Fingerprint

Semantics

Cite this

Endrullis, J. ; Hendriks, R.D.A. ; Bakhshi, R.R. ; Rosu, G. / On the Complexity of Stream Equality. In: Journal of Functional Programming. 2014.
@article{02adc95ffc31400b9e2ab36883f5d0a2,
title = "On the Complexity of Stream Equality",
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 Π",
author = "J. Endrullis and R.D.A. Hendriks and R.R. Bakhshi and G. Rosu",
year = "2014",
doi = "10.1017/S0956796813000324",
language = "English",
journal = "Journal of Functional Programming",
issn = "0956-7968",
publisher = "Cambridge University Press",

}

On the Complexity of Stream Equality. / Endrullis, J.; Hendriks, R.D.A.; Bakhshi, R.R.; Rosu, G.

In: Journal of Functional Programming, 2014.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - On the Complexity of Stream Equality

AU - Endrullis, J.

AU - Hendriks, R.D.A.

AU - Bakhshi, R.R.

AU - Rosu, G.

PY - 2014

Y1 - 2014

N2 - 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 Π

AB - 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 Π

U2 - 10.1017/S0956796813000324

DO - 10.1017/S0956796813000324

M3 - Article

JO - Journal of Functional Programming

JF - Journal of Functional Programming

SN - 0956-7968

ER -