Logic and Computation through the Lens of Semirings

2025/02/18 by Timon Barlag, Barlag, Timon, Nicolas Fröhlich +15 · 2 citations
Computer Science · #Advanced Algebra and Logic #Computational Complexity (cs.CC) #Constraint Satisfaction and Optimization #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge

paper · pdf · doi:10.48550/arxiv.2502.12939

openalex publication_date 2025/02/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We study the expressivity and computational aspects of first-order logic and its extensions in the semiring semantics developed by Grädel and Tannen. We characterize the complexity of model checking and data complexity of first-order logic both in terms of a generalization of Blum-Shub-Smale machines and arithmetic circuits defined over a semiring. In particular, we give a logical characterization of constant-depth arithmetic circuits by an extension of first-order logic that holds for any semiring that is both commutative and positive.

Cited by

• Logical Approaches to Non-deterministic Polynomial Time over Semirings
• Fagin's Theorem for Semiring Turing Machines

Related

• Logical Approaches to Non-deterministic Polynomial Time over Semirings
• Fagin's Theorem for Semiring Turing Machines
• Zero-One Laws and Almost Sure Valuations of First-Order Logic in Semiring Semantics
• Semiring Provenance for First-Order Model Checking
• Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth