5 papers
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. % fo…
Characterizing Small Circuit Classes from FAC^0 to FAC^1 via Discrete Ordinary Differential Equations
Melissa Antonelli, Arnaud Durand, 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 r…
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…
A Primer for Preferential Non-Monotonic Propositional Team Logics
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…
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…