2 citations · 3 across the 16 of their papers we have counts for
4 papers · 2 filters
An Extension of Trakhtenbrot's Theorem
Reijo Jaakkola
The celebrated Trakhtenbrot's theorem states that the set of finitely valid sentences of first-order logic is not computably enumerable. In this note we will extend this theorem by…
Complexity of the Ackermann fragment with one leading existential quantifier
Reijo Jaakkola
In this short note we prove that the satisfiability problem of the Ackermann fragment with one leading existential quantifier is ExpTime-complete.
Uniform Guarded Fragments
Reijo Jaakkola
In this paper we prove that the uniform one-dimensional guarded fragment, which is a natural polyadic generalization of the guarded two-variable logic, has the Craig interpolation…
Ordered fragments of first-order logic
Reijo Jaakkola
Using a recently introduced algebraic framework for the classification of fragments of first-order logic, we study the complexity of the satisfiability problem for several ordered…