Turing-completeness of polymorphic stream equation systems

DOI10.4230/LIPICS.RTA.2012.256MaRDI QIDQ5111910zbMATH OpenOpenAlexFDO

Authors Florent Balestrieri, Christian Sattler

Publication date 27 May 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2012/3497/pdf/20.pdf

zbMATH Keywords

recursionstream functionsTuring-completeness

Mathematics Subject Classification ID

Other nonclassical models of computation (68Q09) Grammars and rewriting systems (68Q42) Abstract data types; algebraic specification (68Q65)

Recommendations

• On the complexity of stream equality
• Equality of streams is a \({\Pi}^0_2\)-complete problem
• scientific article; zbMATH DE number 785052
• The computational content of atomic polymorphism
• Polygraphic programs and polynomial-time functions

Cited in

(2)

• Characterizing polynomial time complexity of stream programs using interpretations
• Equality of streams is a \({\Pi}^0_2\)-complete problem

This page was built for publication: Turing-completeness of polymorphic stream equation systems

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