Turing-completeness of polymorphic stream equation systems

DOI10.4230/LIPICS.RTA.2012.256zbMATH Open1437.68064OpenAlexW2293641398MaRDI QIDQ5111910FDOQ5111910

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

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

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)

Cited In (2)

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

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)