The Psyche prover

Dr Stéphane Graham-Lengrand

Chargé de Recherche au CNRS

Laboratoire d'Informatique de l'X

Current work

[GL13]	S. Graham-Lengrand. Psyche: a proof-search engine based on sequent calculus with an LCF-style architecture. April 2013. Submitted. [ bib ] [pdf]
[BGL13]	A. Bernadet and S. Graham-Lengrand. A big-step operational semantics via non-idempotent intersection types. April 2013. Submitted. [ bib ] [pdf]
[FGLM13]	M. Farooque, S. Graham-Lengrand, and A. Mahboubi. DPLL(T) as a tableau method. April 2013. Submitted. [ bib ] [pdf], with typos corrected
[BL12b]	A. Bernadet and S. Lengrand. A simple presentation of the effective topos. April 2012. Submitted. [ bib ] [pdf]
[BL12a]	A. Bernadet and S. Lengrand. Non-idempotent intersection types and strong normalisation. February 2012. Submitted. [ bib ] [pdf] (Subsumes Complexity of strongly normalising $\lambda$-terms via non-idempotent intersection types and Filter models: non-idempotent intersection types, orthogonality and polymorphism)

Journal papers (published or accepted)

[LDM11]	S. Lengrand, R. Dyckhoff, and J. McKinna. A focused sequent calculus framework for proof search in Pure Type Systems. Logical Methods in Computer Science, 7(1), 2011. [ bib ] [pdf] (Subsumes A sequent calculus for Type Theory)
[GL09]	M. Gabbay and S. Lengrand. The λ-context calculus. Information and Computation, 207(12):1369-1400, 2009. [ bib ] (Subsumes The lambda-context calculus)
[LM08]	S. Lengrand and A. Miquel. Classical F_ω, orthogonality and symmetric candidates. Annals of Pure and Applied Logic, 153:3-20, 2008. [ bib ] [pdf] (Subsumes A classical version of Fomega)
[DL07]	R. Dyckhoff and S. Lengrand. Call-by-value λ-calculus and LJQ. Journal of Logic and Computation, 17:1109-1134, 2007. [ bib ] [pdf] The proof of strong normalisation of LJQ: [pdf] (updated in December 2007)
[KL07]	D. Kesner and S. Lengrand. Resource operators for the λ-calculus. Information and Computation, 205:419-473, 2007. [ bib ] [pdf] (Subsumes Extending the Explicit Substitution Paradigm)
[LLD⁺04]	S. Lengrand, P. Lescanne, D. Dougherty, M. Dezani-Ciancaglini, and S. van Bakel. Intersection types for explicit substitutions. Information and Computation, 189(1):17-42, 2004. [ bib ] [pdf] (Subsumes An improved system of intersection types for explicit substitutions)

Reviewed Conference and Workshop papers (published or accepted)

[BL11b]	A. Bernadet and S. Lengrand. Filter models: non-idempotent intersection types, orthogonality and polymorphism. In M. Bezem, editor, Proceedings of the 20th Annual Conference of the European Association for Computer Science Logic (CSL'11), Leibniz International Proceedings in Informatics. Schloss Dagstuhl Leibniz Center for Informatics, September 2011. [ bib ] [pdf]
[BL11a]	A. Bernadet and S. Lengrand. Complexity of strongly normalising λ-terms via non-idempotent intersection types. In M. Hofmann, editor, Proceedings of the 14th International Conference on Foundations of Software Science and Computation Structures (FOSSACS'11), volume 6604 of Lecture Notes in Computer Science. Springer-Verlag, March 2011. [ bib ] [pdf]
[KL08]	K. Kikuchi and S. Lengrand. Strong normalisation of cut-elimination that simulates β-reduction. In R. Amadio, editor, Proceedings of the 11th International Conference on Foundations of Software Science and Computation Structures (FOSSACS'08), volume 4962 of Lecture Notes in Computer Science, pages 380-394. Springer-Verlag, March 2008. [ bib ] [pdf] Long version: [pdf]
[GL08]	M. Gabbay and S. Lengrand. The lambda-context calculus. volume 196 of Electronic Notes in Theoretical Computer Science, pages 19-35, 2008. Revision from the Second International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2007) (was A(nother) NEW Calculus of Contexts). [ bib ] [pdf] (Subsumed by The lambda-context Calculus)
[LDM06]	S. Lengrand, R. Dyckhoff, and J. McKinna. A sequent calculus for type theory. In Z. Esik, editor, Proceedings of the 15th Annual Conference of the European Association for Computer Science Logic (CSL'06), volume 4207 of Lecture Notes in Computer Science, pages 441-455. Springer-Verlag, September 2006. [ bib ] [pdf] (Subsumed by A Focused Sequent Calculus Framework for Proof Search in Pure Type Systems)
[DKL06]	R. Dyckhoff, D. Kesner, and S. Lengrand. Strong cut-elimination systems for Hudelmaier's depth-bounded sequent calculus for implicational logic. In U. Furbach and N. Shankar, editors, Proceedings of the 3rd International Joint Conference on Automated Reasoning (IJCAR'06), volume 4130 of Lecture Notes in Artificial Intelligence, pages 347-361. Springer-Verlag, August 2006. [ bib ] [pdf] Long version: [pdf]
[DL06]	R. Dyckhoff and S. Lengrand. LJQ, a strongly focused calculus for intuitionistic logic. In A. Beckmann, U. Berger, B. Loewe, and J. V. Tucker, editors, Proceedings of the 2nd Conference on Computability in Europe (CiE'06), volume 3988 of Lecture Notes in Computer Science, pages 173-185. Springer-Verlag, July 2006. [ bib ] [pdf] The proof of strong normalisation of LJQ: [pdf] (updated in December 2007)
[LM06]	S. Lengrand and A. Miquel. A classical version of F_ω. In S. van Bakel and S. Berardi, editors, 1st Workshop on Classical logic and Computation, July 2006. [ bib ] [pdf] (Subsumed by Classical Fomega, orthogonality and symmetric candidates)
[BL05]	K. Brünnler and S. Lengrand. On two forms of bureaucracy in derivations. In F. L. Paola Bruscoli and J. Stewart, editors, 1st Workshop on Structures and Deductions (SD'05), Technical Report, Technische Universität Dresden, pages 69-80, July 2005. ISSN 1430-211X. [ bib ] [pdf] Slides [postscript]
[KL05]	D. Kesner and S. Lengrand. Extending the explicit substitution paradigm. In J. Giesl, editor, Proceedings of the 16th International Conference on Rewriting Techniques and Applications(RTA'05), volume 3467 of Lecture Notes in Computer Science, pages 407-422. Springer-Verlag, April 2005. [ bib ] [postscript] (Best paper award RTA 2005) (Subsumed by Resource operators for the lambda-calculus)
[Len04]	S. Lengrand. Deriving strong normalisation. In D. Kesner, F. van Raamsdonk, and J. Wells, editors, 2nd International Workshop on Higher-Order Rewriting (HOR'04), Technical Report AIB-2004-03, RWTH Aachen, pages 84-88, June 2004. [ bib ] [postscript] (Subsumed by Induction principles as the foundation of the theory of normalisation: concepts and techniques)
[Len03]	S. Lengrand. Call-by-value, call-by-name, and strong normalization for the classical sequent calculus. volume 86(4) of Electronic Notes in Theoretical Computer Science. Elsevier, 2003. Revision from the 3rd International Workshop on Reduction Strategies in Rewriting and Programming (WRS'03). [ bib ] [postscript] Slides: [postscript] Erratum: [postscript]
[DLL02]	D. J. Dougherty, S. Lengrand, and P. Lescanne. An improved system of intersection types for explicit substitutions. In R. A. Baeza-Yates, U. Montanari, and N. Santoro, editors, Proceedings of the IFIP 17th World Computer Congress - TC1 Stream / 2nd IFIP International Conference on Theoretical Computer Science (TCS'02), volume 223 of IFIP Conference Proceedings, pages 511-523. Kluwer, August 2002. [ bib ] [postscript] (Subsumed by Intersection types for explicit substitutions)

Dissertations and Reports

[FGL13]	M. Farooque and S. Graham-Lengrand. Sequent calculi with procedure calls. Technical report, Laboratoire d'informatique de l'école polytechnique - LIX , PARSIFAL - INRIA Saclay - Ile de France, January 2013 [ bib \| http ]
[FLM12a]	M. Farooque, S. Lengrand, and A. Mahboubi. Simulating the DPLL(T) procedure in a sequent calculus with focusing. Technical report, Laboratoire d'informatique de l'école polytechnique - LIX , PARSIFAL - INRIA Saclay - Ile de France, TypiCal - INRIA Saclay - Ile de France, March 2012 [ bib \| http ]
[FLM12b]	M. Farooque, S. Lengrand, and A. Mahboubi. Two simulations about DPLL(T). Technical report, Laboratoire d'informatique de l'école polytechnique - LIX , PARSIFAL - INRIA Saclay - Ile de France , Microsoft Research - Inria Joint Centre - MSR - INRIA , TypiCal - INRIA Saclay - Ile de France, March 2012 [ bib \| http ]
[FL11]	M. Farooque and S. Lengrand. A sequent calculus with procedure calls. Technical report, Laboratoire d'informatique de l'école polytechnique - LIX , PARSIFAL - INRIA Saclay - Ile de France, December 2011 [ bib \| http ]
[BL11]	A. Bernadet and S. Lengrand. Filter models: non-idempotent intersection types, orthogonality and polymorphism - long version. Technical report, LIX, CNRS-INRIA-Ecole Polytechnique, June 2011 [ bib \| http ]
[Len08]	S. Lengrand. Termination of lambda-calculus with the extra call-by-value rule known as assoc. Technical report, LIX, CNRS-INRIA-Ecole Polytechnique, January 2008 [ bib \| http ]
[Len06]	S. Lengrand. Normalisation & Equivalence in Proof Theory & Type Theory. PhD thesis, Université Paris 7 & University of St Andrews, 2006. [ bib ] Supervised by Pr. Delia KESNER & Dr Roy DYCKHOFF. Publicly defended on 8th December 2006 before Dr Pierre-Louis CURIEN, Chairman Dr James McKINNA, Internal examiner of St Andrews Pr. Gilles DOWEK, Referee (rapporteur) for Paris VII Pr. Luke ONG, Referee (rapporteur) for St Andrews Pr. Henk BARENDREGT, Examiner Pr. Dale MILLER, Examiner & my supervisors. For this thesis I was one of the three recipients of the 2007 Ackermann Award, the EACSL Outstanding Dissertation Award for Logic in Computer Science, presented at the conference CSL'2007 in Lausanne. [The dissertation (pdf) 2522 Kb] [with a synopsis in French (pdf) 2609 Kb] Abstract (In French)
[Len05]	S. Lengrand. Induction principles as the foundation of the theory of normalisation: Concepts and techniques. Technical report, PPS laboratory, Université Paris 7, March 2005 [ bib \| http ]