Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze

DOI10.1137/0215059MaRDI QIDQ3732943zbMATH OpenOpenAlexFDO

Authors H. B. III Hunt, Daniel J. Rosenkrantz

Publication date 1986

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0215059

zbMATH Keywords

computational complexitydivergencepartial correctnessexponential timedecision problemstotal correctnessstrong equivalenceexecutabilitytotalitycomputational identityrecursive programming language

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• The complexity of monadic recursion schemes: Exponential time bounds
• Non-polynomial worst-case analysis of recursive programs
• scientific article; zbMATH DE number 1114331
• Complexity of model checking recursion schemes for fragments of the modal mu-calculus
• scientific article; zbMATH DE number 1456960

Cited in

(2)

• Non-polynomial worst-case analysis of recursive programs
• The complexity of monadic recursion schemes: Exponential time bounds

This page was built for publication: Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze

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