11 citations · 19 across the 12 of their papers we have counts for
5 papers · 1 filter
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…
Defining long words succinctly in FO and MSO
Lauri Hella, Miikka Vilander
We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of heig…
Games for Succinctness of Regular Expressions
Miikka Vilander
We present a version of so called formula size games for regular expressions. These games characterize the equivalence of languages up to expressions of a given size. We use the re…
Formula size games for modal logic and -calculus
Lauri Hella, Miikka Vilander
We propose a new version of formula size game for modal logic. The game characterizes the equivalence of pointed Kripke-models up to formulas of given numbers of modal operators an…
On the Succinctness of Atoms of Dependency
Martin Lück, Miikka Vilander
Propositional team logic is the propositional analog to first-order team logic. Non-classical atoms of dependence, independence, inclusion, exclusion and anonymity can be expressed…