Cover Image

Logical Approaches to Non-deterministic Polynomial Time over Semirings

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Barlag, Timon, Fröhlich, Nicolas, Hankala, Teemu, Hannula, Miika, Hirvonen, Minna, Holzapfel, Vivian, Kontinen, Juha, Meier, Arne, Strieker, Laura
Format:	Preprint
Published:	2025
Subjects:	Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Logic and Computation through the Lens of Semirings
by: Barlag, Timon, et al.
Published: (2025)

Aspects of Coherence in Dependence Logic
by: Barlag, Timon, et al.
Published: (2026)

Logics with probabilistic team semantics and the Boolean negation
by: Hannula, Miika, et al.
Published: (2023)

Implication Problems over Positive Semirings
by: Hirvonen, Minna
Published: (2025)

Independence Under Incomplete Information
by: Hannula, Miika, et al.
Published: (2025)

Locally Consistent K-relations: Entailment and Axioms of Functional Dependence
by: Barlag, Timon, et al.
Published: (2025)

Parameterised Complexity of Consistent Query Answering via Graph Representations
by: Hankala, Teemu, et al.
Published: (2024)

On the Complexity and Properties of Preferential Propositional Dependence Logic
by: Sauerwald, Kai, et al.
Published: (2025)

Representation Theorems for Cumulative Propositional Dependence Logics
by: Kontinen, Juha, et al.
Published: (2026)

On the Complexity of Entailment for Cumulative Propositional Dependence Logics
by: Sauerwald, Kai, et al.
Published: (2026)

On the expressive power of inquisitive team logic and inquisitive first-order logic
by: Kontinen, Juha, et al.
Published: (2026)

The Implication Problem for Functional Dependencies and Variants of Marginal Distribution Equivalences
by: Hirvonen, Minna
Published: (2023)

A Primer for Preferential Non-Monotonic Propositional Team Logics
by: Sauerwald, Kai, et al.
Published: (2024)

Inquisitive first-order logic is neither compact nor recursively axiomatizable
by: Ciardelli, Ivano, et al.
Published: (2026)

Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2024)

Recurrent Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2026)

Dichotomy for Axiomatising Inclusion Dependencies on K-Databases
by: Hannula, Miika, et al.
Published: (2026)

Disjunctions of Two Dependence Atoms
by: Fröhlich, Nicolas, et al.
Published: (2025)

A Remark on the Expressivity of Asynchronous TeamLTL and HyperLTL
by: Kontinen, Juha, et al.
Published: (2024)

Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

Complexity Results in Team Semantics: Nonemptiness Is Not So Complex
by: Anttila, Aleksi, et al.
Published: (2025)

Expressibility and inexpressibility in propositional team logics
by: Häggblom, Matilda, et al.
Published: (2025)

The flattening operator in team-based logics
by: Durand, Arnaud, et al.
Published: (2025)

Semiring Provenance for Büchi Games: Strategy Analysis with Absorptive Polynomials
by: Grädel, Erich, et al.
Published: (2021)

Codd's Theorem for Databases over Semirings
by: Badia, Guillermo, et al.
Published: (2025)

A logic-based framework for database repairs
by: Fröhlich, Nicolas, et al.
Published: (2023)

Semiring Provenance for Lightweight Description Logics
by: Bourgaux, Camille, et al.
Published: (2023)

Provenance Analysis and Semiring Semantics for First-Order Logic
by: Grädel, Erich, et al.
Published: (2024)

Ehrenfeucht-Fraïssé Games for Continuous First-Order Logic
by: Hirvonen, Åsa, et al.
Published: (2024)

Synchronous Team Semantics for Temporal Logics
by: Krebs, Andreas, et al.
Published: (2024)

Preservation Theorems in Semiring Semantics
by: Brinke, Sophie, et al.
Published: (2026)

Locality Theorems in Semiring Semantics
by: Bizière, Clotilde, et al.
Published: (2023)

Polynomial Lawvere Logic
by: Bacci, Giorgio, et al.
Published: (2024)

Abstract computation over first-order structures. Part I: Deterministic and non-deterministic BSS RAMs
by: Gaßner, Christine
Published: (2025)

A Unifying Framework for Semiring-Based Constraint Logic Programming With Negation (full version)
by: Spaans, Jeroen, et al.
Published: (2025)

Modal Fragments
by: Bezhanishvili, Nick, et al.
Published: (2026)

Weighted Rewriting: Semiring Semantics for Abstract Reduction Systems
by: Ahrens, Emma, et al.
Published: (2025)

Fagin's Theorem for Semiring Turing Machines
by: Badia, Guillermo, et al.
Published: (2025)

A SUBSET-SUM Characterisation of the A-Hierarchy
by: Gutleben, Jan, et al.
Published: (2024)

When Symmetry Yields NP-Hardness: Affine ML-SAT on S5 Frames
by: Krebs, Andreas, et al.
Published: (2025)