Cover Image

Fagin's Theorem for Semiring Turing Machines

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Badia, Guillermo, Droste, Manfred, Eiter, Thomas, Kiesel, Rafael, Noguera, Carles, Paul, Erik
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Logic in Computer Science
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Logical Characterizations of Weighted Complexity Classes
by: Badia, Guillermo, et al.
Published: (2024)

Epistemic Logic Programs: Non-Ground and Counting Complexity
by: Eiter, Thomas, et al.
Published: (2025)

Stochastic Process Turing Machines
by: Wolpert, David, et al.
Published: (2024)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
by: Nechesov, Andrey
Published: (2024)

Simulation of Turing machines with analytic discrete ODEs: FPTIME and FPSPACE over the reals characterised with discrete ordinary differential equations
by: Blanc, Manon, et al.
Published: (2023)

Extending CDCL to disjunctions of parity equations
by: Beame, Paul, et al.
Published: (2026)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

Effective Versions of Strong Measure Zero
by: Rayman, Matthew
Published: (2025)

Meta-Mathematics of Computational Complexity Theory
by: Oliveira, Igor C.
Published: (2025)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
by: Gokaj, Geri, et al.
Published: (2025)

Proof Complexity of Linear Logics
by: Tabatabai, Amirhossein Akbar, et al.
Published: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
by: Mottet, Antoine, et al.
Published: (2023)

Proof complexity of positive branching programs
by: Das, Anupam, et al.
Published: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
by: Ježil, Ondřej, et al.
Published: (2026)

The complete classification for quantified equality constraints
by: Zhuk, Dmitriy, et al.
Published: (2021)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
by: Atserias, Albert, et al.
Published: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
by: Zhuk, Dmitriy
Published: (2024)

A note reviewing Turing's 1936
by: Cattabriga, Paola
Published: (2013)

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)

Cypher is Turing-Complete: A Formal Proof via 2-Counter Machine Simulation
by: Halftermeyer, Pierre
Published: (2026)

Specification and Automatic Verification of Computational Reductions
by: Grange, Julien, et al.
Published: (2024)

Dynamic Planar Graph Isomorphism is in DynFO
by: Datta, Samir, et al.
Published: (2026)

On Probabilistic and Causal Reasoning with Summation Operators
by: Ibeling, Duligur, et al.
Published: (2024)

Query maintenance under batch changes with small-depth circuits
by: Datta, Samir, et al.
Published: (2024)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
by: Seppelt, Tim
Published: (2024)

What If Turing Had Preceded Gödel?
by: Oberhoff, Sebastian
Published: (2024)

Fine-grained Meta-Theorems for Vertex Integrity
by: Lampis, Michael, et al.
Published: (2021)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
by: Lemke, Caroline, et al.
Published: (2025)

Better Extension Variables in DQBF via Independence
by: Chew, Leroy, et al.
Published: (2025)

Discrete Homotopy and Promise Constraint Satisfaction Problem
by: Beikmohammadi, Arash, et al.
Published: (2025)

Modular Counting CSP: Reductions and Algorithms
by: Kazeminia, Amirhossein, et al.
Published: (2025)

On the Interplay of Cube Learning and Dependency Schemes in QCDCL Proof Systems
by: Choudhury, Abhimanyu, et al.
Published: (2025)

Uniformity within Parameterized Circuit Classes
by: Hegeman, Steef, et al.
Published: (2025)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

On Middle Grounds for Preference Statements
by: George, Anne-Marie, et al.
Published: (2025)

Model Counting for Dependency Quantified Boolean Formulas
by: Fung, Long-Hin, et al.
Published: (2025)