Details
| Original language | English |
|---|---|
| Pages (from-to) | 346-374 |
| Number of pages | 29 |
| Journal | Mathematical Structures in Computer Science |
| Volume | 34 |
| Issue number | 5 |
| Early online date | 13 May 2024 |
| Publication status | E-pub ahead of print - 13 May 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.
Keywords
- algebraic circuits, descriptive complexity
ASJC Scopus subject areas
- Mathematics(all)
- Mathematics (miscellaneous)
- Computer Science(all)
- Computer Science Applications
Cite this
- Standard
- Harvard
- Apa
- Vancouver
- BibTeX
- RIS
In: Mathematical Structures in Computer Science, Vol. 34, No. 5, 13.05.2024, p. 346-374.
Research output: Contribution to journal › Article › Research › 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 -