{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,31]],"date-time":"2025-08-31T10:06:11Z","timestamp":1756634771608,"version":"3.40.5"},"reference-count":16,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T00:00:00Z","timestamp":1715558400000},"content-version":"unspecified","delay-in-days":12,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["cambridge.org"],"crossmark-restriction":true},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present an adapted construction of algebraic circuits over the reals introduced by Cucker and Meer to arbitrary infinite integral domains and generalize the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000136_inline1.png\"\/><jats:tex-math>\n$\\mathrm{AC}_{\\mathbb{R}}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000136_inline2.png\"\/><jats:tex-math>\n$\\mathrm{NC}_{\\mathbb{R}}^{}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> classes for this setting. We give a theorem in the style of Immerman\u2019s theorem which shows that for these adapted formalisms, sets decided by circuits of constant depth and polynomial size are the same as sets definable by a suitable adaptation of first-order logic. Additionally, we discuss a generalization of the guarded predicative logic by Durand, Haak and Vollmer, and we show characterizations for the <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000136_inline3.png\"\/><jats:tex-math>\n$\\mathrm{AC}_{R}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000136_inline4.png\"\/><jats:tex-math>\n$\\mathrm{NC}_R^{}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> hierarchy. Those generalizations apply to the Boolean <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000136_inline5.png\"\/><jats:tex-math>\n$\\mathrm{AC}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" xlink:href=\"S0960129524000136_inline6.png\"\/><jats:tex-math>\n$\\mathrm{NC}$\n<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula> hierarchies as well. Furthermore, we introduce a formalism to be able to compare some of the aforementioned complexity classes with different underlying integral domains.<\/jats:p>","DOI":"10.1017\/s0960129524000136","type":"journal-article","created":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T08:54:28Z","timestamp":1715590468000},"page":"346-374","update-policy":"https:\/\/doi.org\/10.1017\/policypage","source":"Crossref","is-referenced-by-count":1,"title":["Logical characterizations of algebraic circuit classes over integral domains"],"prefix":"10.1017","volume":"34","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6139-5219","authenticated-orcid":false,"given":"Timon","family":"Barlag","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Florian","family":"Chudigiewitsch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sabrina A.","family":"Gaube","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2024,5,13]]},"reference":[{"key":"S0960129524000136_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03927-4"},{"key":"S0960129524000136_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-03338-8"},{"key":"S0960129524000136_ref9","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2675"},{"key":"S0960129524000136_ref3","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0701-6"},{"key":"S0960129524000136_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0041-0"},{"volume-title":"Algebra: Chapter 0. Graduate Studies in Mathematics","year":"2009","author":"Aluffi","key":"S0960129524000136_ref1"},{"author":"Barlag","key":"S0960129524000136_ref2"},{"key":"S0960129524000136_ref4","volume-title":"Bd.","volume":"7","author":"B\u00fcrgisser","year":"2013"},{"key":"S0960129524000136_ref12","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0539-5"},{"key":"S0960129524000136_ref15","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804419"},{"key":"S0960129524000136_ref7","doi-asserted-by":"publisher","DOI":"10.2307\/2586770"},{"key":"S0960129524000136_ref6","doi-asserted-by":"publisher","DOI":"10.1016\/0885-064X(92)90024-6"},{"key":"S0960129524000136_ref8","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209179"},{"year":"2004","author":"Libkin","key":"S0960129524000136_ref14"},{"key":"S0960129524000136_ref11","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225151"},{"year":"2007","author":"Gr\u00e4del","key":"S0960129524000136_ref10"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129524000136","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T13:16:13Z","timestamp":1727874973000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129524000136\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":16,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["S0960129524000136"],"URL":"https:\/\/doi.org\/10.1017\/s0960129524000136","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"type":"print","value":"0960-1295"},{"type":"electronic","value":"1469-8072"}],"subject":[],"published":{"date-parts":[[2024,5]]},"assertion":[{"value":"\u00a9 The Author(s), 2024. Published by Cambridge University Press","name":"copyright","label":"Copyright","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This is an Open Access article, distributed under the terms of the Creative Commons Attribution licence (http:\/\/creativecommons.org\/licenses\/by\/4.0\/), which permits unrestricted re-use, distribution and reproduction, provided the original article is properly cited.","name":"license","label":"License","group":{"name":"copyright_and_licensing","label":"Copyright and Licensing"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}