On the complexity of stream equality

DOI10.1017/S0956796813000324zbMATH Open1297.68050MaRDI QIDQ2875229FDOQ2875229

Jörg Endrullis, Grigore Roşu, Rena Bakhshi, Dimitri Hendriks

Publication date: 14 August 2014

Published in: Journal of Functional Programming (Search for Journal in Brave)

Mathematics Subject Classification ID

Functional programming and lambda calculus (68N18)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Universal coalgebra: A theory of systems
• Initial Algebra Semantics and Continuous Algebras
• A coinductive calculus of streams
• A hidden agenda
• Behavioural differential equations: a coinductive calculus of streams, automata, and power series
• Nondeterministic Ω-Computations and the Analytical Hierarchy
• Correspondence between ALGOL 60 and Church's Lambda-notation
• Infinitary lambda calculus
• Rewrite, rewrite, rewrite, rewrite, rewrite, \dots
• Productivity of stream definitions
• 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.

Cited In (3)

• Transducer degrees: atoms, infima and suprema
• Characterizing polynomial time complexity of stream programs using interpretations
• Checking equivalence of corecursive streams: an inductive procedure

Uses Software

• Haskell
• CIRC
• Maude

Recommendations

• Title not available (Why is that?) 👍 👎
• Efficiency of Equivalence Algorithms 👍 👎
• Equality of streams is a Π0 over 2-complete problem 👍 👎
• Streams of approximations, equivalence of recursive effectful programs 👍 👎
• Proving equality of streams automatically 👍 👎
• Complexity classes of equivalence problems revisited 👍 👎
• On the complexity of equalizing inequalities 👍 👎
• Characterizing polynomial time complexity of stream programs using interpretations 👍 👎
• Interpretation of Stream Programs: Characterizing Type 2 Polynomial Time Complexity 👍 👎
• Equivalence in the complexity of several problems 👍 👎

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)