Publications

In preparation

  1. Tomáš Jakl, Dan Marsden, Nihil Shah: A game comonadic account of Courcelle and Feferman-Vaught-Mostowski theorems, arXiv:2205.05387.
  2. Tomáš Jakl, Dan Marsden, Nihil Shah: Generalizations of Bilinear Maps – Technical Report, arXiv:2205.05382.

Published or accepted

Discrete Density Comonads and Graph Parameters (with Samson Abramsky, Thomas Paine), In: H.H. Hansen, F. Zanasi (eds) Coalgebraic Methods in Computer Science. CMCS 2022. Lecture Notes in Computer Science, vol 13225. Springer, 2022.

BibTeX

@InProceedings{abramskyjaklpaine2022,
  author="Abramsky, Samson and Jakl, Tom{\'a}{\v{s}} and Paine, Thomas",
  title="Discrete Density Comonads and Graph Parameters",
  series="Lecture Notes in Computer Science",
  editor="Hansen, Helle Hvid and Zanasi, Fabio",
  booktitle="Coalgebraic Methods in Computer Science. CMCS 2022",
  year="2022",
  volume="13225",
  pages="23--44",
  publisher="Springer International Publishing",
  isbn="978-3-031-10736-8"
}

Abstract

Game comonads have brought forth a new approach to studying finite model theory categorically. By representing model comparison games semantically as comonads, they allow important logical and combinatorial properties to be exressed in terms of their Eilenberg-Moore coalgebras. As a result, a number of results from finite model theory, such as preservation theorems and homomorphism counting theorems, have been formalised and parameterised by comonads, giving rise to new results simply by varying the comonad. In this paper we study the limits of the comonadic approach in the combinatorial and homomorphism-counting aspect of the theory, regardless of whether any model comparison games are involved. We show that any standard graph parameter has a corresponding comonad, classifying the same class. This comonad is constructed via a simple Kan extension formula, making it the initial solution to this problem and, furthermore, automatically admitting a homomorphism-counting theorem.

A duality theoretic view on limits of finite structures (Extended version) (with Mai Gehrke, Luca Reggio), Logical Methods in Computer Science (Selected Papers of FoSSaCS 2020), Volume 18 (1), 2022.

BibTeX

@article{gehrkejaklreggio2022,
  TITLE = {{A duality theoretic view on limits of finite structures: Extended version}},
  AUTHOR = {Mai Gehrke and Tom{'a}{\v{s}} Jakl and Luca Reggio},
  URL = {https://lmcs.episciences.org/8978},
  DOI = {10.46298/lmcs-18(1:16)2022},
  JOURNAL = {{Logical Methods in Computer Science}},
  VOLUME = {{Volume 18, Issue 1}},
  YEAR = {2022},
  MONTH = Jan,
  KEYWORDS = {Computer Science - Logic in Computer Science ; Mathematics - Logic},
}

Abstract

A systematic theory of structural limits for finite models has been developed by Nesetril and Ossona de Mendez. It is based on the insight that the collection of finite structures can be embedded, via a map they call the Stone pairing, in a space of measures, where the desired limits can be computed. We show that a closely related but finer grained space of (finitely additive) measures arises – via Stone-Priestley duality and the notion of types from model theory – by enriching the expressive power of first-order logic with certain “probabilistic operators”. We provide a sound and complete calculus for this extended logic and expose the functorial nature of this construction.

The consequences are two-fold. On the one hand, we identify the logical gist of the theory of structural limits. On the other hand, our construction shows that the duality theoretic variant of the Stone pairing captures the adding of a layer of quantifiers, thus making a strong link to recent work on semiring quantifiers in logic on words. In the process, we identify the model theoretic notion of types as the unifying concept behind this link. These results contribute to bridging the strands of logic in computer science which focus on semantics and on more algorithmic and complexity related areas, respectively.

Lovász-type Theorems and Game Comonads (with Anuj Dawar, Luca Reggio), Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021.

BibTeX

@inproceedings{10.1109/LICS52264.2021.9470609,
    author = {Dawar, Anuj and Jakl, Tom\'{a}\v{s} and Reggio, Luca},
    title = {Lov\'{a}sz-Type Theorems and Game Comonads},
    year = {2021},
    isbn = {9781665448956},
    publisher = {Association for Computing Machinery},
    address = {New York, NY, USA},
    doi = {10.1109/LICS52264.2021.9470609},
    booktitle = {Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science},
    articleno = {53},
    pages={1-13},
    numpages = {13}
}

Abstract

Lovász (1967) showed that two finite relational structures A and B are isomorphic if, and only if, the number of homomorphisms from C to A is the same as the number of homomorphisms from C to B for any finite structure C. Soon after, Pultr (1973) proved a categorical generalisation of this fact. We propose a new categorical formulation, which applies to any locally finite category with pushouts and a proper factorisation system. As special cases of this general theorem, we obtain two variants of Lovász’ theorem: the result by Dvořák (2010) that characterises equivalence of graphs in the k-dimensional Weisfeiler-Leman equivalence by homomorphism counts from graphs of tree-width at most k, and the result of Grohe (2020) characterising equivalence with respect to first-order logic with counting and quantifier depth k in terms of homomorphism counts from graphs of tree-depth at most k. The connection of our categorical formulation with these results is obtained by means of the game comonads of Abramsky et al. We also present a novel application to homomorphism counts in modal logic.

A Cook’s tour of duality in logic: from quantifiers, through Vietoris, to measures (with Mai Gehrke, Luca Reggio), To appear in Outstanding Contribution to Logic (Springer).

Abstract

We identify and highlight certain landmark results in Samson Abramsky’s work which we believe are fundamental to current developments and future trends. In particular, we focus on the use of (i) topological duality methods to solve problems in logic and computer science; (ii) category theory and, more particularly, free (and co-free) constructions; (iii) these tools to unify the power' andstructure’ strands in computer science.

A Duality Theoretic View on Limits of Finite Structures (with Mai Gehrke and Luca Reggio), Foundations of Software Science and Computation Structures (FoSSaCS), Proceedings of the 23rd International Conference, Lecture Notes in Computer Science, Springer International Publishing, 2020.

BibTeX

@InProceedings{10.1007/978-3-030-45231-5_16,
  author = "Gehrke, Mai and Jakl, Tom{\'a}{\v{s}} and Reggio, Luca",
  editor = "Goubault-Larrecq, Jean and K{\"o}nig, Barbara",
  title = "A Duality Theoretic View on Limits of Finite Structures",
  booktitle = "Foundations of Software Science and Computation Structures",
  year = "2020",
  publisher = "Springer International Publishing",
  address = "Cham",
  pages = "299--318",
  isbn = "978-3-030-45231-5"
}

Abstract

A systematic theory of structural limits for finite models has been developed by Nešetřil and Ossona de Mendez. It is based on the insight that the collection of finite structures can be embedded, via a map they call the Stone pairing, in a space of measures, where the desired limits can be computed. We show that a closely related but finer grained space of measures arises — via Stone-Priestley duality and the notion of types from model theory — by enriching the expressive power of first-order logic with certain ``probabilistic operators’’. We provide a sound and complete calculus for this extended logic and expose the functorial nature of this construction.

Canonical extensions of locally compact frames, Topology and its Applications, Volume 273, 2020.

BibTeX

@article{jakl2020,
  author = "Tom{\'a}{\v{s}} Jakl",
  title = "Canonical extensions of locally compact frames",
  journal = "Topology and its Applications",
  volume = "273",
  pages = "106976",
  year = "2020",
  issn = "0166-8641",
  doi = "https://doi.org/10.1016/j.topol.2019.106976"
}

Abstract

Canonical extension of finitary ordered structures such as lattices, posets, proximity lattices, etc., is a certain completion which entirely describes the topological dual of the ordered structure and it does so in a purely algebraic and choice-free way. We adapt the general algebraic technique that constructs them to the theory of frames. As a result, we show that every locally compact frame embeds into a completely distributive lattice by a construction which generalises, among others, the canonical extensions for distributive lattices and proximity lattices. This construction also provides a new description of a construction by Marcel Erné. Moreover, canonical extensions of frames enable us to frame-theoretically represent monotone maps with respect to the specialisation order.

Quotients of d-frames (with Achim Jung, Aleš Pultr), Applied Categorical Structures, Volume 27 (3), 2019.

BibTeX

@article{jakljungpultr2019,
  author="Jakl, Tom{\'a}{\v{s}} and Jung, Achim and Pultr, Ale{\v{s}}",
  title="Quotients of d-Frames",
  journal="Applied Categorical Structures",
  year="2019",
  month="Jun",
  day="01",
  volume="27",
  number="3",
  pages="261--275",
  issn="1572-9095",
  doi="10.1007/s10485-018-09553-7"
}

Abstract

It is shown that every d-frame admits a complete lattice of quotients. Quotienting may be triggered by a binary relation on one of the two constituent frames, or by changes to the consistency or totality structure, but as these are linked by the reasonableness conditions of d-frames, the result in general will be that both frames are factored and both consistency and totality are increased.

d-Frames as algebraic duals of bitopological spaces, Charles University and University of Birmingham (Ph.D. thesis), 2018.

Free constructions and coproducts of d-frames (with Achim Jung), 7th Conference on Algebra and Coalgebra in Computer Science, Leibniz International Proceedings in Informatics, 2017.

BibTeX

@InProceedings{jakljung2017,
  author =    {Tom{\'a}{\v{s}} Jakl and Achim Jung},
  title =     {{Free Constructions and Coproducts of d-Frames}},
  booktitle = {7th Conference on Algebra and Coalgebra in Computer Science (CALCO 2017)},
  pages =     {14:1--14:15},
  series =    {Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =      {978-3-95977-033-0},
  ISSN =      {1868-8969},
  year =      {2017},
  volume =    {72},
  editor =    {Filippo Bonchi and Barbara K{\"o}nig},
  publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =   {Dagstuhl, Germany},
  doi =       {10.4230/LIPIcs.CALCO.2017.14},
  annote =    {Keywords: Free construction, d-frame, coproduct, C-ideals}
}

Abstract

A general theory of presentations for d-frames does not yet exist. We review the difficulties and give sufficient conditions for when they can be overcome. As an application we prove that the category of d-frames is closed under coproducts.

Bitopology and four-valued logic (with Achim Jung, Aleš Pultr), Proceedings of the 32nd Annual Conference on Mathematical Foundations of Programming Semantics (MFPS XXXII), Electronic Notes in Theoretical Computer Science, 2016.

BibTeX

@article{jakljungpultr2016,
  title = "Bitopology and Four-valued Logic",
  author = "Tom{\'a}{\v{s}} Jakl and Achim Jung and Ale{\v{s}} Pultr",
  journal = "Electronic Notes in Theoretical Computer Science",
  volume = "325",
  pages = "201 - 219",
  year = "2016",
  note = "The Thirty-second Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXII)",
  issn = "1571-0661",
  doi = "https://doi.org/10.1016/j.entcs.2016.09.039",
  keywords = "Bilattices, d-frames, nd-frames, bitopological spaces, four-valued logic"
}

Abstract

Bilattices and d-frames are two different kinds of structures with a four-valued interpretation. Whereas d-frames were introduced with their topological semantics in mind, the theory of bilattices has a closer connection with logic. We consider a common generalisation of both structures and show that this not only still has a clear bitopological semantics, but that it also preserves most of the original bilattice logic. Moreover, we also obtain a new bitopological interpretation for the connectives of four-valued logic.

Tightness relative to some (co)reflections in topology (with Richard N. Ball, Bernhard Banaschewski, Aleš Pultr, Joanne Walters-Waylande), Quaestiones Mathematicae, Volume 39 (3), 2016.

BibTeX

@article{bbjpw2016,
  author =  {Richard N. Ball and Bernhard Banaschewski and
             Tom{\'a}{\v{s}} Jakl and Ale{\v{s}} Pultr and
             Joanne Walters-Wayland},
  title =   {Tightness relative to some (co)reflections in topology},
  journal = {Quaestiones Mathematicae},
  volume =  {39},
  number =  {3},
  pages =   {421-436},
  year  =   {2016},
  publisher = {Taylor & Francis},
  doi =       {10.2989/16073606.2015.1073191}
}

Abstract

We address what might be termed the reverse reflection problem: given a monoreflection from a category A onto a subcategory B, when is a given object b ∈ B the reflection of a proper subobject? We start with a well known specific instance of this problem, namely the fact that a compact metric space is never the Čech-Stone compactification of a proper subspace. We show that this holds also in the pointfree setting, i.e., that a compact metrizable locale is never the Čech-Stone compactification of a proper sublocale. This is a stronger result than the classical one, but not because of an increase in scope; after all, assuming weak choice principles, every compact regular locale is the topology of a compact Hausdorff space. The increased strength derives from the conclusion, for in general a space has many more sublocales than subspaces. We then extend the analysis from metric locales to the broader class of perfectly normal locales, i.e., those whose frame of open sets consists entirely of cozero elements. We include a second proof of these results which is purely algebraic in character.

At the opposite extreme from these results, we show that an extremally disconnected locale is a compactification of each of its dense sublocales. Finally, we analyze the same phenomena, also in the pointfree setting, for the 0-dimensional compact reflection and for the Lindelöf reflection.

Other

Also see my Google Scholar, Semantic Scholar, ResearchGate, dblp, Github, and Genealogy profiles.

My ORCID is 0000-0003-1930-4904 and my MR Author ID is 1164669.

Web Analytics