Equality of streams is a Π0 over 2-complete problem
From MaRDI portal
Publication:5501465
DOI10.1145/1159803.1159827zbMath1321.68288OpenAlexW2002608561MaRDI QIDQ5501465
Publication date: 3 August 2015
Published in: Proceedings of the eleventh ACM SIGPLAN international conference on Functional programming (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1159803.1159827
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Soundness and completeness proofs by coinductive methods ⋮ Coalgebras in functional programming and type theory ⋮ Behavioral Rewrite Systems and Behavioral Productivity ⋮ A language-independent proof system for full program equivalence ⋮ Complexity of Fractran and Productivity ⋮ The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)