## Details

Original language | English |
---|---|

Number of pages | 29 |

Journal | Mathematical Structures in Computer Science |

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

**Logical characterizations of algebraic circuit classes over integral domains.**/ Barlag, Timon; Chudigiewitsch, Florian; Gaube, Sabrina A.

In: Mathematical Structures in Computer Science, 13.05.2024.

Research output: Contribution to journal › Article › Research › peer review

*Mathematical Structures in Computer Science*. https://doi.org/10.1017/S0960129524000136

*Mathematical Structures in Computer Science*. Advance online publication. https://doi.org/10.1017/S0960129524000136

}

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

JO - Mathematical Structures in Computer Science

JF - Mathematical Structures in Computer Science

SN - 0960-1295

ER -