On the complexity of stream equality
From MaRDI portal
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
- scientific article; zbMATH DE number 5822570 (Why is no real title available?)
- scientific article; zbMATH DE number 3888893 (Why is no real title available?)
- scientific article; zbMATH DE number 3577197 (Why is no real title available?)
- scientific article; zbMATH DE number 1556014 (Why is no real title available?)
- scientific article; zbMATH DE number 1889386 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3387326 (Why is no real title available?)
- A coinductive calculus of streams
- A hidden agenda
- Behavioural differential equations: a coinductive calculus of streams, automata, and power series
- Context induction: A proof principle for behavioural abstractions and algebraic implementations
- Correspondence between ALGOL 60 and Church's Lambda-notation
- Decision problems for Turing machines
- Highlights in infinitary rewriting and lambda calculus
- Infinitary lambda calculus
- Initial Algebra Semantics and Continuous Algebras
- Levels of undecidability in rewriting
- Nondeterministic Ω-Computations and the Analytical Hierarchy
- Observational logic, constructor-based logic, and their duality.
- Productivity of stream definitions
- Rewrite, rewrite, rewrite, rewrite, rewrite, \dots
- Universal coalgebra: A theory of systems
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
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)
