The Complexity of Finite Memory Programs with Recursion

DOI10.1145/322063.322074MaRDI QIDQ4147590zbMATH OpenOpenAlexWikidataFDO

Authors Neil D. Jones, Steven S. Muchnick

Publication date 1978

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/322063.322074

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cited in

(5)

• Some simplified undecidable and NP-hard problems for simple programs
• An approach to deciding the observational equivalence of Algol-like languages
• An observationally complete program logic for imperative higher-order functions
• Complexity of proving program correctness
• Contextual equivalence for state and control via nested data

This page was built for publication: The Complexity of Finite Memory Programs with Recursion

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