Equality of streams is a ^0_2-complete problem

DOI10.1145/1159803.1159827zbMATH Open1321.68288OpenAlexW2002608561WikidataQ130962995 ScholiaQ130962995MaRDI QIDQ5501465FDOQ5501465

Authors: Grigore Roşu 

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

Recommendations

• On the complexity of stream equality
• Proving equality of streams automatically
• On the complexity of equivalence of specifications of infinite objects
• Turing-completeness of polymorphic stream equation systems
• Degrees of streams

zbMATH Keywords

algebraic specificationstreamsinfinite structures

Mathematics Subject Classification ID

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)

Cited In (8)

• Complexity of Fractran and Productivity
• Behavioral Rewrite Systems and Behavioral Productivity
• Proving equality of streams automatically
• The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
• Soundness and completeness proofs by coinductive methods
• Coalgebras in functional programming and type theory
• A language-independent proof system for full program equivalence
• On the complexity of stream equality

This page was built for publication: Equality of streams is a \({\Pi}^0_2\)-complete problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501465)