3 papers
cs.LO2026
The Triguarded Fragment
Emanuel KieroÅski, Sebastian Rudolph, Mantas Å imkus
A prominent research question in computational logic is how to restrict first-order predicate logic (FO) in such a way that the satisfiability problem becomes decidable. Among othe…
cs.LO2025
Datalog-Expressibility for Monadic and Guarded Second-Order Logic
Manuel Bodirsky, Simon Knäuer, Sebastian Rudolph
We characterise the sentences in Monadic Second-order Logic (MSO) that are over finite structures equivalent to a Datalog program, in terms of an existential pebble game. We also s…
cs.LO2025
Decidability of Querying First-Order Theories via Countermodels of Finite Width
Thomas Feller, Tim S. Lyon, Piotr Ostropolski-Nalewaja +1
We propose a generic framework for establishing the decidability of a wide range of logical entailment problems (briefly called querying), based on the existence of countermodels t…