4 papers
Enumerating Teams in First-Order Team Logics
Anselm Haak, Arne Meier, Fabian Müller +1
We start the study of the enumeration complexity of different satisfiability problems in first-order team logics. Since many of our problems go beyond DelP, we use a framework for…
Parameterised Counting in Logspace
Anselm Haak, Arne Meier, Om Prakash +1
In this paper, we introduce a new framework for parameterised counting in logspace, inspired by the parameterised space bounded models developed by Elberfeld, Stockhusen and Tantau…
Counting of Teams in First-Order Team Logics
Anselm Haak, Juha Kontinen, Fabian Müller +2
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 i…
Model-Theoretic Characterizations of Boolean and Arithmetic Circuit Classes of Small Depth
Arnaud Durand, Anselm Haak, Heribert Vollmer
In this paper we give a characterization of both Boolean and arithmetic circuit classes of logarithmic depth in the vein of descriptive complexity theory, i.e., the Boolean classes…