PhD Position F/M Algebraic structures in dependent types theory
Contract type : Fixed-term contract
Level of qualifications required : Graduate degree or equivalent
Fonction : PhD Position
About the research centre or Inria department
The Inria Rennes - Bretagne Atlantique Centre is one of Inria's eight centres and has more than thirty research teams. The Inria Center is a major and recognized player in the field of digital sciences. It is at the heart of a rich R&D and innovation ecosystem: highly innovative PMEs, large industrial groups, competitiveness clusters, research and higher education players, laboratories of excellence, technological research institute, etc.
Context
The PhD thesis witll be co-supervised by Assia Mahboubi (GALLINETTE) and Cyril Cohen (STAMP/CASH). It takes place in the frame of the FRESCO ERC project, conducted by Assia Mahboubi.
Assignment
The goal of this project consists in advancing the support for abstract algebra in proof assistants based on dependent type theory, such as Coq/Rocq, Agda or Lean. The main objective is to devise principled approaches to relate the different formal representations of a given structure, typically involving different variants of inductive types, with the relevant corresponding category. This study should enable automating the generation of the expected corresponding data and properties, improving this way the robustness and maintainability of libraries of formalized mathematics. Typical examples of expected applications include the generation of abstract syntax trees, of hierarchies of morphisms, of the construction of (co)limits, etc. By lack of relevant support, all these items are currently treated in a manual and ad hoc manner in state corpora of formalized mathematics, such as Coq/Rocq's Mathematical Components library or Lean's Mathlib ibrary.
Hierarchies of abstract mathematical structures are the cornerstone of modern libraries of formalized mathematics [2,4]. In type theory, mathematical structures are usually represented as telescopes, i.e., as dependent tuples (also called dependent records), which pack a carrier type with a signature and an equational theory. These telescopes provide an internal representation of interfaces for domains equipped with an algebraic structure, and hierarchies describe the existing inheritance and sharing relations between these abstractions.
Modern techniques for representing algebraic structures and for inferring instances thereof are used extensively in large corpora of formalized mathematics, so as to share notations and properties [2,4], or to provide representation independence principles [1]. Studying and exploiting the functorial structure of (co)datatype constructors [3] as well as syntactic relational models of type theory [5,6] have resulted in useful concrete tools, e.g., for automating proof transfer or for generating useful elimination schemes. But no such support exist as of today to turn basic category theory into effective automation for formalized abstract algebra, resulting in excessively bureaucratic formal developments. The main objective of the present project is thus to investigate this question.
[1] Carlo Angiuli, Evan Cavallo, Anders Mörtberg,Max Zeuner. Internalizing representation independence with univalence. Proc. ACM Program. Lang. 5(POPL): 1-30 (2021)
[2] Anne Baanen. “Use and Abuse of Instance Parameters in the Lean Mathematical Library”. Proc: ITP 2022: 4:1-4:20.
[3] Basil Fürer, Andreas Lochbihler, Joshua Schneider, Dmitriy Traytel. Quotients of Bounded Natural Functors. Log. Methods Comput. Sci. 18(1) (2022).
[4] Assia Mahboubi and Enrico Tassi. Mathematical Components. Zenodo, Jan. 2021.
[5] Nicolas Tabareau, Éric Tanter, and Matthieu Sozeau. “The Marriage of Univalence and Parametricity”. J. ACM 68.1 (2021), 5:1–5:44.
[6] Enrico Tassi. “Deriving Proved Equality Tests in Coq-Elpi: Stronger Induction Principles for Containers in Coq”. Proc. ITP 2019: 29:1-29:18
Main activities
The PhD student will contribute to the development of fundamental type theoretic and categorical methods, and will investigate their implementation in the Coq/Rocq proof assistant.
Skills
Working language : English or French.
We particularly welcome applications from underrepresented groups in mathematics and computer science.
Benefits package
- Subsidized meals
- Partial reimbursement of public transport costs
Remuneration
monthly gross salary amounting to 2100 euros
General Information
- Theme/Domain : Proofs and Verification
- Town/city : Nantes
- Inria Center : Centre Inria de l'Université de Rennes
- Starting date : 2024-10-01
- Duration of contract : 3 years
- Deadline to apply : 2024-06-25
Warning : you must enter your e-mail address in order to save your application to Inria. Applications must be submitted online on the Inria website. Processing of applications sent from other channels is not guaranteed.
Instruction to apply
Please submit online : your resume, cover letter and letters of recommendation eventually
For more information, please contact assia.mahboubi@inria.fr
Please note the working place is Nantes
Defence Security :
This position is likely to be situated in a restricted area (ZRR), as defined in Decree No. 2011-1425 relating to the protection of national scientific and technical potential (PPST).Authorisation to enter an area is granted by the director of the unit, following a favourable Ministerial decision, as defined in the decree of 3 July 2012 relating to the PPST. An unfavourable Ministerial decision in respect of a position situated in a ZRR would result in the cancellation of the appointment.
Recruitment Policy :
As part of its diversity policy, all Inria positions are accessible to people with disabilities.
Contacts
- Inria Team : GALLINETTE
-
PhD Supervisor :
Mahboubi Assia / Assia.Mahboubi@inria.fr
The keys to success
The candidate should have a strong background in theoretical computer science, including in particular either type theory or basic category theory. Previous experience with formal proofs in a type theory based proof assistant, e.g., Coq/Rocq, Agda or Lean appreciated.
About Inria
Inria is the French national research institute dedicated to digital science and technology. It employs 2,600 people. Its 200 agile project teams, generally run jointly with academic partners, include more than 3,500 scientists and engineers working to meet the challenges of digital technology, often at the interface with other disciplines. The Institute also employs numerous talents in over forty different professions. 900 research support staff contribute to the preparation and development of scientific and entrepreneurial projects that have a worldwide impact.