Loading [MathJax]/extensions/tex2jax.js

Logic and Computation Through the Lens of Semirings

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

Authors

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

Research Organisations

External Research Organisations

  • University of Helsinki
  • University of Tartu

Details

Original languageEnglish
Publication statusE-pub ahead of print - 18 Feb 2025

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.

Keywords

    cs.LO, cs.CC

Cite this

Logic and Computation Through the Lens of Semirings. / Barlag, Timon; Fröhlich, Nicolas; Hankala, Teemu et al.
2025.

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

Barlag, T, Fröhlich, N, Hankala, T, Hannula, M, Hirvonen, M, Holzapfel, V, Kontinen, J, Meier, A & Strieker, L 2025 'Logic and Computation Through the Lens of Semirings'. https://doi.org/10.48550/arXiv.2502.12939
Barlag, T., Fröhlich, N., Hankala, T., Hannula, M., Hirvonen, M., Holzapfel, V., Kontinen, J., Meier, A., & Strieker, L. (2025). Logic and Computation Through the Lens of Semirings. Advance online publication. https://doi.org/10.48550/arXiv.2502.12939
Barlag T, Fröhlich N, Hankala T, Hannula M, Hirvonen M, Holzapfel V et al. Logic and Computation Through the Lens of Semirings. 2025 Feb 18. Epub 2025 Feb 18. doi: 10.48550/arXiv.2502.12939
Barlag, Timon ; Fröhlich, Nicolas ; Hankala, Teemu et al. / Logic and Computation Through the Lens of Semirings. 2025.
Download
@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\{"}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. ",
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",

}

Download

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 -

By the same author(s)