Joint work with B. Bumpkis, T. Eagling-Vose, J. Enright, M. Fellows, D. Kutner, L. Laros-Jones, B. Martin, F. Rosamond, and E. Yates

I report on recent work seeking to understand the lower reaches of fixed parameter tractability. These are problems solvable, with parameter $k$,

in time $a\cdot |\langle x,k\rangle | +f(k)$. The model we use is the word RAM model. We believe that this is motivated by practical considerations and it has proven that this class is remarkably 

well-populated, and would see of relevance to ``big data’’. 

This paper presents models for counterfactual (e.g., "if it were that … then it would be that”) and deontic operators (e.g. “it ought to be that .. “ “it is permissible that …”) in the framework of the state semantics for substructural logics. The state semantics utilises a distinction between minimal and non-minimal states. The semantics for counterfactuals and deontic operators illustrates that usefulness of minimal states.

For a logician, Brouwerian semilattices are algebraic models of

implication-conjunction fragment of the intuitionistic propositional logic

(INT), and Hilbert algebras are algebraic models of the implication fragment of

INT. Similarly, Brouwerian semilattices wth zero and Hilbert algebras with zero,

are the same for implication-conjuction-negation and implication-negation

fragments of INT. For the whole variety of Brouwerian semilattices a

construction of free algebras is well known since 1970s, and for the whole

variety of Hilbert algebras a construction was implicitly known.

Our construction uses a new method that is modular in an engineering sense: for

any given subvariety V (of Brouwerian semilatices, Hilbert algebras, or their

zero-expansions) it can be modified to apply to V, essentially by changing one

parameter. If subdirectly irreducible algebras in V have an effective

description, then the construction is algorithmic. Exact sizes of a few free

algebras will be given. The largest number we will see is that of the

3-generated Hilbert algebra with zero: its order of magnitude is 10^647.

This is joint work with  Carles Noguera, Gaia Petreni, Alice Portone and Val Tannen.

In this paper, we study the containment problem for (unions of) conjunctive queries ((U)CQs) with negative information on semiring-annotated databases. Our approach to negative information follows the treatment of negation proposed by Grädel and Tannen (2017, 2019, 2021 and 2024) for first-order logic and fixed point logic which applies productively to large classes of semirings, including bounded distributive lattices, as well as the important provenance semirings studied for positive CQ containment by Green (2009).

Negation features in (U)CQs along two dimensions: negated equalities (disequations), and negated relational atoms. We study complexity for each of them separately, as well as jointly. For disequations, we extend a methodology that proves the same complexity bounds (in the second level of the polynomial hierarchy) for our semirings of interest as the ones already known for the standard  Boolean semiring. For CQs with negated relational atoms  we show that the complexity, surprisingly, is the same as that of the containment of  CQs without negation when one considers model-defining and provenance-tracking interpretations (namely, nondeterministic polynomial time).  Interestingly, among bounded distributive lattices, the Boolean two-element case is the only one where the complexity of the problem continues to be hard for the second level of the polynomial hierarchy for model-defining interpretations. Furthermore, we show that the complexity increases again for distributive lattices if we focus on other classes of interpretations. Finally, we consider queries that have both negated equalities and negated relational atoms and show that the complexity of containment continues to be that of the case with just negated equalities.

The work is joint with Yifan Jia and Heer Tern Koh.

We address a problem that originates in the algebraic semantics of programs:

Can every finitely generated computably enumerable algebra, viewed as the semantics of a program, be specified by a finite set of equations or quasi-equations after expanding its signature?

This question was posed by Bergstra and Tucker in the late 1970s and early 1980s \cite{BT1983} (also see \cite{2BT1979, BT1979}), and independently by S. Goncharov in the mid 1980s  \cite{Goncharov1986}. It has remained open since. We answer the question in the negative, and a three-way interplay between universal algebra, model theory, and computability theory underlies our proof, with effective procedures playing a central role throughout. This settles the foundational question of whether every computably enumerable data type can be finitely axiomatized when conditional equations and auxiliary operations are permitted.

TBA

In recent years, the speaker, together with collaborators, has been investigating

subtoposes of the realizability topos, with a focus on their deep connections to concrete computability theory (degree theory). Furthermore, applications to constructive

reverse mathematics and links to filter combinatorics have been uncovered. In this talk,

I will provide an overview of the rapid recent progress in the study of subtoposes of

realizability toposes, driven by these concrete theories.

 In a landmark study of existentially closed groups, Martin Ziegler introduced what is now called Ziegler reducibility, \leq_Z.  It is a common refinement of Turing and enumeration reducibility, and Ziegler showed that it characterises when one group is, in a suitable sense, \exists-definable relative to another. Inspired by this result and by a programme of building a dictionary between subshifts and groups, Nakid Cordero and I prove an analogous theorem for subshifts. We introduce a notion of one subshift being finitely determined over another, and show that this holds exactly when the co-language of the first is Ziegler reducible to the co-language of the second. In contrast, the natural notion of existential closure for subshifts does not satisfy an analogue of Ziegler’s theorem.

On the degree-theoretic side, I will discuss the structure and complexity of the Ziegler degrees.  This is joint work with Downey, Lempp, and Jacobsen-Grocott.