Answers are grounded in this paper and cite their sources.
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 KEY WORDS AND PHRASES computational complexity, program analysts, program eqmvalence, recurstve programs, pushdown automata, call by name, finite memory programs CR CATEGORIES 5.22, 5.23, 5.24, 5 25, 5 27 General permtsslon to make fair use m teaching or research of all or part of this material is granted to mdtvtdual readers and to nonprofit hbranes acting for them provided that ACM's copyright nottce ts given and that reference Is made to the pubhcatton, to tts date of tssue, and to the fact that reprmtmg prtvtleges were granted by permission of the Assoctatton for Computmg Machinery To otherwtse repnnt a figure, table, other substantial excerpt, or the enttre work reqmres specific permtsston as does republlcatton, or systematic or multtple reproductton
No takes yet. Share an insight, caveat, or question.
Jones et al. (1978) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: