Doctorant F/H Certification of automated theorem provers for higher-order logic (F/M)
Type de contrat : CDD
Niveau de diplôme exigé : Bac + 5 ou équivalent
Fonction : Doctorant
A propos du centre ou de la direction fonctionnelle
The Inria Saclay-Île-de-France Research Centre was established in 2008. It has developed as part of the Saclay site in partnership with Paris-Saclay University and with the Institut Polytechnique de Paris .
The centre has 39 project teams , 27 of which operate jointly with Paris-Saclay University and the Institut Polytechnique de Paris; Its activities occupy over 600 people, scientists and research and innovation support staff, including 44 different nationalities.
Contexte et atouts du poste
Automated theorem provers (ATPs) are tools that attempt to fully automatically prove a given conjecture from a set of assumptions. Such systems are based on a logic in which the reasoning problems are formulated using a machine readable input syntax. A calculus for said logic then provides the deduction rules that are implemented to form inferences from the assumptions. The step by step derivation of the conjecture from the assumptions through the application of the inference rules then represents a proof produced by such systems.
ATPs have a wide and extending field of applications, including software and hardware verification, mathematics, philosophy and artificial intelligence. It is thus important to be able to trust that any statement provable with a given system is indeed a logical consequence of the provided assumptions, a property known as soundness. The generated proofs can be lengthy and the reasoning usually does not follow human intuition, which can make the correctness of proofs hard to check for human readers. In practice, established provers have nevertheless gained the trust of the community by consistently performing reliably over long term usage and in numerous applications and tests. Such empirical verification is however not sufficient to ensure that the results of the systems will always be trustworthy. This is where formal verification comes into play. There are different possible techniques to warrant the correctness of the produced proofs: One might for instance look at the provers themselves and verify their implementation. The complexity of this task however makes checking individual proofs an attractive alternative. To this end, a trace containing details about all of the steps taken in the individual proofs produced by ATPs can be used to check the inferences and thereby verify the correctness.
Mission confiée
The aim of the thesis will be the development of a tool that verifies Leo-III proofs using the Dedukti framework. More specifically, the reasoning that takes place after the transformation of the formulas to CNF will be the focus here since the transformation of formulas containing existential quantification involves skolemization. While this preserves satisfiability, which is sufficient for the purpose of deriving the empty clause from the negated conjecture and thus showing provability, equivalence is not maintained. The use of the other inference rules can however be verified when both the applied inference rules and the steps of the proof are encoded in LambdaPi Syntax. If necessary, the output produced by Leo-III will be extended if additional information will be needed for the translation of the proof certificate. This approach might however be limited to proofs that Leo-III did not cooperate with external system for since such cooperations can cause gaps in proofs. The first step will be the successful implementation of the translation-tool for only a subset of the inference rules and for monomorphic HOL. This will then be extend later on, if time will permit it.
Principales activités
Compétences
Familiarity with logic and functional programming.
Avantages
- Subsidized meals
- Partial reimbursement of public transport costs
- Leave: 7 weeks of annual leave + 10 extra days off due to RTT (statutory reduction in working hours) + possibility of exceptional leave (sick children, moving home, etc.)
- Possibility of teleworking (after 6 months of employment) and flexible organization of working hours
- Professional equipment available (videoconferencing, loan of computer equipment, etc.)
- Social, cultural and sports events and activities
- Access to vocational training
- Social security coverage
Rémunération
Gross salary 2.100 euros/mois
Informations générales
- Thème/Domaine :
Preuves et vérification
Calcul Scientifique (BAP E) - Ville : GIF SUR YVETTE
- Centre Inria : Centre Inria de Saclay
- Date de prise de fonction souhaitée : 2024-10-01
- Durée de contrat : 3 ans
- Date limite pour postuler : 2024-09-30
Attention: Les candidatures doivent être déposées en ligne sur le site Inria. Le traitement des candidatures adressées par d'autres canaux n'est pas garanti.
Consignes pour postuler
Sécurité défense :
Ce poste est susceptible d’être affecté dans une zone à régime restrictif (ZRR), telle que définie dans le décret n°2011-1425 relatif à la protection du potentiel scientifique et technique de la nation (PPST). L’autorisation d’accès à une zone est délivrée par le chef d’établissement, après avis ministériel favorable, tel que défini dans l’arrêté du 03 juillet 2012, relatif à la PPST. Un avis ministériel défavorable pour un poste affecté dans une ZRR aurait pour conséquence l’annulation du recrutement.
Politique de recrutement :
Dans le cadre de sa politique diversité, tous les postes Inria sont accessibles aux personnes en situation de handicap.
Contacts
- Équipe Inria : DEDUCTEAM
-
Directeur de thèse :
Blanqui Frederic / Frederic.Blanqui@inria.fr
A propos d'Inria
Inria est l’institut national de recherche dédié aux sciences et technologies du numérique. Il emploie 2600 personnes. Ses 215 équipes-projets agiles, en général communes avec des partenaires académiques, impliquent plus de 3900 scientifiques pour relever les défis du numérique, souvent à l’interface d’autres disciplines. L’institut fait appel à de nombreux talents dans plus d’une quarantaine de métiers différents. 900 personnels d’appui à la recherche et à l’innovation contribuent à faire émerger et grandir des projets scientifiques ou entrepreneuriaux qui impactent le monde. Inria travaille avec de nombreuses entreprises et a accompagné la création de plus de 200 start-up. L'institut s'efforce ainsi de répondre aux enjeux de la transformation numérique de la science, de la société et de l'économie.