{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:38:07Z","timestamp":1787387887605,"version":"build-2736575974"},"reference-count":14,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1980,5]]},"abstract":"<jats:p>The computatiional complexity of several decidable problems about program schemes, recursion schemes, and simple programming languages is considered. The strong equivalence, weak equivalence, containment, halting, and divergence problems for the single variable program schemes and the linear monadic recursion schemes are shown to be $NP$-complete. The equivalence problem for the Loop 1 programming language is also shown to be $NP$-complete. Sufficient conditions for a program scheme problem to be $NP$-hard are presented. The strong equivalence problem for a subset of the single variable program schemes, the strongly free schemes, is shown to be decidable deterministically in polynomial time.<\/jats:p>","DOI":"10.1137\/0209031","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:21:58Z","timestamp":1109226118000},"page":"396-416","source":"Crossref","is-referenced-by-count":15,"title":["On the Computational Complexity of Program Scheme Equivalence"],"prefix":"10.1137","volume":"9","author":[{"given":"H. B.","family":"Hunt III","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"R. L.","family":"Constable","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S.","family":"Sahni","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/321765.321780"},{"key":"R2","unstructured":"R. L. Constable, H. B. Hunt, III, S. Sahni,  On the computational complexity of scheme equivalence, TR-74-201, Department of Computer Science, Cornell University, Ithaca, NY,  1974"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"S. A. Cook,  The complexity of theorem proving procedures,  Proceedings Third Annual ACM Symposium on Theory of Computing,  1971,  151\u2013158, May","DOI":"10.1145\/800157.805047"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80040-6"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/BF00264025"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"J. E. Hopcroft,  Z.  Kohavi, A.  Paz,  An nlogn algorithm for minimizing states in a finite automaton,  Theory of Machines and Computations, Academic Press,  1971,  189\u2013196","DOI":"10.1016\/B978-0-12-417750-5.50022-1"},{"key":"R7","volume-title":"Formal languages and their relation to automata","author":"Hopcroft John E.","year":"1969"},{"key":"R8","author":"Ianov I.","year":"1958","journal-title":"Cybernetics Problems I"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80027-9"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80022-8"},{"key":"R11","volume-title":"Currents in the theory of computing","author":"Manna Zohar","year":"1973"},{"key":"R12","unstructured":"A. R. Meyer, D. Ritchie,  Computational complexity and program structure,  1967, IBM research paper, May 15"},{"key":"R13","unstructured":"M. Paterson,  Equivalence problems in a model of computation, MIT A.I. Laboratory Technical Memo, 1, Massachusetts Institute of Technology, Cambridge, Ma,  1970"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1145\/321607.321621"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0209031","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:32:37Z","timestamp":1787337157000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0209031"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1980,5]]},"references-count":14,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1980,5]]}},"alternative-id":["10.1137\/0209031"],"URL":"https:\/\/doi.org\/10.1137\/0209031","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1980,5]]}}}