11 citations · 16 across the 5 of their papers we have counts for
7 papers · 1 filter
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…
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…
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…