Publications

Pending

POSIX Lexing with Bitcoded Derivatives. (with Tan) Accepted at ITP'23. [pdf]

2023

POSIX Lexing with Derivatives of Regular Expressions. In Journal of Automated Reasoning, Springer Verlag. [pdf]

2018

Priority Inheritance Protocol Proved Correct. (with Zhang and Wu). In Journal of Automated Reasoning, Springer Verlag. [pdf]

The sources of the Isabelle/HOL code are now hosted at https://talisker.nms.kcl.ac.uk/cgi-bin/repos.cgi/pip/.

2017

Modelling Homogeneous Generative Meta-Programming (with Berger and Tratt) In Proceedings of the 31st European Conference on Object-Oriented Programming (ECOOP 2017). In Volume 74 of Leibniz International Proceedings in Informatics (LIPIcs). Pages 5:1-23. Schloss Dagstuhl-Leibniz-Zentrum, 2017. [pdf]

2016

POSIX Lexing with Derivatives of Regular Expressions (with Ausaf and Dyckhoff) In Proceedings of the 7th International Conference on Interactive Theorem Proving (ITP 2016). In Volume 9807 of Lecture Notes in Computer Science. Pages 69-86. Springer Verlag, 2016. [pdf]

2015

Proceedings of the 6th International Conference on Interactive Theorem Proving (with Zhang) Volume 9236 of LNCS, Springer Verlag, 2015.

2014

A Formalisation of the Myhill-Nerode Theorem based on Regular Expressions. (with Wu and Zhang) In Journal of Automatic Reasoning, 2014, Vol. 52(4), 451-480. [pdf]

(You should really use the linked version above, rather than the published version from Springer: somehow Springer managed to delete the rather important word ``finite'' from Theorem 5. They probably did not like our formatting and fooled around with our formulas. And we of course did not notice in the galley proofs.)

Revisiting Zucker's Work on the Correspondence Between Cut-Elimination and Normalisation. In Advances in Natural Deduction: A Celebration of Dag Prawitz's Work, Trends in Logic Series, Volume 39, 2014, Pages 31-50. Springer Verlag

2013

Mechanising Turing Machines and Computability Theory in Isabelle/HOL. (with Xu and Zhang) In Proceedings of the 4th Conference on Interactive Theorem Proving (ITP 2013). In Volume 7998 of Lecture Notes in Computer Science. Pages 147-162. © Springer Verlag [pdf]

(The phrase in the abstract is meant to say "we tie the knot ... ". This typo is corrected in the version above.)

A Formal Model and Correctness Proof for an Access Control Policy Framework. (with Wu and Zhang) In Proceedings of the 3rd Conference on Certified Programs and Proofs (CPP 2013). In Volume 8307 of Lecture Notes in Computer Science. Pages 292-307. © Springer Verlag [pdf]

2012

General Bindings and Alpha-Equivalence in Nominal Isabelle. (with Kaliszyk) Journal of Logical Methods in Computer Science, Volume 8 (2:14), 2012. 35 pages. [pdf]

Priority Inheritance Protocol Proved Correct. (with Zhang and Wu) In Proceedings of the 3rd Conference on Interactive Theorem Proving (ITP 2012). In Volume 7406 of Lecture Notes in Computer Science. Pages 217-232. © Springer Verlag [pdf]

(In the published version is a bogus sentence after the definition of detached and also a typo in the definition of schs. Both are corrected in the version above.)

2011

General Bindings and Alpha-Equivalence in Nominal Isabelle. (with Kaliszyk) In Proceedings of the 20th European Symposium on Programming (ESOP 2011). In Volume 6602 of Lecture Notes in Computer Science. Pages 480-500. © Springer Verlag [pdf]

A Formalisation of the Myhill-Nerode Theorem based on Regular Expressions (Proof Pearl). (with Wu and Zhang) In Proceedings of the 2nd Conference on Interactive Theorem Proving (ITP 2011). In Volume 6898 of Lecture Notes in Computer Science. Pages 341-356. © Springer Verlag [pdf]

Quotients Revisited for Isabelle/HOL. (with Kaliszyk) In Proceedings of the ACM Symposium on Applied Computing (SAC 2011), Software Verification and Testing track, Pages 1639-1644. [pdf]

(We silently assume in this paper to only lift from types that have covariant type-constructors. Many thanks to Ondřej Kunčar, who pointed this out. John Wickerson pointed out a typo in Definition 2 and one in the Appendix, which are corrected in the pdf-file above. Thanks!)

Mechanizing the Metatheory of Mini-XQuery. (with Cheney) In Proceedings of the 1st Conference on Certified Programs and Proofs (CPP 2011). In Volume 7086 of Lecture Notes in Computer Science. Pages 280-295. © Springer Verlag [pdf]

2010

Proof Pearl: A New Foundation for Nominal Isabelle. (with Huffman) In Proceedings of the 1st Conference on Interactive Theorem Proving (ITP 2010). In Volume 6172 of Lecture Notes in Computer Science. Pages 35-50. © Springer Verlag [pdf]

Mechanizing the Metatheory of LF. (with Cheney and Berghofer) In ACM Transactions on Computational Logic, Vol 12(2), Pages 15:1 - 15:42, 2011. [technical report]

Nominal Unification Revisited. (invited paper) In Proceedings of the 24th Workshop on Unification (UNIF 2010). In Volume 42 of Electronic Proceedings in Theoretical Computer Science. Pages 1-11, 2010. [pdf]

2009

Nominal Formalisations of Typical SOS Proofs. (with Narboux) In Proceedings of the 3rd Workshop on Logical and Semantic Frameworks with Applications (LFSA'08). Electronic Notes in Theoretical Computer Science, 247, Pages 139-155, 2009. [pdf].

Proceedings of Theorem Proving in Higher Order Logics (TPHOLs'09). (with Berghofer, Nipkow and Wenzel) Volume 5674 of Lecture Notes in Computer Science, 2009. © Springer Verlag

Nominal Verification of W. (with Nipkow) From Semantics to Computer Science, Essays in Honour of Gilles Kahn, edited by Bertot, Huet, Levy and Plotkin. Cambridge University Press, 2009. Pages 363-382. [pdf]

2008

Mechanizing the Metatheory of LF. (with Cheney and Berghofer) In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LICS 2008), IEEE Computer Society, June 2008. Pages 45-56. [pdf] More information is elsewhere.

Nominal Inversion Principles. (with Berghofer) In Proceedings of 21st International Conference on Theorem Proving in Higher Order Logics (TPHOLs'08). In Volume 5170 of Lecture Notes in Computer Science. Pages 71-85. © Springer Verlag [pdf]

(Note that the proof in figure 3 is chosen as an illustrative example to show how to use inversion principles (the main topic of the paper). If one does the induction on the beta-reduction relation, instead of the typing relation, then the proof is almost trivial and can be found automatically by Isabelle only using some very standard inversion principles for the typing relation.)

Mechanising a Proof of Craig's Interpolation Theorem for Intuitionistic Logic in Nominal Isabelle. (with Chapman and McKinna) In Proceedings of 9th International Conference on Artificial Intelligence and Symbolic Computation (AISC'08). In Volume 5144 of Lecture Notes in Artificial Intelligene. Pages 38-52. © Springer Verlag

Revisiting Cut-Elimination: One Difficult Proof is Really a Proof. (with Zhu) In Proceedings of the 19th International Conference on Rewriting Techniques and Applications (RTA 2008). In Volume 5117 of Lecture Notes in Computer Science. Pages 409-424. © Springer Verlag [pdf]

(This paper corrects some lemmas in my PhD-thesis. The errors were found by formalising the proof in Nominal Isabelle.)

How to Prove False using the Variable Convention. Appeared as a poster at TTVSI (Mike fest), 1 page. [pdf] [poster]

2007

Barendregt's Variable Convention in Rule Inductions. (with Berghofer and Norrish) In Proceedings of the 21th Conference on Automated Deduction (CADE 2007). In volume 4603 of Lecture Notes in Artificial Intelligence. Bremen, Germany. July 2007. Pages 35-50. © Springer Verlag [pdf] [ps]

This paper supersedes the MERLIN-paper from 2005.

Nominal Techniques in Isabelle/HOL. In Journal of Automatic Reasoning, 2008, Vol. 40(4), 327-356. [ps] [pdf]

Strong Induction Principles in the Locally Nameless Representation of Binders (Preliminary Notes). (with Pollack) A shorter version of this paper was accepted at WMM'07. [pdf]

Formalising in Nominal Isabelle Crary's Completeness Proof for Equivalence Checking. (with Narboux) In Proceedings of the International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2007). Electronic Notes in Theoretical Computer Science. Vol. 196. Pages 3-18. [pdf]

(There is a minor problem in the statement on page 4 where we write that alpha-renamings are required in order to show the equivalence of Q-Beta and Q-Beta': While the equivalence can be proved using alpha-renamings, it can also be proved by a careful analysis of the available freshness-constraints.)

Nominal Logic Programming. (with Cheney) In ACM Transactions on Programming Languages and Systems, 2008, Vol. 30(5), Pages 26:1-26:47.

2006

Proof Theory of Classical Propositional Calculus. (with Hyland, Bellin and Robinson) In Theoretical Computer Science 2006. Vol. 364(2). Pages 143-170. [ps]

A Recursion Combinator for Nominal Datatypes Implemented in Isabelle/HOL. (with Berghofer) In Proceedings of the 3rd International Joint Conference on Automated Deduction (IJCAR 2006). Seattle, USA. In volume 4130 of Lecture Notes in Artificial Intelligence. Pages 498-512. © Springer Verlag [ps]

Classical Logic is better than Intuitionistic Logic: A Conjecture about Double-Negation Translations. (with Ratiu) In Proceedings of the 1st International Workshop on Classical Logic and Computation (CL & C 2006). Venice, Italy. 20pp. [ps]

A Head-to-Head Comparison of de Bruijn Indices and Names. (with Berghofer) In Proceedings of the International Workshop on Logical Frameworks and Meta-Languages: Theory and Practice (LFMTP 2006). Electronic Notes in Theoretical Computer Science. Vol. 174(5). Pages 53-67. [ps]

2005

A Formal Treatment of the Barendregt Variable Convention in Rule Inductions. (with Norrish) In Proceedings of the ACM Workshop on Mechanized Reasoning about Languages with Variable Binding and Names (MERLIN 2005). Tallinn, Estonia. September 2005. Pages 25-32. © ACM, Inc. [ps] [pdf]

(There was a small typo in the definition of permutation equality, which has been corrected in the versions above. This paper received favourable comments on the FOM mailing-list.)

Nominal Techniques in Isabelle/HOL. (with Tasson) In Proceedings of the 20th Conference on Automated Deduction (CADE 2005). In volume 3632 of Lecture Notes in Artificial Intelligence. Tallinn, Estonia. July 2005. Pages 38-53. © Springer Verlag [ps]

(This paper is superseded by the journal version in 2007.)

Avoiding Equivariance in Alpha-Prolog. (with Cheney) In Proceedings of the 7th International Conference on Typed Lambda Calculi and Applications (TLCA 2005). In Volume 3461 of Lecture Notes in Computer Science. Nara, Japan. April 2005. Pages 401-416. © Springer Verlag [ps]

2004

Nominal Unification. (with Pitts and Gabbay) In Theoretical Computer Science 2004. Vol. 323(1-3). Pages 473-497. [ps] [pdf]

Nominal Techniques for Reasoning about Formal Languages. Reader for an advanced course at the ESSLLI summer school. 26 Pages. Appeared as LORIA technical report.

Alpha-Prolog: A Logic Programming Language with Names, Binding and Alpha-Equivalence. (with Cheney) In Proceedings of the International Conference on Logic Programming (ICLP 2004). In Volume 3132 of Lecture Notes in Computer Science. St-Malo, France. September 2004. Pages 269-283. © Springer Verlag [ps]

2003

Nominal Unification. (with Pitts and Gabbay) In Proceedings of the Computer Science Logic and 8th Kurt Gödel Colloquium (CSL & KGC 2003). In Volume 2803 of Lecture Notes in Computer Science. Vienna, Austria. August 2003. Pages 513-527. © Springer Verlag [ps]

System Description: Alpha-Prolog, a Fresh Approach to Logic Programming Modulo Alpha-Equivalence. (with Cheney) In Proceedings of the 17th International Workshop on Unification, UNIF'03. Valencia, Spain. June 2003. Technical Report DSIC-II/12/03, Departamento de Sistemas Informaticos y Computacion, Universidad Politecnica de Valencia, 2003. Pages 15-19. [ps]

Work in Progress: Logic Programming with Names and Binding. (with Cheney) CoLogNet Newsletter No. 4, 2003. Pages 25-28. [ps]

2002

Strong Normalisation of Herbelin's Explicit Substitution Calculus with Substitution Propagation. (with Dyckhoff) Journal of Logic and Computation, Volume 13, No 5, Pages 689-706. [pdf]

2001

Strong Normalisation of Cut-Elimination in Classical Logic. (with Bierman) Fundamenta Informaticae, 45(1-2), January 2001, Pages 123-155. [ps.gz] [pdf]

Strong Normalisation of Herbelin's Explicit Substitution Calculus with Substitution Propagation. (with Dyckhoff) In Proceedings of the 4th Workshop on Explicit Substitutions Theory and Applications (WESTAPP'01). Logic Group Preprint series No 210. Utrecht, the Netherlands. May 2001. Pages 26-45. [pdf]

Strong Normalisation for a Gentzen-like Cut-Elimination Procedure. In Proceedings of the 5th International Conference on Typed Lambda Calculi and Applications (TLCA 2001). In Volume 2044 of Lecture Notes in Computer Science. Krakow, Poland. May 2001. Pages 415-429. © Springer Verlag [ps.gz] [pdf]

2000

Classical Logic and Computation. Ph.D. Thesis, University of Cambridge. Supervised by Dr Gavin Bierman. October 2000. Some details are elsewhere. [ps.gz]

1999

Strong Normalisation of Cut-Elimination in Classical Logic. (with Bierman) In Proceedings of the 5th International Conference on Typed Lambda Calculi and Applications (TLCA 1999). In Volume 1581 of Lecture Notes in Computer Science. L'Aquila, Italy. April 1999. Pages 365-380. © Springer Verlag [ps.gz] [pdf]

1998

Implementation of Proof Search in the Imperative Programming Language Pizza. In Proceedings of the 7th International Conference on Automated Reasoning with Analytic Tableaux and Related Methods (TABELAUX 1998). In Volume 1397 of Lecture Notes in Artificial Intelligence. Oisterwijk, the Netherlands. May 1998. Pages 313-319. © Springer Verlag [ps.gz]

1996

Forum and Its Implementation. M.Phil. Thesis, University of St Andrews. Supervised by Dr Roy Dyckhoff. April 1996.