Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze
Authors:
- Iii H. B. HuntIHIii H. B. Hunt
- D. J. RosenkrantzDRD. J. Rosenkrantz
- 1 August 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 15 (3) , 831-850
Abstract
Deterministic exponential lower time bounds are presented for analyzing recursion schemes and recursive programs. The lower bounds for recursion schemes hold for any interpretation with a nontrivial predicate, i.e. a predicate that is neither identically true nor identically false. The lower bounds for recursive programs hold for very simple programs in any recursive programming language with a nontrivial predicate. These lower time bounds hold for the executability, computational identity, totality, divergence, partial correctness, and total correctness problems.Keywords
This publication has 11 references indexed in Scilit:
- The complexity of monadic recursion schemes: exponential time boundsJournal of Computer and System Sciences, 1984
- On the Complexity of Flowchart and Loop Program Schemes and Programming LanguagesJournal of the ACM, 1982
- Verification Decidability of Presburger Array ProgramsJournal of the ACM, 1980
- The Complexity of Finite Memory Programs with RecursionJournal of the ACM, 1978
- Simple Programs Realize Exactly Presburger FormulasSIAM Journal on Computing, 1976
- Theory of Program Structures: Schemes, Semantics, Verification1975
- Program schemes, recursion schemes, and formal languagesJournal of Computer and System Sciences, 1973
- Characterizations of Pushdown Machines in Terms of Time-Bounded ComputersJournal of the ACM, 1971
- The Equivalence Problem of Simple ProgramsJournal of the ACM, 1970
- On formalised computer programsJournal of Computer and System Sciences, 1970