A Logical Characterization of Constant-Depth Circuits over the Reals

Publikation: Beitrag in Buch/Bericht/Sammelwerk/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Forschungs-netzwerk anzeigen

Details

OriginalspracheEnglisch
Titel des SammelwerksLogic, Language, Information, and Computation
Untertitel27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings
Herausgeber/-innenAlexandra Silva, Renata Wassermann, Ruy de Queiroz
Seiten16-30
Seitenumfang15
Bandabs/2005.04916
ISBN (elektronisch)978-3-030-88853-4
PublikationsstatusVeröffentlicht - 2021

Publikationsreihe

NameLecture Notes in Computer Science (LNCS)
Herausgeber (Verlag)Springer
Band13038
ISSN (Print)0302-9743
ISSN (elektronisch)1611-3349

Abstract

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.

ASJC Scopus Sachgebiete

Zitieren

A Logical Characterization of Constant-Depth Circuits over the Reals. / Barlag, Timon; Vollmer, Heribert.
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/KonferenzbandAufsatz in KonferenzbandForschungPeer-Review

Barlag, T & Vollmer, H 2021, A Logical Characterization of Constant-Depth Circuits over the Reals. in A Silva, R Wassermann & R de Queiroz (Hrsg.), Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. Bd. abs/2005.04916, Lecture Notes in Computer Science (LNCS), Bd. 13038, S. 16-30. https://doi.org/10.1007/978-3-030-88853-4_2
Barlag, T., & Vollmer, H. (2021). A Logical Characterization of Constant-Depth Circuits over the Reals. In A. Silva, R. Wassermann, & R. de Queiroz (Hrsg.), Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings (Band abs/2005.04916, S. 16-30). (Lecture Notes in Computer Science (LNCS); Band 13038). https://doi.org/10.1007/978-3-030-88853-4_2
Barlag T, Vollmer H. A Logical Characterization of Constant-Depth Circuits over the Reals. in Silva A, Wassermann R, de Queiroz R, Hrsg., Logic, Language, Information, and Computation: 27th International Workshop, WoLLIC 2021, Virtual Event, October 5–8, 2021, Proceedings. Band abs/2005.04916. 2021. S. 16-30. (Lecture Notes in Computer Science (LNCS)). Epub 2021 Okt 6. doi: 10.1007/978-3-030-88853-4_2
Barlag, Timon ; Vollmer, Heribert. / A Logical Characterization of Constant-Depth Circuits over the Reals. 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)).
Download
@inproceedings{9e0e118b14ff47f9ae3d2c9ba47ac0d0,
title = "A Logical Characterization of Constant-Depth Circuits over the Reals",
abstract = "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. ",
keywords = "cs.CC, F.1.1; F.1.3; F.4.1, Constant-depth circuit families, Computation over the reals, Descriptive complexity",
author = "Timon Barlag and Heribert Vollmer",
note = "Funding Information: Supported by DFG VO 630/8-1.",
year = "2021",
doi = "10.1007/978-3-030-88853-4_2",
language = "English",
isbn = "978-3-030-88852-7 ",
volume = "abs/2005.04916",
series = "Lecture Notes in Computer Science (LNCS)",
publisher = "Springer",
pages = "16--30",
editor = "Alexandra Silva and Renata Wassermann and {de Queiroz}, Ruy",
booktitle = "Logic, Language, Information, and Computation",

}

Download

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 -

Von denselben Autoren