4 papers
The Fluted Fragment with Transitivity
Ian Pratt-Hartmann, Lidia Tendera
We study the satisfiability problem for the fluted fragment extended with transitive relations. We show that the logic enjoys the finite model property when only one transitive rel…
Quine's Fluted Fragment Revisited
I. Pratt-Hartmann, W. Szwast, L. Tendera
We study the fluted fragment, a decidable fragment of first-order logic with an unbounded number of variables, originally identified in 1968 by W.V. Quine. We show that the satisfi…
On the satisfiability problem for fragments of the two-variable logic with one transitive relation
Wiesław Szwast, Lidia Tendera
We study the satisfiability problem for the two-variable first-order logic over structures with one transitive relation. % We show that the problem is decidable in 2-NExpTime for t…
Finite Model Reasoning in Expressive Fragments of First-Order Logic
Lidia Tendera
Over the past two decades several fragments of first-order logic have been identified and shown to have good computational and algorithmic properties, to a great extent as a result…