{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,6]],"date-time":"2026-04-06T07:47:50Z","timestamp":1775461670075,"version":"3.50.1"},"reference-count":75,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2006,11,13]],"date-time":"2006-11-13T00:00:00Z","timestamp":1163376000000},"content-version":"vor","delay-in-days":3238,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[1998,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a model of computation for string functions over single\u2010sorted, total algebraic structures and study some basic features of a general theory of computability within this framework. Our concept generalizes the Blum\u2010Shub\u2010Smale setting of computability over the reals and other rings. By dealing with strings of arbitrary length instead of tuples of fixed length, some suppositions of deeper results within former approaches to generalized recursion theory become superfluous. Moreover, this gives the basis for introducing computational complexity in a BSS\u2010like manner. Relationships both to classical computability and to Friedman's concept of eds computability are established. Two kinds of nondeterminism as well as several variants of recognizability are investigated with respect to interdependencies on each other and on properties of the underlying structures. For structures of finite signatures, there are universal programs with the usual characteristics. For the general case of not necessarily finite signature, this subject will be studied in a separate, forthcoming paper.<\/jats:p>","DOI":"10.1002\/malq.19980440102","type":"journal-article","created":{"date-parts":[[2007,5,31]],"date-time":"2007-05-31T04:59:12Z","timestamp":1180587552000},"page":"1-44","source":"Crossref","is-referenced-by-count":11,"title":["Computability of String Functions Over Algebraic Structures Armin Hemmerling"],"prefix":"10.1002","volume":"44","author":[{"given":"Armin","family":"Hemmerling","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2006,11,13]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600061506"},{"key":"e_1_2_1_3_2","unstructured":"Balzer B. Erkennbarkeitsbegriffe \u00fcber allgemeinen Strukturen. Diploma Thesis E.\u2010M.\u2010A.\u2010Universit\u00e4t Greifswald 1996."},{"key":"e_1_2_1_4_2","volume-title":"Complexity and real computation: a manifesto","author":"Blum L."},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-1989-15750-9"},{"key":"e_1_2_1_6_2","volume-title":"The G\u00f6del incompleteness theorem and decidability over a ring","author":"Blum L."},{"key":"e_1_2_1_6_3","series-title":"Proc. of the Smalefest","first-page":"321","volume-title":"From Topology to Computation","year":"1993"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.2307\/2160343"},{"key":"e_1_2_1_8_2","unstructured":"Cucker F. andM.Matamala On digital nondeterminism. Preprint1993."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00069-7"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274424"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01705528"},{"key":"e_1_2_1_12_2","volume-title":"Berechnungstheorie f\u00fcr Informatiker","author":"Engeler E.","year":"1988"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-11157-3_38"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19730191901"},{"key":"e_1_2_1_14_3","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210164"},{"key":"e_1_2_1_14_4","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19770231902"},{"key":"e_1_2_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-11824-5"},{"key":"e_1_2_1_16_2","volume-title":"Fundamentals of Generalized Recursion Theory","author":"Fitting M. C.","year":"1981"},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"Friedman H. Algorithmic procedures generalized Turing algorithms and elementary recursion theory. In [19] pp.361\u2013390.","DOI":"10.1016\/S0049-237X(08)71238-2"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.2307\/2154033"},{"key":"e_1_2_1_19_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71257-6"},{"key":"e_1_2_1_20_2","volume-title":"Logic Colloquium '69","author":"Gandy R. O.","year":"1971"},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80040-6"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01700692"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.2307\/2275252"},{"key":"e_1_2_1_24_2","first-page":"704","article-title":"Finitistically computable functions and relations on an abstract structure (abstract)","volume":"36","author":"Gordon C. E.","year":"1971","journal-title":"J. Symb. Logic"},{"key":"e_1_2_1_25_2","first-page":"77","article-title":"On genuine complexity and kinds of nondeterminism","volume":"30","author":"Hemmerling A.","year":"1994","journal-title":"J. Inform. Process. Cybernet. EIK"},{"key":"e_1_2_1_26_2","unstructured":"Hemmerling A. Computability and complexity over structures of finite type. Preprint Nr. 2\u20131995 Preprint\u2010Reihe Mathematik Ernst\u2010Moritz\u2010Arndt\u2010Universit\u00e4t Greifswald 1995."},{"key":"e_1_2_1_27_2","volume-title":"Computability of string functions over algebraic structures","author":"Hemmerling A."},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-2.1.73"},{"key":"e_1_2_1_29_2","first-page":"82","article-title":"The logical schemes of algorithms","volume":"1","author":"Janov Ju. I.","year":"1960","journal-title":"Problems of Cybernetics"},{"key":"e_1_2_1_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90013-0"},{"key":"e_1_2_1_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80002-4"},{"key":"e_1_2_1_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5749-3"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288773"},{"key":"e_1_2_1_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-6802-1"},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"Kreisel G. Some reasons for generalising recursion theory. In [19] pp.139\u2013198.","DOI":"10.1016\/S0049-237X(08)71230-8"},{"key":"e_1_2_1_36_2","doi-asserted-by":"crossref","unstructured":"Lacombe D. Recursion theoretic structure for relational systems. In [19] 3\u201318.","DOI":"10.1016\/S0049-237X(08)71223-0"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80022-8"},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1070\/RM1961v016n03ABEH001120"},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-322-85356-1"},{"key":"e_1_2_1_40_2","volume-title":"Komplexit\u00e4tsbetrachtungen f\u00fcr reelle Maschinenmodelle","author":"Meer K.","year":"1993"},{"key":"e_1_2_1_41_2","first-page":"113","article-title":"A survey on real structural complexity theory","volume":"3","author":"Meer K.","year":"1996","journal-title":"Bull. Belg. Math. Soc."},{"key":"e_1_2_1_42_2","doi-asserted-by":"publisher","DOI":"10.1137\/0212022"},{"key":"e_1_2_1_43_2","series-title":"Proc. of the Smalefest","first-page":"432","volume-title":"From Topology to Computation","author":"Megiddo N.","year":"1993"},{"key":"e_1_2_1_44_2","doi-asserted-by":"publisher","DOI":"10.2307\/2048754"},{"key":"e_1_2_1_45_2","volume-title":"Computation: Finite and Infinite Machines","author":"Mlnsky M. L.","year":"1967"},{"key":"e_1_2_1_46_2","doi-asserted-by":"publisher","DOI":"10.2307\/2270854"},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.2307\/1994926"},{"key":"e_1_2_1_48_2","volume-title":"Les petits cailloux, une approche mod\u00e8le\u2010th\u00e9orique de l'algorithmie","author":"Poizat B.","year":"1995"},{"key":"e_1_2_1_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.2307\/1993295"},{"key":"e_1_2_1_51_2","volume-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers H.","year":"1967"},{"key":"e_1_2_1_52_2","volume-title":"Output sets, halting sets and an arithmetical hierarchy for ordered substrings of the real numbers under Blum\/Shub\/Smale computation","author":"Saint John R."},{"key":"e_1_2_1_53_2","unstructured":"Saint John R. Theory of computation for the real numbers and subrings of the real numbers following Blum\/Shub\/Smale. Dissertation. University of California at Berkeley 1995."},{"key":"e_1_2_1_54_2","volume-title":"Theorie der geometrischen Konstruktionen","author":"Schreiber P.","year":"1975"},{"key":"e_1_2_1_55_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71963-3"},{"key":"e_1_2_1_56_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(09)70163-6"},{"key":"e_1_2_1_57_2","first-page":"581","volume-title":"The Universal Turing Machine, A Half\u2010Century Survey","author":"Shepherdson J. C.","year":"1994"},{"key":"e_1_2_1_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22378-9"},{"key":"e_1_2_1_59_2","first-page":"341","volume-title":"Math. Logic and Appl.","author":"Soskov I. N.","year":"1987"},{"key":"e_1_2_1_60_2","doi-asserted-by":"publisher","DOI":"10.2307\/2274858"},{"key":"e_1_2_1_61_2","first-page":"89","article-title":"An external characterization of the prime computability","volume":"83","author":"Soskov I. N.","year":"1989","journal-title":"Ann. Univ. Sofia"},{"key":"e_1_2_1_62_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01621094"},{"issue":"1","key":"e_1_2_1_63_2","article-title":"An external approach to abstract data types I","volume":"87","author":"Soskova A. A.","year":"1994","journal-title":"Ann. Univ. Sofia"},{"key":"e_1_2_1_64_2","first-page":"361","volume-title":"Heyting '88","author":"Soskova A. A.","year":"1990"},{"key":"e_1_2_1_65_2","doi-asserted-by":"publisher","DOI":"10.1525\/9780520348097"},{"key":"e_1_2_1_66_2","series-title":"Lecture Notes in Computer Science 125","first-page":"198","volume-title":"Logic of Programs","author":"Tluryn J.","year":"1979"},{"key":"e_1_2_1_67_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629181.009"},{"key":"e_1_2_1_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0032065"},{"key":"e_1_2_1_69_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0035796"},{"key":"e_1_2_1_70_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(81)90163-7"},{"key":"e_1_2_1_71_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80057-6"},{"key":"e_1_2_1_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69965-8"},{"key":"e_1_2_1_73_2","unstructured":"Weihrauch K. A simple introduction to computable analysis. Informatik\u2010Berichte 171\u20102\/1995 Fern Univ. Hagen 1995."}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.19980440102","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.19980440102","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,28]],"date-time":"2023-10-28T12:55:00Z","timestamp":1698497700000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.19980440102"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,1]]},"references-count":75,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,1]]}},"alternative-id":["10.1002\/malq.19980440102"],"URL":"https:\/\/doi.org\/10.1002\/malq.19980440102","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"value":"0942-5616","type":"print"},{"value":"1521-3870","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,1]]}}}