{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,29]],"date-time":"2023-10-29T06:10:44Z","timestamp":1698559844208},"reference-count":37,"publisher":"Wiley","issue":"2","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3603,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1997,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We compare two different Grzegorczyk hierarchies {<jats:italic>H<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup>\u03c3<\/jats:sup>}<jats:italic>n<\/jats:italic>\u22650 and {<jats:italic>L<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup>\u03c3<\/jats:sup>}<jats:italic>n<\/jats:italic>\u22651 on term algebras, which grow according to the height and length of terms, respectively. The solution of almost all inclusion problems among the Grzegorczyk classes and the (simultaneous) recursion number classes <jats:italic>R<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup>\u03c3<\/jats:sup> and <jats:italic>S<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup>\u03c3<\/jats:sup> on term algebras shows {<jats:italic>H<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup>\u03c3<\/jats:sup>}<jats:italic>n<\/jats:italic>\u22650 to generalize Weihrauch's Grzegorczyk hierarchy on words {<jats:italic>E<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup><jats:italic>k<\/jats:italic><\/jats:sup>}<jats:italic>n<\/jats:italic>\u22650 to arbitrary term algebras. However, by regarding terms as words, {<jats:italic>L<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup>\u03c3<\/jats:sup>}<jats:italic>n<\/jats:italic>\u22651 turns out to be computationally equivalent to Weihrauch's hierarchy {<jats:italic>E<\/jats:italic><jats:sub><jats:italic>n<\/jats:italic><\/jats:sub><jats:sup>\u03c3<\/jats:sup>}<jats:italic>n<\/jats:italic>\u22650 on the whole. Especially, <jats:italic>L<\/jats:italic><jats:sub>2<\/jats:sub><jats:sup>\u03c3<\/jats:sup>} is equivalent to polynomial time computability and contains several natural term algebra functions. This establishes a notion of feasible term algebra functions and predicates.<\/jats:p>","DOI":"10.1002\/malq.19970430208","type":"journal-article","created":{"date-parts":[[2007,5,30]],"date-time":"2007-05-30T07:24:09Z","timestamp":1180509849000},"page":"251-286","source":"Crossref","is-referenced-by-count":0,"title":["Some Hierarchies of Primitive Recursive Functions on Term Algebras"],"prefix":"10.1002","volume":"43","author":[{"given":"Klaus\u2010Hilmar","family":"Sprenger","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01459088"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/978-3-642-95289-0_12","volume-title":"6. GI\u2010Jahrestagung","author":"Ausiello G.","year":"1976"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19650110310"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0201019"},{"key":"e_1_2_1_6_2","volume-title":"Computability, Complexity, Logic","author":"B\u00f6rger E.","year":"1989"},{"key":"e_1_2_1_7_2","volume-title":"Theories of Computational Complexity","author":"Calude C.","year":"1988"},{"key":"e_1_2_1_8_2","first-page":"24","volume-title":"Int. Congr. of Logic, Method, and Phil, of Sci. 1964","author":"Cobham A.","year":"1965"},{"key":"e_1_2_1_9_2","unstructured":"Cohors\u2010Fresenborg E. Subrekursive Funktionenklassen \u00fcber bin\u00e4ren B\u00e4umen. Dissertation Univ. M\u00fcnster1971."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0039158"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19810271802"},{"key":"e_1_2_1_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19820282206"},{"key":"e_1_2_1_13_2","unstructured":"D\u00f6pke W. Klassen primitiv\u2010rekursiver Funktionen \u00fcber Termmengen. Diplomarbeit Univ. M\u00fcnster1977."},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1051\/ita\/1979130100491","article-title":"A hierarchy of primitive recursive sequence functions","volume":"13","author":"Fachini E.","year":"1979","journal-title":"R.A.I.R.O. Inform. Th\u00e9or."},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19820282705"},{"key":"e_1_2_1_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(84)90018-5"},{"key":"e_1_2_1_17_2","unstructured":"Fachini E. andM.Napoli A hierarchy of LOOP programs over binary trees. Internal Report University of Salerno."},{"key":"e_1_2_1_18_2","unstructured":"Grzegorczyk A. Some Classes of Recursive Functions. Rozprawy Matematyczne IV 1953."},{"key":"e_1_2_1_19_2","unstructured":"Heinermann W. Untersuchungen \u00fcber die Rekursionszahlen rekursiver Funktionen. Dissertation Univ. M\u00fcnster1961."},{"key":"e_1_2_1_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02242369"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10854-8_21"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01982048"},{"key":"e_1_2_1_23_2","unstructured":"Meyer A. R. andD. M.Ritchie Computational Complexity and Program Structure. IBM Research Report RC\u20101817 1967."},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19760220156"},{"key":"e_1_2_1_25_2","unstructured":"M\u00fcller H. Klassifizierungen der primitiv\u2010rekursiven Funktionen. Dissertation Univ. M\u00fcnster1974."},{"key":"e_1_2_1_26_2","volume-title":"Classical Recursion Theory","author":"Odifreddi P.","year":"1989"},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1090\/S0002-9947-1963-0158822-2","article-title":"Classes of predictably computable functions","volume":"106","author":"Ritchie R. W.","year":"1963","journal-title":"Trans. Amer. Math. Soc."},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.1027"},{"key":"e_1_2_1_29_2","unstructured":"Rose G. andK.Weihrauch Eine Charakterisierung der KlassenL1undR1primitiv\u2010rekursiver Wortfunktionen. GMD\u2010Bericht Nr. 63 1973."},{"key":"e_1_2_1_30_2","volume-title":"Subrecursion. Functions and Hierarchies","author":"Rose H. E.","year":"1984"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01982053"},{"key":"e_1_2_1_32_2","unstructured":"Sprenger K.\u2010H. Hierarchies of Primitive Recursive Functions on Term Algebras. Dissertation Univ. Siegen 1995; also published by Shaker\u2010Verlag Aachen 1996."},{"key":"e_1_2_1_33_2","volume-title":"Computability","author":"Tourlakis G. J.","year":"1984"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/321607.321621"},{"key":"e_1_2_1_35_2","unstructured":"Tsichrltzis D. andP.Weiner Some unsolvable problems and partial solutions. Dept. Electr. Engineering Comp. Sci. Lab. TR No. 69 Princeton Univ.1968."},{"key":"e_1_2_1_36_2","unstructured":"Warkentin J. C. Small Classes of Recursive Functions and Relations. Dept. Appl. Analysis and Comp. Sci. Dissertation Univ. Waterloo Waterloo Ontario1971."},{"key":"e_1_2_1_37_2","volume-title":"Computational Complexity","author":"Wagner K.","year":"1986"},{"key":"e_1_2_1_38_2","unstructured":"Weihrauch K. Teilklassen primitiv\u2010rekursiver Wortfunktionen. GMD\u2010Bericht Nr. 91 Dissertation Univ. Bonn1974."}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19970430208","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19970430208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T09:11:28Z","timestamp":1698484288000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19970430208"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,1]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,1]]}},"alternative-id":["10.1002\/malq.19970430208"],"URL":"https:\/\/doi.org\/10.1002\/malq.19970430208","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1997,1]]}}}