Logic and Computation Through the Lens of Semirings

Timon Barlag; Nicolas Fröhlich; Teemu Hankala; Miika Hannula; Minna Hirvonen; Vivian Holzapfel; Juha Kontinen; Arne Meier; Laura Strieker

doi:10.48550/arXiv.2502.12939

Logic and Computation Through the Lens of Semirings

Timon Barlag
, Nicolas Fröhlich
, Teemu Hankala
, Miika Hannula
, Minna Hirvonen
, Vivian Holzapfel
, Juha Kontinen
, Arne Meier
, Laura Strieker

Institute of Theoretical Computer Science

Research output: Working paper/Preprint › Technical report › Research

Abstract

We study computational aspects of first-order logic and its extensions in the semiring semantics developed by Gr\"adel and Tannen. We characterize the complexity of model checking and data complexity of first-order logic both in terms of a generalization of BSS-machines and arithmetic circuits defined over $K$. In particular, we give a logical characterization of $\mathrm{FAC}^0_{K}$ by an extension of first-order logic that holds for any $K$ that is both commutative and positive.

Original language	English
DOIs	https://doi.org/10.48550/arXiv.2502.12939
Publication status	E-pub ahead of print - 18 Feb 2025

Keywords

cs.LO
cs.CC

Access to Document

10.48550/arXiv.2502.12939Licence: Arxiv nonexclusive-distrib 1.0

Applications and complexity of logics in semiring team semantics
Meier, A. (Principal Investigator), Vollmer, H. (Project staff), Barlag, T. (Project staff), Fröhlich, N. F. H. (Project staff), Holzapfel, V. (Project staff) & Strieker, L. (Project staff)
1 Jan 2024 → 31 Dec 2025
Project: Research

Cite this

@techreport{5a5c75c623bc40f8810057828d988553,

title = "Logic and Computation Through the Lens of Semirings",

abstract = " We study computational aspects of first-order logic and its extensions in the semiring semantics developed by Gr\textbackslash{}{"}adel and Tannen. We characterize the complexity of model checking and data complexity of first-order logic both in terms of a generalization of BSS-machines and arithmetic circuits defined over \$K\$. In particular, we give a logical characterization of \$\textbackslash{}mathrm\{FAC\}\textasciicircum{}0\_\{K\}\$ by an extension of first-order logic that holds for any \$K\$ that is both commutative and positive. ",

keywords = "cs.LO, cs.CC",

author = "Timon Barlag and Nicolas Fr{\"o}hlich and Teemu Hankala and Miika Hannula and Minna Hirvonen and Vivian Holzapfel and Juha Kontinen and Arne Meier and Laura Strieker",

year = "2025",

month = feb,

day = "18",

doi = "10.48550/arXiv.2502.12939",

language = "English",

type = "WorkingPaper",

}

TY - UNPB

T1 - Logic and Computation Through the Lens of Semirings

AU - Barlag, Timon

AU - Fröhlich, Nicolas

AU - Hankala, Teemu

AU - Hannula, Miika

AU - Hirvonen, Minna

AU - Holzapfel, Vivian

AU - Kontinen, Juha

AU - Meier, Arne

AU - Strieker, Laura

PY - 2025/2/18

Y1 - 2025/2/18

N2 - We study computational aspects of first-order logic and its extensions in the semiring semantics developed by Gr\"adel and Tannen. We characterize the complexity of model checking and data complexity of first-order logic both in terms of a generalization of BSS-machines and arithmetic circuits defined over $K$. In particular, we give a logical characterization of $\mathrm{FAC}^0_{K}$ by an extension of first-order logic that holds for any $K$ that is both commutative and positive.

AB - We study computational aspects of first-order logic and its extensions in the semiring semantics developed by Gr\"adel and Tannen. We characterize the complexity of model checking and data complexity of first-order logic both in terms of a generalization of BSS-machines and arithmetic circuits defined over $K$. In particular, we give a logical characterization of $\mathrm{FAC}^0_{K}$ by an extension of first-order logic that holds for any $K$ that is both commutative and positive.

KW - cs.LO

KW - cs.CC

U2 - 10.48550/arXiv.2502.12939

DO - 10.48550/arXiv.2502.12939

M3 - Technical report

BT - Logic and Computation Through the Lens of Semirings

ER -

Logic and Computation Through the Lens of Semirings

Abstract

Keywords

Access to Document

Projects

Applications and complexity of logics in semiring team semantics

Cite this