6 papers
Maslov's class K with Equivalence
Oskar Fiuk
Maslov's class K is a decidable fragment of equality-free first-order logic. It subsumes numerous classical decidable fragments, including the equality-free monadic fragment, the e…
The Guarded Fragment with Nested Equivalences
Oskar Fiuk
The Guarded Fragment (GF) is a well-established decidable fragment of first-order logic. We study an extension of GF with nested equivalence relations, namely a family of distingui…
Random Models and the Guarded Fragment
Oskar Fiuk
Building on ideas of Gurevich and Shelah for the Gödel Class, we present a new probabilistic proof of the finite model property for the Guarded Fragment of First-Order Logic. Our p…
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…
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…
Alternating Quantifiers in Uniform One-Dimensional Fragments with an Excursion into Three-Variable Logic
Oskar Fiuk, Emanuel Kieronski
The uniform one-dimensional fragment of first-order logic was introduced a few years ago as a generalization of the two-variable fragment to contexts involving relations of arity g…