3 papers
cs.CC2026
Fagin's Theorem for Semiring Turing Machines
Guillermo Badia, Manfred Droste, Thomas Eiter +3
In recent years, quantitative complexity over semirings has been intensively investigated. In this context, Eiter and Kiesel (Semiring Reasoning Frameworks in AI and Their Computat…
cs.LO2025
Codd's Theorem for Databases over Semirings
Guillermo Badia, Phokion G. Kolaitis, Carles Noguera
Codd's Theorem, a fundamental result of database theory, asserts that relational algebra and relational calculus have the same expressive power on relational databases. We explore…
math.LO2024
Logical Characterizations of Weighted Complexity Classes
Guillermo Badia, Manfred Droste, Carles Noguera +1
Fagin's seminal result characterizing in terms of existential second-order logic started the fruitful field of descriptive complexity theory. In recent years, there h…