The Complexity of Finite Memory Programs with Recursion
Neil Deaton Jones, Steven S. Muchnick · Journal of the ACM · 1978
In order to study the effects of recurston on the complexity of program analysis, a fimte memory machme wtth recurstve calls is defined, as well as two parameter passmg mechamsms whmch extend the power of the language Close upper and lower bounds on the complexity of determmmg whether a program accepts the empty language are gtven for each of the three program models It ts shown that such questtons as acceptance of the empty set, eqmvalence, and so on are retractable even for these relatively simple programs