5 papers · 1 filter
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…
Two-Variable Logic for Hierarchically Partitioned and Ordered Data
Oskar Fiuk, Emanuel Kieronski, Vincent Michielini
We study Two-Variable First-Order Logic, FO2, under semantic constraints that model hierarchically structured data. Our first logic extends FO2 with a linear order < and a chain of…
Guarded Fragments Meet Dynamic Logic: The Story of Regular Guards (Extended Version)
Bartosz Bednarczyk, Emanuel Kieroński
We study the Guarded Fragment with Regular Guards (RGF), which combines the expressive power of the Guarded Fragment (GF) with Propositional Dynamic Logic with Intersection and Con…
On the complexity of Maslov's class
Oskar Fiuk, Emanuel Kieronski, Vincent Michielini
Maslov's class is an expressive fragment of First-Order Logic known to have decidable satisfiability problem, whose exact complexity, however, has not been es…
Finite Model Theory of the Triguarded Fragment and Related Logics
Emanuel Kieroński, Sebastian Rudolph
The Triguarded Fragment (TGF) is among the most expressive decidable fragments of first-order logic, subsuming both its two-variable and guarded fragments without equality. We show…