31 citations · 101 across the 14 of their papers we have counts for
21 papers
Arity hierarchies for quantifiers closed under partial polymorphisms
Anuj Dawar, Lauri Hella, Benedikt Pago
We investigate the expressive power of generalized quantifiers closed under partial polymorphism conditions motivated by the study of constraint satisfaction problems. We answer a…
Regular Representations of Uniform TC^0
Lauri Hella, Juha Kontinen, Kerkko Luosto
The circuit complexity class DLOGTIME-uniform AC^0 is known to be a modest subclass of DLOGTIME-uniform TC^0. The weakness of AC^0 is caused by the fact that AC^0 is not closed und…
Quantifiers closed under partial polymorphisms
Anuj Dawar, Lauri Hella
We study Lindstrom quantifiers that satisfy certain closure properties which are motivated by the study of polymorphisms in the context of constraint satisfaction problems (CSP). W…
Dimension in team semantics
Lauri Hella, Kerkko Luosto, Jouko Väänänen
We introduce three measures of complexity for families of sets. Each of the three measures, that we call dimensions, is defined in terms of the minimal number of convex subfamilies…
Descriptive complexity for distributed computing with circuits
Veeti Ahvonen, Damian Heiman, Lauri Hella +1
We consider distributed algorithms in the realistic scenario where distributed message passing is operated via circuits. We show that within this setting, modal substitution calcul…
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…
A Completeness Proof for A Regular Predicate Logic with Undefined Truth Value
Antti Valmari, Lauri Hella
We provide a sound and complete proof system for an extension of Kleene's ternary logic to predicates. The concept of theory is extended with, for each function symbol, a formula t…
Bounded Game-Theoretic Semantics for Modal Mu-Calculus and Some Variants
Lauri Hella, Antti Kuusisto, Raine Rönnholm
We introduce a new game-theoretic semantics (GTS) for the modal mu-calculus. Our so-called bounded GTS replaces parity games with alternative evaluation games where only finite pat…
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…
Complexity Thresholds in Inclusion Logic
Miika Hannula, Lauri Hella
Logics with team semantics provide alternative means for logical characterization of complexity classes. Both dependence and independence logic are known to capture non-determinist…
Bounded game-theoretic semantics for modal mu-calculus
Lauri Hella, Antti Kuusisto, Raine Rönnholm
We introduce a new game-theoretic semantics (GTS) for the modal mu-calculus. Our so-called bounded GTS replaces parity games with alternative evaluation games where only finite pat…
Model Checking and Validity in Propositional and Modal Inclusion Logics
Lauri Hella, Antti Kuusisto, Arne Meier +1
Propositional and modal inclusion logic are formalisms that belong to the family of logics based on team semantics. This article investigates the model checking and validity proble…
The Succinctness of First-order Logic over Modal Logic via a Formula Size Game
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…
The expressive power of modal logic with inclusion atoms
Lauri Hella, Johanna Stumpf
Modal inclusion logic is the extension of basic modal logic with inclusion atoms, and its semantics is defined on Kripke models with teams. A team of a Kripke model is just a subse…
Satisfiability of Modal Inclusion Logic: Lax and Strict Semantics
Lauri Hella, Antti Kuusisto, Arne Meier +1
We investigate the computational complexity of the satisfiability problem of modal inclusion logic. We distinguish two variants of the problem: one for the strict and another one f…
Boolean Dependence Logic and Partially-Ordered Connectives
Johannes Ebbing, Lauri Hella, Peter Lohmann +1
We introduce a new variant of dependence logic called Boolean dependence logic. In Boolean dependence logic dependence atoms are of the type =(x_1,...,x_n,α), where αis a Boolean v…
The Expressive Power of Modal Dependence Logic
Lauri Hella, Kerkko Luosto, Katsuhiko Sano +1
We study the expressive power of various modal logics with team semantics. We show that exactly the properties of teams that are downward closed and closed under team k-bisimulatio…
One-dimensional fragment of first-order logic
Lauri Hella, Antti Kuusisto
We introduce a novel decidable fragment of first-order logic. The fragment is one-dimensional in the sense that quantification is limited to applications of blocks of existential (…
Inclusion Logic and Fixed Point Logic
Pietro Galliani, Lauri Hella
We investigate the properties of Inclusion Logic, that is, First Order Logic with Team Semantics extended with inclusion dependencies. We prove that Inclusion Logic is equivalent t…
The size of a formula as a measure of complexity
Lauri Hella, Jouko Väänänen
We introduce a refinement of the usual Ehrenfeucht-Fra\"ıssé game. The new game will help us make finer distinctions than the traditional one. In particular, it can be used to meas…
Weak Models of Distributed Computing, with Connections to Modal Logic
Lauri Hella, Matti Järvisalo, Antti Kuusisto +5
This work presents a classification of weak models of distributed computing. We focus on deterministic distributed algorithms, and study models of computing that are weaker version…