Complexity of Fractran and Productivity

DOI10.1007/978-3-642-02959-2_28zbMath1250.68087OpenAlexW1503481618MaRDI QIDQ5191114

Clemens Grabmayer, Jörg Endrullis, Dimitri Hendriks

Publication date: 28 July 2009

Published in: Automated Deduction – CADE-22 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-02959-2_28

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Theory of programming languages (68N15) Functional programming and lambda calculus (68N18) Complexity of computation (including implicit computational complexity) (03D15)

Related Items

Highlights in infinitary rewriting and lambda calculus ⋮ Unnamed Item ⋮ Behavioral Rewrite Systems and Behavioral Productivity ⋮ Lazy productivity via termination ⋮ Complexity of Fractran and Productivity ⋮ Unnamed Item

Uses Software

• FRACTRAN

Cites Work

• Unnamed Item
• Unnamed Item
• Termination of term rewriting using dependency pairs
• The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity)
• Degrees of Undecidability in Term Rewriting
• The 3x + 1 Problem and Its Generalizations
• Complexity of Fractran and Productivity
• The Undecidability of the Generalized Collatz Problem
• Productivity of Stream Definitions
• Equality of streams is a Π0 over 2-complete problem
• Strong Computability and Variants of the Uniform Halting Problem

This page was built for publication: Complexity of Fractran and Productivity