2 citations · 3 across the 16 of their papers we have counts for
8 papers · 1 filter
Formula size game and model checking for modal substitution calculus
Veeti Ahvonen, Reijo Jaakkola, Antti Kuusisto
Recent research has applied modal substitution calculus (MSC) and its variants to characterize various computational frameworks such as graph neural networks (GNNs) and distributed…
Short Boolean Formulas as Explanations in Practice
Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto +2
We investigate explainability via short Boolean formulas in the data model based on unary relations. As an explanation of length k, we take a Boolean formula of length k that minim…
Complexity of Polyadic Boolean Modal Logics: Model Checking and Satisfiability
Reijo Jaakkola
We study the computational complexity of model checking and satisfiability problems of polyadic modal logics extended with permutations and Boolean operators on accessibility relat…
Towards a Model Theory of Ordered Logics: Expressivity and Interpolation (Extended version)
Bartosz Bednarczyk, Reijo Jaakkola
We consider the family of guarded and unguarded ordered logics, that constitute a recently rediscovered family of decidable fragments of first-order logic (FO), in which the order…
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…