Faites connaître cette offre !
Reference : UMR7351-MAIGEH-002
Workplace : NICE
Date of publication : Tuesday, June 16, 2020
Scientific Responsible name : Gehrke, Mai
Type of Contract : PhD Student contract / Thesis offer
Contract Period : 36 months
Start date of the thesis : 1 September 2020
Proportion of work : Full time
Remuneration : 2 135,00 € gross monthly
Description of the thesis topic
Dualities between algebraic and topological structures are omnipresent in mathematics and theoretical computer science and have often been associated with major breakthroughs. The main objective of the DuaLL project is the application of these topo-algebraic dualities to a certain number of theoretical computer science subjects, thus making them progress, while systematizing and unifying them. The successful candidate will conduct research with the goal of writing a doctoral thesis within this project.
The proposed subject aims more particularly at the duality for the categorical semantics of logic and its application in finite model theory and/or in descriptive complexity theory.
The categorical semantics of logic takes its point of departure in the 1970s with the work of Lawvere and Tierney. The central structure is that of a topos which comes from the work of the Grothendieck school in algebraic geometry. This notion encodes the algebraic point of view of logic, but a more geometric point of view, in closer connection with the models of logic in question, is at least as important and is obtained by duality. Consequently, the duality for these structures has been studied from the start, notably in Makkai's work on the "Topos of Types", and is still a very studied subject today, see for example [Lurie].
We want to study these general and abstract tools in the much more concrete context of computational models in theoretical computer science such as automata, and more generally, finite models. Recent work shows that the tools of semantics and duality in logic provide useful methods targeting questions of algorithmic complexity, see for example [GGP08,Geh16,Mell17,AbSh18].
[Lurie] J. Lurie. Ultracategories. See https://www.math.ias.edu/~lurie/papers/Conceptual.pdf
[GGP08] M. Gehrke, S. Grigorieff, and J.-E. Pin. Duality and equational theory of regular languages. In ICALP'08, 246-257, 2008.
[Geh16] M. Gehrke. Stone duality, topological algebra, and recognition, Journal of Pure and Applied Algebra, Volume 220, Issue 7, July 2016, 2711–2747
[Mel17] Paul-André Melliès. Higher-order parity automata. Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017, Reykjavik, Iceland, 2017.
[AbSh18]. S. Abramsky, N. Shah. Relating Structure and Power: Comonadic Semantics for Computational Resources. CSL 2018: 2:1-2:17.
The successful candidate must have an excellent level in mathematics (a Master degree in mathematics or the equivalent is required before the start of the thesis), and preference is given to students with an in-depth course in category theory and knowledge of mathematical logic.
The J. A. Dieudonné Laboratory, Parc Valrose, Nice is a Joint Research Unit - UMR N ° 7351 - dependent on the National Center for Scientific Research (CNRS) and the University of the Côte d'Azur (UCA). It includes 135 researchers and teacher-researchers, 13 administrative staff and research assistance engineers and 60 doctoral and post-doctoral students. The laboratory is structured around 6 teams, including the ATG team (Algebra, Topology and Geometry). The ERC DuaLL project team is part of ATG.
The PhD candidate will be part of the DuaLL project team, see Duality in Formal Languages and Logic – a unifying approach to complexity and semantics, https://math.unice.fr/~mgehrke/DuaLL.htm
We talk about it on Twitter!