On the complexity of stream equality
From MaRDI portal
Publication:2875229
DOI10.1017/S0956796813000324zbMATH Open1297.68050MaRDI QIDQ2875229FDOQ2875229
Authors: Jörg Endrullis, Dimitri Hendriks, Rena Bakhshi, Grigore Roşu 
Publication date: 14 August 2014
Published in: Journal of Functional Programming (Search for Journal in Brave)
Recommendations
- Equality of streams is a \({\Pi}^0_2\)-complete problem
- On the complexity of equalizing inequalities
- Proving equality of streams automatically
- Characterizing polynomial time complexity of stream programs using interpretations
- Streams of approximations, equivalence of recursive effectful programs
- Efficiency of Equivalence Algorithms
- Equivalence in the complexity of several problems
- Interpretation of stream programs: characterizing type 2 polynomial time complexity
- Complexity classes of equivalence problems revisited
- Time bounds for streaming problems
Cites Work
- Universal coalgebra: A theory of systems
- Initial Algebra Semantics and Continuous Algebras
- Title not available (Why is that?)
- A coinductive calculus of streams
- Title not available (Why is that?)
- A hidden agenda
- Behavioural differential equations: a coinductive calculus of streams, automata, and power series
- Nondeterministic Ω-Computations and the Analytical Hierarchy
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Correspondence between ALGOL 60 and Church's Lambda-notation
- Infinitary lambda calculus
- Rewrite, rewrite, rewrite, rewrite, rewrite, \dots
- Productivity of stream definitions
- Title not available (Why is that?)
- Context induction: A proof principle for behavioural abstractions and algebraic implementations
- Levels of undecidability in rewriting
- Decision problems for Turing machines
- Highlights in infinitary rewriting and lambda calculus
- Observational logic, constructor-based logic, and their duality.
- Title not available (Why is that?)
Cited In (8)
- Transducer degrees: atoms, infima and suprema
- Turing-completeness of polymorphic stream equation systems
- Equality of streams is a \({\Pi}^0_2\)-complete problem
- Characterizing polynomial time complexity of stream programs using interpretations
- Proving equality of streams automatically
- Checking equivalence of corecursive streams: an inductive procedure
- Degrees of streams
- On the complexity of equivalence of specifications of infinite objects
Uses Software
This page was built for publication: On the complexity of stream equality
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2875229)
