Logic and Computation through the Lens of Semirings

Timon Barlag, Nicolas Fröhlich, Teemu Hankala +6

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…