Even Simple Programs Are Hard To Analyze

DOI10.1145/322003.322016zbMATH Open0359.68014OpenAlexW2074674105MaRDI QIDQ4131614FDOQ4131614

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)

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

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)