2 citations · 3 across the 16 of their papers we have counts for
19 papers
Graph Learning via Logic-Based Weisfeiler-Leman Variants and Tabularization
Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto +3
We present a novel approach for graph classification based on tabularizing graph data via new variants of the Weisfeiler-Leman algorithm and then applying methods for tabular data.…
Why this and not that? A Logic-based Framework for Contrastive Explanations
Tobias Geibinger, Reijo Jaakkola, Antti Kuusisto +2
We define several canonical problems related to contrastive explanations, each answering a question of the form ''Why P but not Q?''. The problems compute causes for both P and Q,…
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…
Globally Interpretable Classifiers via Boolean Formulas with Dynamic Propositions
Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto +2
Interpretability and explainability are among the most important challenges of modern artificial intelligence, being mentioned even in various legislative sources. In this article,…
Description Complexity of Unary Structures in First-Order Logic with Links to Entropy
Reijo Jaakkola, Antti Kuusisto, Miikka Vilander
The description complexity of a model is the length of the shortest formula that defines the model. We study the description complexity of unary structures in first-order logic FO,…
Interpretable classifiers for tabular data via discretization and feature selection
Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto +2
We introduce a method for computing immediately human interpretable yet accurate classifiers from tabular data. The classifiers obtained are short Boolean formulas, computed via fi…
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…
A monotone connection between model class size and description length
Reijo Jaakkola, Antti Kuusisto, Miikka Vilander
This paper links sizes of model classes to the minimum lengths of their defining formulas, that is, to their description complexities. Limiting to models with a fixed domain of siz…
Explainability via Short Formulas: the Case of Propositional Logic with Implementation
Reijo Jaakkola, Tomi Janhunen, Antti Kuusisto +2
We conceptualize explainability in terms of logic and formula size, giving a number of related definitions of explainability in a very general setting. Our main interest is the so-…
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…
Convergence in the space of compact labeled metric spaces
Reijo Jaakkola, Antti Kykkänen
A labeled metric space is intuitively speaking a metric space together with a special set of points to be understood as the geometric boundary of the space. We study basic properti…
Relating description complexity to entropy
Reijo Jaakkola, Antti Kuusisto, Miikka Vilander
We demonstrate some novel links between entropy and description complexity, a notion referring to the minimal formula length for specifying given properties. Let MLU be the logic o…
First-order logic with self-reference
Reijo Jaakkola, Antti Kuusisto
We consider an extension of first-order logic with a recursion operator that corresponds to allowing formulas to refer to themselves. We investigate the obtained language under two…
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…
Algebraic classifications for fragments of first-order logic and beyond
Reijo Jaakkola, Antti Kuusisto
Complexity and decidability of logics is a major research area involving a huge range of different logical systems. This calls for a unified and systematic approach for the field.…