{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:43:34Z","timestamp":1787341414354,"version":"build-2736575974"},"reference-count":9,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1972,3]]},"abstract":"<jats:p>We define the following classes of program schemata: ${\\text{P}} = $ class of schemes using a finite number of simple variables; ${\\text{P}}_{\\text{A}} = $ class of schemes using simple and subscripted variables (arrays); ${\\text{P}}_{{\\text{Ae}}} = $ class of schemes in ${\\text{P}}_{\\text{A}} = $, with the addition of an equality test on subscript values; ${\\text{P}}_{\\text{R}} = $ class of schemes allowing recursive functions; ${\\text{P}}_{\\text{L}} = $ class of schemes allowing labels as values; ${\\text{P}}_{\\text{M}} = $ class of schemes allowing a finite number of special markers as values; ${\\text{P}}_{{\\text{pds}}} = $ class of schemes using pushdown stores. With these, we can also discuss, for example, ${\\text{P}}_{{\\text{AM}}} $, the class of schemes allowing arrays, and special markers as values ; and ${\\text{P}}_{{\\text{AL}}} $, the class of schemes allowing arrays, and labels as values.<\/jats:p>\n                  <jats:p>We argue that ${\\text{P}}_{\\text{A}}$, ${\\text{P}}_{\\text{R}}$, and ${\\text{P}}_{\\text{L}}$ faithfully represent mechanisms of subscripting, recursion, and labels as values, that are present in many \u201creal\u201d programming languages.<\/jats:p>\n                  <jats:p>We show that \\[ {\\text{P}} &lt; {\\text{P}}_{\\text{R}} &lt; {\\text{P}}_{\\text{A}} \\equiv {\\text{P}}_{{\\text{AM}}} \\equiv {\\text{P}}_{{\\text{pdsM}}} \\equiv {\\text{P}}_{{\\text{Ae}}} \\equiv {\\text{EF}}, \\] where EF is Strong\u2019s class of effective functionals, assuming total functions and predicates. The inclusions ${\\text{P}} &lt; {\\text{P}}_{\\text{R}} &lt; {\\text{P}}_{\\text{A}} $ and equivalences ${\\text{P}}_{{\\text{AL}}} \\equiv {\\text{P}}_{{\\text{AM}}} \\equiv {\\text{P}}_{{\\text{pdsM}}} \\equiv {\\text{P}}_{{\\text{Ae}}} $ are effective. For example, given a program scheme in ${\\text{P}}_{{\\text{AM}}} $ we can construct an equivalent one in ${\\text{P}}_{{\\text{AL}}} $. However, we show that for any scheme in ${\\text{P}}_{{\\text{AM}}} $ an equivalent ${\\text{P}}_{\\text{A}} $ scheme exists, but also prove it cannot (in general) be constructed!<\/jats:p>\n                  <jats:p>We conjecture that ${\\text{P}}_{{\\text{A}}} $, ${\\text{P}}_{{\\text{AL}}} $, and equivalent classes are indeed \u201cuniversal.\u201d<\/jats:p>\n                  <jats:p>The above results assume that the uninterpreted functions and predicates are total. We discuss the problems which arise when they are partial. We define the class of multischemes and outline the relationship between the class ${\\text{P}}_{{\\text{Ae}}} $, multischemes, and Strong\u2019s nondeterministic and deterministic effective functionals.<\/jats:p>","DOI":"10.1137\/0201006","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T05:53:01Z","timestamp":1109224381000},"page":"66-118","source":"Crossref","is-referenced-by-count":65,"title":["On Classes of Program Schemata"],"prefix":"10.1137","volume":"1","author":[{"given":"Robert L.","family":"Constable","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gries","family":"David","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","volume-title":"Formal languages and their relation to automata","author":"Hopcroft John E.","year":"1969"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80022-8"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1145\/367177.367199"},{"key":"R4","unstructured":"M. S. Paterson, Masters Thesis,  Equivalence problems in a model of computation, Doctoral thesis, Cambridge Univ., Cambridge, England,  1967, Also Artificial Intelligence Tech. Memo, 1, M.I.T., Cambridge, Mass. , 1970, 153 pp."},{"key":"R5","unstructured":"M. S. Paterson, C. E. Hewitt,  Comparative schematology,  Conf. Record of Project MAC Conference on Concurrent Systems and Parallel Computation, Assoc. for Computing Machinery, New York,  1970,  119\u2013128"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(71)80036-3"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"H. R. Strong,  High level languages of maximum power,  Proc. IEEE Conf. on Switching and Automata Theory,  1971,  1\u20134","DOI":"10.1109\/SWAT.1971.15"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(72)90007-5"},{"key":"R9","volume-title":"Computation: finite and infinite machines","author":"Minsky Marvin L.","year":"1967"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0201006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:18:03Z","timestamp":1787339883000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0201006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1972,3]]},"references-count":9,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1972,3]]}},"alternative-id":["10.1137\/0201006"],"URL":"https:\/\/doi.org\/10.1137\/0201006","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1972,3]]}}}