31 citations · 83 across the 33 of their papers we have counts for
6 papers · 1 filter
Decidability of predicate logics with team semantics
Juha Kontinen, Antti Kuusisto, Jonni Virtema
We study the complexity of predicate logics based on team semantics. We show that the satisfiability problems of two-variable independence logic and inclusion logic are both NEXPTI…
Complexity and Expressivity of Uniform One-Dimensional Fragment with Equality
Emanuel Kieroński, Antti Kuusisto
Uniform one-dimensional fragment UF1^= is a formalism obtained from first-order logic by limiting quantification to applications of blocks of existential (universal) quantifiers su…
Infinite Networks, Halting and Local Algorithms
Antti Kuusisto
The immediate past has witnessed an increased amount of interest in local algorithms, i.e., constant time distributed algorithms. In a recent survey of the topic (Suomela, ACM Comp…
Team Semantics and Recursive Enumerability
Antti Kuusisto
It is well known that dependence logic captures the complexity class NP, and it has recently been shown that inclusion logic captures P on ordered models. These results demonstrate…
Some Turing-Complete Extensions of First-Order Logic
Antti Kuusisto
We introduce a natural Turing-complete extension of first-order logic FO. The extension adds two novel features to FO. The first one of these is the capacity to add new points to m…
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 (…