Even Simple Programs Are Hard To Analyze

DOI10.1145/322003.322016zbMath0359.68014OpenAlexW2074674105MaRDI QIDQ4131614

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

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

Related Items (14)

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

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