Equality of streams is a ^0_2-complete problem

DOI10.1145/1159803.1159827MaRDI QIDQ5501465zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

algebraic specificationinfinite structuresstreams

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

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

Cited in

(10)

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

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)