Open AccessThe Complexity of Finite Memory Programs with Recursion
Author(s) -
Neil D. Jones,
Steven S. Muchnick
Publication year - 1976
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v5i68.6486
Subject(s) - decidability , undecidable problem , equivalence (formal languages) , pushdown automaton , presburger arithmetic , computer science , recursion (computer science) , pspace , discrete mathematics , mathematics , simple (philosophy) , halting problem , theoretical computer science , programming language , finite state machine , algorithm , computational complexity theory , turing machine , philosophy , epistemology , computation
In an earlier paper (JACM, 1976) we studied the computational complexity of a number of questions of both programming and theoretical interest (e.g. halting, looping, equivalence) concerning the behaviour of programs written in an extremely simple programming language. These finite memory programs or fmps model the behaviour of FORTRAN-like programs with a finite memory whose size can be determined by examination of the program itself. The present paper is a continuation in which we extend the analysis to include ALGOL-like programs (called fmp^(rec) s) with the finite memory augmented by an implicit pushdown stack used to support recursion. Our major results are the following. First, we show that at least deterministic exponential time is required to determine whether a program in the basic fmpr~C model accepts a nonempty set. Then we show that a model with a limited version of call-by-name requires exponential space to determine acceptance of a nonempty set, and that a more sophisticated model with rewritable conditional formal parametershas an undecidable halting problem. The same lower bounds apply to the equivalence problem, which in contrast to the situation for the basic fmp model is not known to be decidable (since it is not known whether equivalence of deterministic pushdown automata is decidable).