2 papers
cs.LO2018
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…
cs.LO2018
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…