Even Simple Programs Are Hard To Analyze

DOI10.1145/322003.322016MaRDI QIDQ4131614zbMATH OpenOpenAlexFDO

Authors Neil D. Jones, Steven S. Muchnick

Publication date 1977

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

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

Mathematics Subject Classification ID

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

Cited in

(14)

• On the power of deep pushdown stacks
• Simultaneous (poly-time, log-space) lower bounds
• A characterization of time complexity by simple loop programs
• Some simplified undecidable and NP-hard problems for simple programs
• Logical and schematic characterization of complexity classes
• Program schemes, arrays, Lindström quantifiers and zero-one laws
• The regular-language semantics of second-order idealized ALGOL
• Games for complexity of second-order call-by-name programs
• Winning Regions of Pushdown Parity Games: A Saturation Method
• Program Schemes with Deep Pushdown Storage
• An observationally complete program logic for imperative higher-order functions
• Optimal strategies in pushdown reachability games
• Deciding bisimulation equivalences for a class of non-finite-state programs
• Complexity of proving program correctness

This page was built for publication: Even Simple Programs Are Hard To Analyze

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