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 language | English |
---|---|
Journal | Journal of Functional Programming |
DOIs | |
Publication status | Accepted/In press - 2014 |