ABSTRACT. In this talk we introduce the type-2 analogue of \textsf{FLOGSPACE}, defined through oracle Turing machines, answering a question raised by Kawamura. We show that this class, dubbed \emph{Easy Feasible Functionals} (\textsf{EFF}) is robust, being closed by both type-0 and type-1 composition.

ABSTRACT. See PDF

ABSTRACT. The talk will be based on two preperints on sequential theories. One paper shows that a certain weak set theory of Harvey Friedman requires a parameter to witness its sequentiality. The other paper proves non-sequentiality of a certain extension of Robinson`s Q with pairing. This theory is a subtheory of PA^_, the theory of nonnegative of parts of discretely ordered commutative rings.

ABSTRACT. This work investigates the expressive power of ontology-mediated queries (OMQs) from a descriptive complexity perspective. We first show that OMQ languages based on non-monotonic extension of one of the most expressive description logics cannot express all coNP-computable generic Boolean queries, despite being coNP-complete in data complexity. We then propose an extension of this language and show that it is expressive enough to precisely capture the class of all Boolean queries computable in coNP.

ABSTRACT. Answer Set Programming (ASP) is a mature and widely used framework for modeling and solving problems in AI, knowledge representation and reasoning, and combinatorial search. Counting answer sets is of growing importance for analyzing search spaces, navigating ASP programs, and enabling probabilistic reasoning. While Truszczýnski established a complete hierarchy for the computational complexity of ASP decision and reasoning problems (skeptical and credulous), a corresponding systematic treatment of counting problems has been missing so far. We close this gap by providing an almost complete characterisation of the counting complexity landscape for ASP.