The bibliographic entry was discovered and compiled by a machine, and published without a person checking it against the publication. The publication itself is the authors' own work — this badge says nothing about it.
Even Simple Programs Are Hard To Analyze
The work
| Authors | Neil D. Jones; Steven S. Muchnick |
|---|---|
| Editors | |
| Type | article |
| Year | 1977 |
| Citekey | jones1977even |
Where it appeared
| Published in | Journal of the ACM |
|---|---|
| Publisher | Association for Computing Machinery (ACM) |
| Volume | 24 |
| Issue | 2 |
| Pages | 338--350 |
Identifiers
| DOI | 10.1145/322003.322016 |
|---|---|
| ISSN | 0004-5411 |
Access
| Landing page | https://doi.org/10.1145/322003.322016 |
|---|
From crossref.
Abstract
A simple programming language which corresponds in computational power to the class of generalized sequential machines with final states is defined. It is shown that a variety of questions of practical programming interest about the language are of nondeterministic linear space complexity. Extensions to the language are defined (adding arithmetic and array data structures) and their complexity properties are explored. It is concluded that questions about halting, equivalence, optimization, and so on are intractable even for very simple programming languages.
How it got here
| How it got here | agent via crossref |
|---|---|
| Added | 2026-10-24 06:33 UTC |
| Not denied by | a person 2026-10-29 17:12 UTC |
Filed under
Cite it as
@article{jones1977even,
title = {Even Simple Programs Are Hard To Analyze},
author = {Neil D. Jones and Steven S. Muchnick},
year = {1977},
journal = {Journal of the ACM},
publisher = {Association for Computing Machinery (ACM)},
volume = {24},
number = {2},
pages = {338--350},
issn = {0004-5411},
doi = {10.1145/322003.322016},
}
This record lives at https://refs.drheap.org/jones1977even/ and will keep doing so.