Details
| Originalsprache | Englisch |
|---|---|
| Seiten (von - bis) | 346-374 |
| Seitenumfang | 29 |
| Fachzeitschrift | Mathematical Structures in Computer Science |
| Jahrgang | 34 |
| Ausgabenummer | 5 |
| Frühes Online-Datum | 13 Mai 2024 |
| Publikationsstatus | Elektronisch veröffentlicht (E-Pub) - 13 Mai 2024 |
Abstract
We present an adapted construction of algebraic circuits over the reals introduced by Cucker and Meer to arbitrary infinite integral domains and generalize the ACℝ and NCℝ classes for this setting. We give a theorem in the style of Immerman's 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 ACℝ and NCℝ hierarchy. Those generalizations apply to the Boolean AC and NC hierarchies as well. Furthermore, we introduce a formalism to be able to compare some of the aforementioned complexity classes with different underlying integral domains.
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Mathematik (sonstige)
- Informatik (insg.)
- Angewandte Informatik
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
in: Mathematical Structures in Computer Science, Jahrgang 34, Nr. 5, 13.05.2024, S. 346-374.
Publikation: Beitrag in Fachzeitschrift › Artikel › Forschung › Peer-Review
}
TY - JOUR
T1 - Logical characterizations of algebraic circuit classes over integral domains
AU - Barlag, Timon
AU - Chudigiewitsch, Florian
AU - Gaube, Sabrina A.
N1 - Publisher Copyright: Copyright © 2024 The Author(s).
PY - 2024/5/13
Y1 - 2024/5/13
N2 - We present an adapted construction of algebraic circuits over the reals introduced by Cucker and Meer to arbitrary infinite integral domains and generalize the ACℝ and NCℝ classes for this setting. We give a theorem in the style of Immerman's 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 ACℝ and NCℝ hierarchy. Those generalizations apply to the Boolean AC and NC hierarchies as well. Furthermore, we introduce a formalism to be able to compare some of the aforementioned complexity classes with different underlying integral domains.
AB - We present an adapted construction of algebraic circuits over the reals introduced by Cucker and Meer to arbitrary infinite integral domains and generalize the ACℝ and NCℝ classes for this setting. We give a theorem in the style of Immerman's 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 ACℝ and NCℝ hierarchy. Those generalizations apply to the Boolean AC and NC hierarchies as well. Furthermore, we introduce a formalism to be able to compare some of the aforementioned complexity classes with different underlying integral domains.
KW - algebraic circuits
KW - descriptive complexity
UR - http://www.scopus.com/inward/record.url?scp=85193063766&partnerID=8YFLogxK
U2 - 10.1017/S0960129524000136
DO - 10.1017/S0960129524000136
M3 - Article
AN - SCOPUS:85193063766
VL - 34
SP - 346
EP - 374
JO - Mathematical Structures in Computer Science
JF - Mathematical Structures in Computer Science
SN - 0960-1295
IS - 5
ER -