Juha Kontinen

TCS Journal 2026 Journal Article

Towards new characterizations of small circuit classes via discrete ordinary differential equations

• Melissa Antonelli
• Arnaud Durand
• Juha Kontinen

Implicit computational complexity is a lively area of theoretical computer science, which aims to provide machine-independent characterizations of relevant complexity classes. One of the seminal works in this field appeared in the 1960s, when Cobham introduced a function algebra closed under bounded recursion on notation to capture polynomial time computable functions (FP). Later on, several complexity classes have been characterized using limited recursion schemas. In this context, an original approach has been recently introduced, showing that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and providing a characterization of FP by a new ODE-schema. In the present paper we generalize this approach by presenting original ODE-characterizations for the small circuit classes FAC 0 and FTC 0.

MFCS Conference 2025 Conference Paper

Characterizing Small Circuit Classes from FAC⁰ to FAC¹ via Discrete Ordinary Differential Equations

• Melissa Antonelli
• Arnaud Durand 0001
• Juha Kontinen

In this paper, we provide a uniform framework for investigating small circuit classes and bounds through the lens of ordinary differential equations (ODEs). Following an approach recently introduced to capture the class of polynomial-time computable functions via ODE-based recursion schemas and later applied to the context of functions computed by unbounded fan-in circuits of constant depth (FAC⁰), we study multiple relevant small circuit classes. In particular, we show that natural restrictions on linearity and derivation along functions with specific growth rate correspond to kinds of functions that can be proved to be in various classes, ranging from FAC⁰ to FAC¹. This reveals an intriguing link between constraints over linear-length ODEs and circuit computation, providing new tools to tackle the complex challenge of establishing bounds for classes in the circuit hierarchies and possibly enhancing our understanding of the role of counters in this setting. Additionally, we establish several completeness results, in particular obtaining the first ODE-based characterizations for the classes of functions computable in constant depth with unbounded fan-in and Mod 2 gates (FACC[2]) and in logarithmic depth with bounded fan-in Boolean gates (FNC¹).

OVERLAY Workshop 2025 Workshop Paper

Circuit Complexity Meets Discrete Ordinary Differential Equations: An Overview

• Melissa Antonelli
• Arnaud Durand
• Juha Kontinen

KR Conference 2025 Conference Paper

On the Complexity and Properties of Preferential Propositional Dependence Logic

• Kai Sauerwald
• Arne Meier
• Juha Kontinen

This paper considers the complexity and properties of KLM-style preferential reasoning in the setting of propositional logic with team semantics and dependence atoms, also known as propositional dependence logic. Preferential team-based reasoning is shown to be cumulative, yet violates System P. We give intuitive conditions that fully characterise those cases where preferential propositional dependence logic satisfies System P. We show that these characterisations do, surprisingly, not carry over to preferential team-based propositional logic. Furthermore, we show how classical entailment and dependence logic entailment can be expressed in terms of non-trivial preferential models. Finally, we present the complexity of preferential team-based reasoning for two natural representations. This includes novel complexity results for classical (non-team-based) preferential reasoning.

I&C Journal 2025 Journal Article

Set semantics for asynchronous TeamLTL: Expressivity and complexity

• Juha Kontinen
• Max Sandström
• Jonni Virtema

We introduce and develop a set-based semantics for asynchronous TeamLTL. We consider two canonical logics in this setting: the extensions of TeamLTL by the Boolean disjunction and by the Boolean negation. We relate the new semantics with the original semantics based on multisets and establish one of the first positive complexity theoretic results in the temporal team semantics setting. In particular we show that both logics enjoy normal forms that can be utilised to obtain results related to expressivity and complexity (decidability) of the new logics.

NMR Workshop 2024 Conference Paper

A First Peek into Preferential Logics with Team Semantics

• Kai Sauerwald
• Juha Kontinen

This paper considers KLM-style preferential non-monotonic reasoning in the setting of propositional team semantics. We show that team-based propositional logics naturally give rise to cumulative non-monotonic entailment relations. Motivated by the non-classical interpretation of disjunction in team semantics, we give a precise characterization for preferential models for propositional dependence logic satisfying all of System P postulates. Furthermore, we show how classical entailment and dependence logic entailment can be expressed in terms of non-trivial preferential models.

MFCS Conference 2024 Conference Paper

A New Characterization of FAC⁰ via Discrete Ordinary Differential Equations

• Melissa Antonelli
• Arnaud Durand 0001
• Juha Kontinen

Implicit computational complexity is an active area of theoretical computer science, which aims at providing machine-independent characterizations of relevant complexity classes. One of the seminal works in this field appeared in 1965, when Cobham introduced a function algebra closed under bounded recursion on notation to capture FP. Later on, several complexity classes have been characterized using limited recursion schemas. In this context, a new approach was recently introduced, showing that ordinary differential equations (ODEs) offer a natural tool for algorithmic design and providing a characterization of FP by an ODE-schema. The overall goal of the present work is precisely that of generalizing this approach to parallel computation, obtaining an original ODE-characterization for the small circuit classes FAC⁰ and FTC⁰.

AAAI Conference 2024 Conference Paper

Complexity of Neural Network Training and ETR: Extensions with Effectively Continuous Functions

• Teemu Hankala
• Miika Hannula
• Juha Kontinen
• Jonni Virtema

The training problem of neural networks (NNs) is known to be ER-complete with respect to ReLU and linear activation functions. We show that the training problem for NNs equipped with arbitrary activation functions is polynomial-time bireducible to the existential theory of the reals extended with the corresponding activation functions. For effectively continuous activation functions (e.g., the sigmoid function), we obtain an inclusion to low levels of the arithmetical hierarchy. Consequently, the sigmoid activation function leads to the existential theory of the reals with the exponential function, and hence the decidability of training NNs using the sigmoid activation function is equivalent to the decidability of the existential theory of the reals with the exponential function, a long-standing open problem. In contrast, we obtain that the training problem is undecidable if sinusoidal activation functions are considered.

JELIA Conference 2023 Conference Paper

Logics with Probabilistic Team Semantics and the Boolean Negation

• Miika Hannula
• Minna Hirvonen
• Juha Kontinen
• Yasir Mahmood 0002
• Arne Meier
• Jonni Virtema

Abstract We study the expressivity and the complexity of various logics in probabilistic team semantics with the Boolean negation. In particular, we study the extension of probabilistic independence logic with the Boolean negation, and a recently introduced logic FOPT. We give a comprehensive picture of the relative expressivity of these logics together with the most studied logics in probabilistic team semantics setting, as well as relating their expressivity to a numerical variant of second-order logic. In addition, we introduce novel entropy atoms and show that the extension of first-order logic by entropy atoms subsumes probabilistic independence logic. Finally, we obtain some results on the complexity of model checking, validity, and satisfiability of our logics.

MFCS Conference 2023 Conference Paper

Set Semantics for Asynchronous TeamLTL: Expressivity and Complexity

• Juha Kontinen
• Max Sandström
• Jonni Virtema

We introduce and develop a set-based semantics for asynchronous TeamLTL. We consider two canonical logics in this setting: the extensions of TeamLTL by the Boolean disjunction and by the Boolean negation. We relate the new semantics with the original semantics based on multisets and establish one of the first positive complexity theoretic results in the temporal team semantics setting. In particular we show that both logics enjoy normal forms that can be utilised to obtain results related to expressivity and complexity (decidability) of the new logics.

KR Conference 2023 Conference Paper

Unified Foundations of Team Semantics via Semirings

• Timon Barlag
• Miika Hannula
• Juha Kontinen
• Nina Pardal
• Jonni Virtema

Semiring semantics for first-order logic provides a way to trace how facts represented by a model are used to deduce satisfaction of a formula. Team semantics is a framework for studying logics of dependence and independence in diverse contexts such as databases, quantum mechanics, and statistics by extending first-order logic with atoms that describe dependencies between variables. Combining these two, we propose a unifying approach for analysing the concepts of dependence and independence via a novel semiring team semantics, which subsumes all the previously considered variants for first-order team semantics. In particular, we study the preservation of satisfaction of dependencies and formulae between different semirings. In addition we create links to reasoning tasks such as provenance, counting, and repairs.

CSL Conference 2021 Conference Paper

On the Complexity of Horn and Krom Fragments of Second-Order Boolean Logic

• Miika Hannula
• Juha Kontinen
• Martin Lück
• Jonni Virtema

Second-order Boolean logic is a generalization of QBF, whose constant alternation fragments are known to be complete for the levels of the exponential time hierarchy. We consider two types of restriction of this logic: 1) restrictions to term constructions, 2) restrictions to the form of the Boolean matrix. Of the first sort, we consider two kinds of restrictions: firstly, disallowing nested use of proper function variables, and secondly stipulating that each function variable must appear with a fixed sequence of arguments. Of the second sort, we consider Horn, Krom, and core fragments of the Boolean matrix. We classify the complexity of logics obtained by combining these two types of restrictions. We show that, in most cases, logics with k alternating blocks of function quantifiers are complete for the kth or (k-1)th level of the exponential time hierarchy. Furthermore, we establish NL-completeness for the Krom and core fragments, when k = 1 and both restrictions of the first sort are in effect.

MFCS Conference 2019 Conference Paper

Counting of Teams in First-Order Team Logics

• Anselm Haak
• Juha Kontinen
• Fabian Müller 0003
• Heribert Vollmer
• Fan Yang 0004

We study descriptive complexity of counting complexity classes in the range from #P to #*NP. A corollary of Fagin’s characterization of NP by existential second-order logic is that #P can be logically described as the class of functions counting satisfying assignments to free relation variables in first-order formulae. In this paper we extend this study to classes beyond #P and extensions of first-order logic with team semantics. These team-based logics are closely related to existential second-order logic and its fragments, hence our results also shed light on the complexity of counting for extensions of first-order logic in Tarski’s semantics. Our results show that the class #*NP can be logically characterized by independence logic and existential second-order logic, whereas dependence logic and inclusion logic give rise to subclasses of #*NP and #P, respectively. We also study the function class generated by inclusion logic and relate it to the complexity class TotP, which is a subclass of #P. Our main technical result shows that the problem of counting satisfying assignments for monotone Boolean Sigma_1-formulae is #*NP-complete with respect to Turing reductions as well as complete for the function class generated by dependence logic with respect to first-order reductions.

JELIA Conference 2019 Conference Paper

Facets of Distribution Identities in Probabilistic Team Semantics

• Miika Hannula
• Åsa Hirvonen
• Juha Kontinen
• Vadim Kulikov
• Jonni Virtema

Abstract We study probabilistic team semantics which is a semantical framework allowing the study of logical and probabilistic dependencies simultaneously. We examine and classify the expressive power of logical formalisms arising by different probabilistic atoms such as conditional independence and different variants of marginal distribution equivalences. We also relate the framework to the first-order theory of the reals and apply our methods to the open question on the complexity of the implication problem of conditional independence.

LPAR Conference 2017 Conference Paper

On the Interaction of Inclusion Dependencies with Independence Atoms

• Miika Hannula
• Juha Kontinen
• Sebastian Link

Inclusion dependencies are one of the most important database constraints. In isolation their finite and unrestricted implication problems coincide, are finitely axiomatizable, PSPACE-complete, and fixed-parameter tractable in their arity. In contrast, finite and unrestricted implication problems for the combined class of functional and inclusion de- pendencies deviate from one another and are each undecidable. The same holds true for the class of embedded multivalued dependencies. An important embedded tractable fragment of embedded multivalued dependencies are independence atoms. These stipulate independence between two attribute sets in the sense that for every two tuples there is a third tuple that agrees with the first tuple on the first attribute set and with the second tuple on the second attribute set. For independence atoms, their finite and unrestricted implication problems coincide, are finitely axiomatizable, and decidable in cubic time. In this article, we study the implication problems of the combined class of independence atoms and inclusion dependencies. We show that their finite and unrestricted implication problems coincide, are finitely axiomatizable, PSPACE-complete, and fixed-parameter tractable in their arity. Hence, significant expressivity is gained without sacrificing any of the desirable properties that inclusion dependencies have in isolation. Finally, we establish an efficient condition that is sufficient for independence atoms and inclusion dependencies not to inter- act. The condition ensures that we can apply known algorithms for deciding implication of the individual classes of independence atoms and inclusion dependencies, respectively, to decide implication for an input that combines both individual classes.

I&C Journal 2016 Journal Article

A finite axiomatization of conditional independence and inclusion dependencies

• Miika Hannula
• Juha Kontinen

We present a complete finite axiomatization of the unrestricted implication problem for inclusion and conditional independence atoms in the context of dependence logic. For databases, this result implies a finite axiomatization of the unrestricted implication problem for inclusion, functional, and embedded multivalued dependencies in the unirelational case. We also indicate the generality of our approach by showing the analogous result for inclusion and embedded join dependencies.

MFCS Conference 2016 Conference Paper

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 NEXPTIME-complete. Furthermore, we show that the validity problem of two-variable dependence logic is undecidable, thereby solving an open problem from the team semantics literature. We also briefly analyse the complexity of the Bernays-Schoenfinkel-Ramsey prefix classes of dependence logic.

CSL Conference 2016 Conference Paper

Descriptive Complexity of #AC 0 Functions

• Arnaud Durand 0001
• Anselm Haak
• Juha Kontinen
• Heribert Vollmer

We introduce a new framework for a descriptive complexity approach to arithmetic computations. We define a hierarchy of classes based on the idea of counting assignments to free function variables in first-order formulae. We completely determine the inclusion structure and show that #P and #AC^0 appear as classes of this hierarchy. In this way, we unconditionally place #AC^0 properly in a strict hierarchy of arithmetic classes within #P. We compare our classes with a hierarchy within #P defined in a model-theoretic way by Saluja et al. We argue that our approach is better suited to study arithmetic circuit classes such as #AC^0 which can be descriptively characterized as a class in our framework.

GandALF Workshop 2016 Workshop Paper

On Quantified Propositional Logics and the Exponential Time Hierarchy

• Miika Hannula
• Juha Kontinen
• Martin Lück
• Jonni Virtema

We study quantified propositional logics from the complexity theoretic point of view. First we introduce alternating dependency quantified boolean formulae (ADQBF) which generalize both quantified and dependency quantified boolean formulae. We show that the truth evaluation for ADQBF is AEXPTIME(poly)-complete. We also identify fragments for which the problem is complete for the levels of the exponential hierarchy. Second we study propositional team-based logics. We show that DQBF formulae correspond naturally to quantified propositional dependence logic and present a general NEXPTIME upper bound for quantified propositional logic with a large class of generalized dependence atoms. Moreover we show AEXPTIME(poly)-completeness for extensions of propositional team logic with generalized dependence atoms.

CSL Conference 2015 Conference Paper

A Van Benthem Theorem for Modal Team Semantics

• Juha Kontinen
• Julian-Steffen Müller
• Henning Schnoor
• Heribert Vollmer

The famous van Benthem theorem states that modal logic corresponds exactly to the fragment of first-order logic that is invariant under bisimulation. In this article we prove an exact analogue of this theorem in the framework of modal dependence logic (MDL) and team semantics. We show that Modal Team Logic (MTL) extending MDL by classical negation captures exactly the FO-definable bisimulation invariant properties of Kripke structures and teams. We also compare the expressive power of MTL to most of the variants and extensions of MDL recently studied in the area.

GandALF Workshop 2015 Workshop Paper

Tractability Frontier of Data Complexity in Team Semantics

• Arnaud Durand
• Juha Kontinen
• Nicolas de Rugy-Altherre
• Jouko Väänänen

We study the data complexity of model-checking for logics with team semantics. For dependence and independence logic, we completely characterize the tractability/intractability frontier of data complexity of both quantifier-free and quantified formulas. For inclusion logic formulas, we reduce the model-checking problem to the satisfiability problem of so-called Dual-Horn propositional formulas. Via this reduction, we give an alternative proof for the recent result showing that the data complexity of inclusion logic is in PTIME.

I&C Journal 2014 Journal Article

Complexity of two-variable dependence logic and IF-logic

• Juha Kontinen
• Antti Kuusisto
• Peter Lohmann
• Jonni Virtema

We study the two-variable fragments D 2 and IF 2 of dependence logic and independence-friendly logic. We consider the satisfiability and finite satisfiability problems of these logics and show that for D 2, both problems are NEXPTIME-complete, whereas for IF 2, the problems are Π 1 0 and Σ 1 0 -complete, respectively. We also show that D 2 is strictly less expressive than IF 2 and that already in D 2, equicardinality of two unary predicates and infinity can be expressed (the latter in the presence of a constant symbol). This is an extended version of a publication in the proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science (LICS 2011).

CSL Conference 2013 Conference Paper

Hierarchies in independence logic

• Pietro Galliani
• Miika Hannula
• Juha Kontinen

We study the expressive power of fragments of inclusion and independence logic defined either by restricting the number of universal quantifiers or the arity of inclusion and independence atoms in formulas. Assuming the so-called lax semantics for these logics, we relate these fragments of inclusion and independence logic to familiar sublogics of existential second-order logic. We also show that, with respect to the stronger strict semantics, inclusion logic is equivalent to existential second-order logic.

I&C Journal 2011 Journal Article

Extensions of MSO and the monadic counting hierarchy

• Juha Kontinen
• Hannu Niemistö

In this paper, we study the expressive power of the extension of first-order logic by the unary second-order majority quantifier Most1. In 1 it was shown that the extension of FO by second-order majority quantifiers of all arities describes exactly the problems in the counting hierarchy. We consider first certain sublogics of FO(Most1) over unary vocabularies. We show that over unary vocabularies the logic MSO(R), where MSO is monadic second-order logic and R is the first-order Rescher quantifier, can be characterized by Presburger arithmetic, whereas the logic MSO ( R n ) n ∈ Z +, where R n is the nth vectorization of R, corresponds to the Δ 0 -fragment of arithmetic. Then we show that FO ( Most 1 ) ⩾ MSO ( R n ) n ∈ Z + and that, on unary vocabularies, FO(Most1) collapses to uniform-TC0. Using this collapse, we show that first-order logic with the binary second-order majority quantifier is strictly more expressive than FO(Most1) over the empty vocabulary. On the other hand, over strings, FO(Most1) is shown to capture the linear fragment of the counting hierarchy. Finally we show that, over non-unary vocabularies, FO(Most1) can express problems complete via first-order reductions for each level of the counting hierarchy.