(joint work with Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield)

A key objective in the field of quantum information and computation is to understand the advantage which can be gained in information processing tasks by the use of quantum resources. While a range of examples have been studied, to date a systematic understanding of quantum advantage is lacking.

Our focus in this abstract is on quantum resources which take the form of non-local, or more generally contextual, correlations. Contextuality is one of the key signatures of non-classicality in quantum mechanics [7, 4], and has been shown to be a necessary ingredient for quantum advantage in a range of information processing tasks [8, 6, 5, 2]. In previous work [1], we introduced a notion of simulation between quantum resources, and more generally between resources described in terms of contextual correlations, in the “sheaf-theoretic” framework for contextuality introduced in [3]. The notion of simulation is expressed as a morphism of empirical models, in a form which allows the behaviour of one set of correlations to be simulated in terms of another using classical processing and shared randomization. Mathematically, this is expressed as coKleisli maps for a comonad of “measurement protocols” on the category of empirical models. This setting is expressive, and allows for a number of variations, e.g. grading the simulation by the number of copies of the simulating resource or by the depth of measurement adaptivity in the protocol, and also allows for a natural relaxation to a notion of approximate simulation.

As with classical notions of reducibility in computability and complexity theory, the existence of simulation maps allows us to compare different contextual behaviours in a fine-grained, mathematically robust way. We can define a degree of contextuality as an equivalence class of empirical models under two-way simulability. These degrees are then partially ordered by the existence of simulations between representatives. Existing results from the study of non-locality can be interpreted as showing the richness of this order, and there are many natural further questions which arise.

The property of (non)contextuality itself can be equivalently formulated as the existence of a simulation by an empirical model over the empty scenario [1]. This suggests that much of contextuality theory can be generalized to a “relativized” form, i.e. essentially working in slice categories.

As an example, consider the classic theorem of Vorob'ev [9]. It characterizes those scenarios over which all empirical models are noncontextual, in terms of an acyclicity condition on the underlying simplicial complex. This can be formulated as characterizing those scenarios such that every model over them can be simulated by a model over the empty scenario. More generally, we can ask for conditions on scenarios $(X, \Sigma, O)$ and $(Y, \Delta, P)$ such that every empirical model over $(Y, \Delta, P)$ can be simulated by some empirical model over $(X, \Sigma, O)$. We are beginning to study this “generalized Vorob'ev theory”.

References

1. Samson Abramsky, Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield. A comonadic view of simulation and quantum resources. In Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LiCS 2019), 2019. To appear, available at www.cs.ox.ac.uk.
2. Samson Abramsky, Rui Soares Barbosa, and Shane Mansfield. Contextual fraction as a measure of contextuality. Physical Review Letters, 119(5):050504, 2017.
3. Samson Abramsky and Adam Brandenburger. The sheaf-theoretic structure of non-locality and contextuality. New Journal of Physics, 13(11):113036, 2011.
4. John S Bell. On the problem of hidden variables in quantum mechanics. Reviews of Modern Physics, 38(3):447–452, 1966. doi:10.1103/RevModPhys.38.447.
5. Juan Bermejo-Vega, Nicolas Delfosse, Dan E Browne, Cihan Okay, and Robert Raussendorf. Contextuality as a resource for models of quantum computation with qubits. Physical Review Letters, 119(12):120505, 2017.
6. Mark Howard, Joel Wallman, Victor Veitch, and Joseph Emerson. Contextuality supplies the ‘magic’ for quantum computation. Nature, 510(7505):351, 2014.
7. Simon Kochen and Ernst P Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17(1):59–87, 1967.
8. Robert Raussendorf. Contextuality in measurement-based quantum computation. Physical Review A, 88(2):022322, 2013.
9. Nikolai Nikolaevich Vorob'ev. Consistent families of measures and their extensions. Theory of Probability & Its Applications, 7(2):147–163, 1962.

(joint work with Alexandru Baltag)

Dependence is a notion pervading many areas, from mathematical probability to reasoning with quantifiers, and from informational correlation in data bases to causal connections or interactive behavior in games. Not surprisingly, dependence has caught the attention of logicians, and various systems have been proposed over the last three decades for capturing basic notions of dependence and their fundamental logical laws.

In this talk, I will present a new decidable system of modal dependence logic, and explore its expressive strength and complete proof calculus. I also discuss its dynamic extensions when new information comes in, and its boundaries with more complex systems, e.g., for reasoning about independence. It will also become clear how the new logic relates to algebraic work on CRS, generalized assignment models for first-order logic, logics of knowledge about both facts and objects, and to probabilistic reasoning.

Domain theory in the narrow sense is concerned with continuous lattices and domains. In a wider sense, it may be regarded as the theory of

Topological Treatment of Transitive Terms and relations
Algebraic Aspects of Approximating Auxiliary relations
Categories of Core generated Closure and Convergence spaces
Lattices in the Logic of Languages and Lambda calculus.

For a preclosure operator $p$, the specialization order $\leq_p$ is given by $x\leq_p y \Leftrightarrow p\{x\}\subseteq p\{ y\}$, and the interior relation $\ll_p$ by $x\ll_p y \Leftrightarrow y\not\in p(X\setminus {\uparrow\!x})$; and $(X,p)$ is a called a precore space if $p\,{\downarrow} = {\downarrow\!p} = p$ and $y\in p(\ll_p\! y)$ for all $y\in X$ (the upset and downset operators, $\uparrow$ and $\downarrow$, refer to $\leq_p$). A core space is then a precore space with idempotent (closure operator) $p$. A fundamental observation is that the category of T$_0$ precore spaces is concretely isomorphic to that of posets with separating auxiliary relations, by sending $(X,p)$ to $(X,\leq_p,\ll_p)$. The classical continuous domains and their way-below relations are obtained by taking for $p$ the Scott preclosure operator, assigning to each subset $Y$ of a dcpo (directed complete poset) the lower set generated by all suprema of directed subsets of ${\downarrow\!Y}$.

Two classes of convergence spaces play a crucial role in the present context: a convergence space is core based resp. core generated iff each filter converging to a point contains another one that has a base resp. subbase of cores, where a core is the intersection of all neighborhoods of some point in the associated topological space. Hence, the topological core spaces are the C-spaces or worldwide web spaces, which are characterized by complete distributivity of their topology.

The theory of continuous lattices and domains admits flexible extensions to so-called $\M$-precontinuous posets $X$; here, $\M$ is a subset of $\PP X$, and each $y\in X$ is the supremum of the set ${\ll_{\M}\!y} = \bigcap \,\{ {\downarrow\!Z} : Z\in \M, y\in \Delta Z\}$, where $\Delta Z$ is the cut generated by $Z$. If the $\M$-below relation $\ll_{\M}$ has a certain weak interpolation property, we speak of $\M$-continuous posets, and if moreover the sets ${\ll_{\M}\!y}$ are directed, of $\M$-$d$-precontinuous resp. $\M$-$d$-continuous posets.

The Scott convergence, alias (lower) lim-inf convergence, is generalized in the present setting to the notion of $\M$-convergence: a net $\M$-converges to a point $x$ iff there is a set $Z\in \M$ of eventual lower bounds of the net such that $x$ belongs to $\Delta Z$ (which means $x\leq \bigvee Z$ if $Z$ has a supremum). Passing from nets to filters, one finds that the convergence-theoretical relevance of $\M$-precontinuity resp. $\M$-continuity for arbitrary sets $\M$ of $\omega$-ideals is manifested by the equivalence to the condition that $\M$-convergence is pretopological resp. topological.

The aforementioned connections between relational and topological structures in domain theory are made precise by concrete equivalences between the following triples of categories (where $\M$ runs through all collections of $\omega$-ideals):

$\M$-precontinuous posets
approximating $\omega$-ideal relations
core generated pretopological T$_0$ spaces

$\M$-$d$-precontinuous posets
approximating ideal relations
core based pretopological T$_0$ spaces

$\M$-continuous posets
approximating weakly interpolating $\omega$-ideal relations
core generated topological T$_0$ spaces

$\M$-$d$-continuous posets
approximating interpolating ideal relations
topological T$_0$ core spaces

Replacing posets and their cut operators with arbitrary closure spaces, equipped with their specialization order, one finally arrives at the definition of generalized continuous closure spaces, which provide a purely topological environment for domain theory, as demanded by leading workers in the field.

The aim of this talk is to show a connection between temporal logics and second order logics on discrete structures, mediated by model theory.

In formal language theory, logic can be used as a descriptive formalism which measures the complexity of a computational problem. For example, the MSO-definable sets of finite words are exactly the regular languages from automata theory. Büchi and Rabin established such translations between MSO logic and automata on many more structures, including omega- indexed words and various types of trees.

In model theory, logic can be used to give a general account of a mathematical construction; particularly relevant to this talk is the construction of the algebraic closure of a field. A fundamental insight due to Robinson is that the notion of algebraically closed field can be generalized to a purely logical notion of “existentially closed model”. The “model companion” of a first order theory, if it exists, gives a first order description of the class of existentially closed models.

This talk’s main thesis will be that MSO logic ‘is’ the model companion of temporal logic. That is, monadic second order (MSO) logic is to temporal logic as algebraically closed fields are to fields. Indeed, in joint work with Ghilardi, we proved such a model companion result both for words and for trees up to bisimulation. Extending these results to full MSO on trees is the subject of ongoing work.

I will survey a recent research program of investigating “possibility semantics”, a generalization of possible world semantics, for modal, superintuitionistic, and inquisitive logics. Relevant references include the following:

• G. Bezhanishvili and W. H. Holliday, “A semantic hierarchy for intuitionistic logic,” Indagationes Mathematicae, 2019.
• G. Bezhanishvili and W. H. Holliday, “Locales, nuclei, and Dragalin frames,” Advances in Modal Logic, 2016.
• N. Bezhanishvili and W. H. Holliday, “Choice-free Stone duality,” The Journal of Symbolic Logic, forthcoming.
• N. Bezhanishvili, G. Grilletti, and W. H. Holliday, “Algebraic and topological semantics for inquisitive logic via choice-free duality,” Proceedings of WoLLIC 2019.
• W. H. Holliday, “Algebraic semantics for S5 with propositional quantifiers,” Notre Dame Journal of Formal Logic, forthcoming.
• W. H. Holliday, “Partiality and adjointness in modal logic,” Advances in Modal Logic, 2014.
• W. H. Holliday, “Possibility frames and forcing for modal logic,” UC Berkeley Working Paper, 2015.
• W. H. Holliday and T. Litak, “Complete additivity and modal incompleteness,” The Review of Symbolic Logic, forthcoming.

(joint work with Christopher Hampson, Stanislav Kikot and Sérgio Marcelino)

Canonicity is a central notion in the theory of Boolean algebras with normal and additive operators (BAOs), and it is an important tool in proving Kripke completeness of propositional multimodal logics. The canonical extension $\A^\sigma$ of a BAO $\A$ is the Boolean set algebra consisting of all the ultrafilters of $\A$, with operators induced from those of $\A$. A variety of BAOs is said to be canonical if it is closed under taking canonical extensions. An equation $e$ is called canonical if for every algebra $\A$ of its signature, $\A\models e$ implies $\A^\sigma\models e$. Though in general canonicity of an equation is an undecidable ‘semantical’ property, there exist well-known syntactical classes of canonical equations, such as Sahlqvist equations and their generalisations by Goranko and Vakarelov.

While any set of canonical equations clearly axiomatises a canonical variety, the converse does not always hold for non-finitely based varieties. Well-known counterexamples are algebraisations of finite-variable fragments of classical first-order logic (representable relation algebras and cylindric algebras of dimension $\geq 3$, with or without diagonals): These are canonical varieties that are only barely canonical in the sense that every base for their equational theories must contain infinitely many non-canonical equations. On the other hand, for dimension 2, the situation is simpler: say, the equational theory of the variety $\mathsf{RDf}_2$ of two-dimensional (2D) representable diagonal-free cylindric algebras (the algebraic counterparts of two-variable substitution and equality free first-order logic) does have a finite Sahlqvist axiomatisation.

In this talk, we discuss the following ‘strict’ version of cylindrifications over binary relations (corresponding to the ‘elsewhere’ quantifier in first-order logic): \[ \begin{aligned} C^s_0 (X) & = \{ (u,v) : \exists u' (u'\ne u\mbox{ and }(u',v)\in X)\},\\ C^s_1 (X) & = \{ (u,v) : \exists v' (v'\ne v\mbox{ and }(u,v')\in X)\}. \end{aligned} \] (Then the usual cylindrifications are expressible as $C_i(X)=C^s_i(X)\cup X$.) It turns out that both the ‘rectangular’ and ‘square’ versions of 2D representable algebras of this kind behave unlike $\mathsf{RDf}_2$ in the sense that

1. they are non-finitely axiomatisable,
2. they have infinite canonical axiomatisations (for the ‘rectangular’ version even with Sahlqvist equations),
3. the ‘square’ version is non-finitely axiomatisable over the ‘rectangular’ version,
4. but can be axiomatised by adding infinitely many generalised Sahlqvist equations to the ‘rectangular’ version.

(based on joint work with Ramón Jansana)

Universal algebra and abstract algebraic logic are two disciplines that study, respectively, general algebraic structures and propositional logics. One of their main achievements is the development of two parallel taxonomies, one of varieties (a.k.a. equational classes) of algebras, and the other one of propositional logics.

More precisely, the Maltsev hierarchy of universal algebra is a classification of varieties in terms of syntactic principles (called Maltsev conditions) intended to describe the structure of the congruence lattices of algebras. The first, and perhaps most celebrated, example of a Maltsev condition is the requirement that a variety $\mathsf{K}$ is congruence permutable, equivalent to the syntactic requirement of the existence of a minority term for $\mathsf{K}$, i.e. a ternary term $\varphi(x, y, z)$ such that

Similarly, in abstract algebraic logic, the Leibniz hierarchy is a taxonomy of propositional logics in terms of rule schemata (called Leibniz conditions) whose aim is to govern the interplay between lattices of deductive filters (a.k.a. theories) of logics and lattices of congruences of algebras. One of the most fundamental examples of a Leibniz condition is the requirement that a logic $\vdash$ possesses a set $\Delta(x, y)$ of binary formulas satisfying the rules

which generalize the behavior of most implication connectives. This requirement is equivalent to the property that the Leibniz operator of the logic $\vdash$ is monotone.

From this point of view, it is natural to wonder whether the Maltsev and Leibniz hierarchies are two faces of the same coin. In this talk we investigate this and some related questions.

In this talk I will give an overview of several instances where Stone duality is underpinning important constructions in automata theory.

A first such example is a proof of correctness of Brzozowski’s minimization algorithm. Several constructions featured in this algorithm can be understood as liftings of well known adjunctions to categories of automata: determinization of automata can be understood via a lifting of the Kleisli adjunction between the category $\mathsf{Rel}$ of sets and relations and the category $\mathsf{Set}$ of sets and functions; while reversing nondeterministic automata can be understood via a lifting of the self-duality of $\mathsf{Rel}$.

A second application is a methodology for extending notions of algebraic recognition to their topological counterparts. I will discuss a notion of syntactic Boolean space associated to a language and extensions of well-known constructions on regular languages to a non-regular setting.

The talk is based on the papers [1] and [2, 3].

References

1. Thomas Colcombet and Daniela Petrişan. Automata minimization: a functorial approach. In CALCO, volume 72 of LIPIcs, pages 8:1–8:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
2. Mai Gehrke, Daniela Petrişan, and Luca Reggio. The Schützenberger product for syntactic spaces. In ICALP, volume 55 of LIPIcs, pages 112:1–112:14. Schloss Dagstuhl - Leibniz-Zentrum fuerInformatik, 2016.
3. Mai Gehrke, Daniela Petrişan, and Luca Reggio. Quantifiers on languages and codensity monads. In LICS, pages 1–12. IEEE Computer Society, 2017.

Sugihara monoids and Sugihara algebras provide complete algebraic semantics for the relevance logics $R$-mingle, with or without Ackermann's truth constant. The variety $\SA $ of Sugihara algebras is generated by $\mathbf Z= (Z, \land,\lor, \neg, \to)$ having the chain of integers as lattice reduct, $\neg a = -a$ and $a\to b = (-a) \vee b $ if $a\leqslant b$ and $(-a) \wedge b$ otherwise. For $\SM$, Sugihara monoids, the constant $0$ is added to the language. Both $\SA$ and $\SM$ are locally finite, with their finite subdirectly irreducible algebras having size $k$, for $k=2,3, \ldots$

The 2019 snapshot will showcase joint work with Leonardo Cabrer (preprints available through http://people.maths.ox.ac.uk/hap/). This work demonstrates the power of a range of duality techniques. We exploit dual equivalences with strong properties and capitalise on what the theory delivers at the finite level: ‘logarithmic’ behaviour, pictorial representations, and transparent access to finitely generated free algebras. Our aim is salesmanship: the underlying natural duality theory will be locked away in a black box.

Stone duality and Priestley duality have very special features. They are strong dualities: dual equivalences set up by hom-functors into a generating algebra and an alter ego, with both functors converting embeddings (surjections) to surjections (embeddings); moreover, duals of free algebras are given by concrete products. A duality of this type has been developed for any finitely generated quasivariety of Sugihara algebras. By moving to a framework allowing multisorted dual structures, one can embrace any finitely generated quasivariety or variety, and likewise for Sugihara monoids. Additionally, the multisorted approach facilitates transition to the Priestley duality for the lattice reducts. The relational structure on the dual side is supplied by partial endomorphisms and homomorphisms. The varieties $\SA$ and $\SM$ can be treated together. [To the initiated: no restriction to the odd case.]

Free algebras
Sugihara algebras and monoids have the property that any finitely generated free algebra $F$ can be calculated within some finitely generated (quasi)variety and so can be accessed easily using a multisorted natural duality for that (quasi)variety. From the natural dual of $F$ one can pass by a quotienting process to the Birkhoff dual $Y$ of $F$'s lattice reduct. This provides a picture of $Y$ which lends itself to combinatorial analysis. Moreover, the pictures display evidence of finite level Esakia duality coming into play. (Affinities between odd Sugihara monoids and Heyting algebras are known to exist in general.)

Admissibility algebras: a route to admissible rules for $R$-mingle.
An algebraic method due to Metcalfe and Röthlisberger for testing a rule for admissibility is only computationally feasible for varieties whose free algebras are small—a rare occurrence. Cabrer, Freisberg, Metcalfe and Priestley proved that, when a strong duality is available, the problem translates into dual form and this leads to an algorithm to find, for any $n$, a minimal ‘admissibility algebra’ on which to test rules (qua quasi-equations) in $n$ variables. Cabrer and Priestley applied the algorithm to each finitely generated Sugihara algebra quasivarieties, so providing a solution for any $k$ to a problem which is insoluble algebraically by computer when $k=5$ ($3$ variables).

We contrast our methods and results with those obtainable from dual equivalences between a category of expansions of distributive lattices and some category of structured Priestley spaces, of which there is a bewildering array in the literature. Equivalences of this type may yield valuable concrete representations and, by forgetting the topology, discrete dualities providing Kripke-style semantics for associated propositional logics. But there is no guarantee that algebraic, or logical, problems can be recast so that they become easier to solve in the dual setting.

This year marks the 50th anniversary of the submission to the Bulletin of the London Mathematical Society of Representation pf distributive lattices by means of ordered spaces, introducing what has become known as Priestley duality. The second, brief, snapshot will acknowledge a number of other contributions from long ago which have not received due recognition. (Here, the publication in 2019 of an edited English translation of Leo Esakia's classic monograph on duality for Heyting algebras is most welcome.) The opportunity will also be taken to highlight what, with hindsight, have proved to be major landmarks in the evolution of duality theory in a TACL context.

I will present a model-theoretic formalism for treating analytic and pro-etale covers of algebraic varieties. This allows a reformulation of Grothendieck's anabelian geometry. It also allows to consider questions of categoricity of respective theories (or rather abstract elementary classes).

A series of results obtained in 2002-2015 for semi-abelian varieties demonstrated that categoricity is equivalent to the classification of the action of Galois groups on the torsion subgroups together with relevant Kummer theory. In anabelian cases categoricity leads directly to conjectures about the action of Galois group on pro-finite fundamental group first raised in Grothendieck's “Esquisse d'un programme”.