{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:40:24Z","timestamp":1787496024561,"version":"build-2736575974"},"reference-count":28,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":6767,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1995,9]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    We design functional algebras that characterize various complexity classes of global functions. For this purpose, classical schemata from recursion theory are tailored for capturing complexity. In particular we present a functional analog of first-order logic and describe algebras of the functions computable in nondeterministic logarithmic space, deterministic and nondeterministic polynomial time, and for the functions computable by AC\n                    <jats:sup>1<\/jats:sup>\n                    -circuits.\n                  <\/jats:p>","DOI":"10.2307\/2275767","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:56:10Z","timestamp":1146941770000},"page":"952-969","source":"Crossref","is-referenced-by-count":9,"title":["Tailoring recursion for complexity"],"prefix":"10.1017","volume":"60","author":[{"given":"Erich","family":"Gr\u00e4del","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuri","family":"Gurevich","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200018375_ref028","first-page":"137","article-title":"Complexity of relational query languages","volume":"14","author":"Vardi","year":"1982","journal-title":"Proceedings of the 14th Symposium on Theory of Computing"},{"key":"S0022481200018375_ref027","first-page":"326","article-title":"Finite automata and the logic of monadic predicates","volume":"140","author":"Trakhtenbrot","year":"1961","journal-title":"Doklady Akademii Nauk SSR"},{"key":"S0022481200018375_ref026","doi-asserted-by":"publisher","DOI":"10.1007\/BF00299636"},{"key":"S0022481200018375_ref025","first-page":"319","article-title":"Polynomial computability and recursivity in finite domains","volume":"16","author":"Sanonov","year":"1980","journal-title":"Elektronische Datenverarbeitung und Kybernetik"},{"key":"S0022481200018375_ref023","first-page":"27","article-title":"The relational model for process control","volume":"4","author":"Livchak","year":"1983","journal-title":"Automatic documentation and mathematical linguistics"},{"key":"S0022481200018375_ref020","doi-asserted-by":"publisher","DOI":"10.1137\/0217058"},{"key":"S0022481200018375_ref019","doi-asserted-by":"publisher","DOI":"10.1137\/0216051"},{"key":"S0022481200018375_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(86)80029-8"},{"key":"S0022481200018375_ref017","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90011-3"},{"key":"S0022481200018375_ref014","first-page":"1","volume-title":"Trends in Theoretical Computer Science","author":"Gurevich","year":"1988"},{"key":"S0022481200018375_ref013","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0099486"},{"key":"S0022481200018375_ref012","first-page":"210","article-title":"Algebras offeasible functions","volume":"24","author":"Gurevich","year":"1983","journal-title":"Proceedings of the 24th IEEE Symposium on Foundations of Computer Science"},{"key":"S0022481200018375_ref011","first-page":"231","volume-title":"Proceedings of the CSL '92","author":"Gr\u00e4del","year":"1993"},{"key":"S0022481200018375_ref010","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90149-A"},{"key":"S0022481200018375_ref009","first-page":"99","article-title":"Characterizing complexity classes by general recursie definitions in higher types","author":"Goerdt","year":"1989","journal-title":"Proceedings of the 2nd workshop on Computer Science Logic CSL '88"},{"key":"S0022481200018375_ref008","first-page":"43","article-title":"Generalized first-order spectra and polynomial-time recognizable sets","volume":"7","author":"Fagin","year":"1974","journal-title":"Proceedings of the SIAM-AMS"},{"key":"S0022481200018375_ref005","volume-title":"Bounded arithmetic","author":"Buss","year":"1986"},{"key":"S0022481200018375_ref003","first-page":"283","volume-title":"Proceedings of the 24th ACM Symposium on the Theory of Computing","author":"Bellantoni","year":"1992"},{"key":"S0022481200018375_ref002","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97062-7"},{"key":"S0022481200018375_ref016","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(86)90055-2"},{"key":"S0022481200018375_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90032-Z"},{"key":"S0022481200018375_ref007","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90063-N"},{"key":"S0022481200018375_ref004","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S0022481200018375_ref022","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90039-6"},{"key":"S0022481200018375_ref015","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80062-5"},{"key":"S0022481200018375_ref006","volume-title":"Logic, methodology and philosophy of science","volume":"II","author":"Cobham","year":"1965"},{"key":"S0022481200018375_ref024","first-page":"118","volume":"57","author":"Lo","year":"1992","journal-title":"Functions and functionals on finite systems"},{"key":"S0022481200018375_ref021","doi-asserted-by":"publisher","DOI":"10.1090\/psapm\/038\/1020810"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200018375","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T17:13:18Z","timestamp":1557767598000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200018375\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,9]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,9]]}},"alternative-id":["S0022481200018375"],"URL":"https:\/\/doi.org\/10.2307\/2275767","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,9]]}}}