TCS and PAM seminar
We have a weekly informal seminar of the TCS group,
jointly with the
PAM-seminar from CWI,
often but not always on Fridays 15.30 - 16.30 at the VU.
Femke van Raamsdonk
(e: f.van.raamsdonk at vu.nl) if you wish to give a talk.
2018 12 04 (Tuesday)
room to be announced
Ahmed Bhayat (University of Manchester, UK)
Higher-order Unification via Combinators in Automated Theorem Proving
First-order representations of higher-order unification are attractive because they circumvent the complexity of bound variable renaming. Further, they are amenable to implementation within first-order provers. Dougherty has developed a complete higher-order unification algorithm that utilises combinators. However, it suffers from a couple of major problems. Firstly, it does not terminate even on trivial instances. Secondly, it produces numerous redundant unifiers. Here, a modification to Dougherty’s algorithm that is incomplete but terminating is presented. It has been implemented in Vampire and resulted in extra 114 problems being solved over first-order unification.
2018 11 27 (Tuesday)
Roy Overbeek (VU)
Master Thesis Presentation
Formalizing the Semantics of Concurrent Revisions
Concurrent revisions is a concurrency control model developed by Microsoft Research. It has many interesting properties that distinguish it from other well-known models such as transactional memory. One of these properties is determinacy: programs written within the model always produce the same outcome, independent of scheduling activity. The concurrent revisions model has an operational semantics, with an informal proof of determinacy. This thesis describes an Isabelle/HOL formalization of this semantics and the proof of determinacy. We identify a number of subtle ambiguities in the specification of the semantics, the resolution of which requires the semantics to be modified. We also work out many details of the proof of determinacy, and show that the proof can be simplified. While the uncovered issues do not appear to map to bugs in existing implementations, the formalization highlights some of the challenges that are involved in the general design and verification of concurrency control models.
for a list of previous seminars.
Last modified November 22, 2018.