Details
Originalsprache | Englisch |
---|---|
Titel des Sammelwerks | Logic, Language, Information, and Computation |
Untertitel | 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings |
Herausgeber/-innen | Alexandra Silva, Renata Wassermann, Ruy de Queiroz |
Seiten | 16-30 |
Seitenumfang | 15 |
Band | abs/2005.04916 |
ISBN (elektronisch) | 978-3-030-88853-4 |
Publikationsstatus | Veröffentlicht - 2021 |
Publikationsreihe
Name | Lecture Notes in Computer Science (LNCS) |
---|---|
Herausgeber (Verlag) | Springer |
Band | 13038 |
ISSN (Print) | 0302-9743 |
ISSN (elektronisch) | 1611-3349 |
Abstract
ASJC Scopus Sachgebiete
- Mathematik (insg.)
- Theoretische Informatik
- Informatik (insg.)
Zitieren
- Standard
- Harvard
- Apa
- Vancouver
- BibTex
- RIS
Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. Hrsg. / Alexandra Silva; Renata Wassermann; Ruy de Queiroz. Band abs/2005.04916 2021. S. 16-30 (Lecture Notes in Computer Science (LNCS); Band 13038).
Publikation: Beitrag in Buch/Bericht/Sammelwerk/Konferenzband › Aufsatz in Konferenzband › Forschung › Peer-Review
}
TY - GEN
T1 - A Logical Characterization of Constant-Depth Circuits over the Reals
AU - Barlag, Timon
AU - Vollmer, Heribert
N1 - Funding Information: Supported by DFG VO 630/8-1.
PY - 2021
Y1 - 2021
N2 - In this paper we give an Immerman's Theorem for real-valued computation. We define circuits operating over real numbers and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on R-structures in the sense of Cucker and Meer. Our characterization holds both non-uniformily as well as for many natural uniformity conditions.
AB - In this paper we give an Immerman's Theorem for real-valued computation. We define circuits operating over real numbers and show that families of such circuits of polynomial size and constant depth decide exactly those sets of vectors of reals that can be defined in first-order logic on R-structures in the sense of Cucker and Meer. Our characterization holds both non-uniformily as well as for many natural uniformity conditions.
KW - cs.CC
KW - F.1.1; F.1.3; F.4.1
KW - Constant-depth circuit families
KW - Computation over the reals
KW - Descriptive complexity
UR - http://www.scopus.com/inward/record.url?scp=85117486121&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-88853-4_2
DO - 10.1007/978-3-030-88853-4_2
M3 - Conference contribution
SN - 978-3-030-88852-7
VL - abs/2005.04916
T3 - Lecture Notes in Computer Science (LNCS)
SP - 16
EP - 30
BT - Logic, Language, Information, and Computation
A2 - Silva, Alexandra
A2 - Wassermann, Renata
A2 - de Queiroz, Ruy
ER -