Course of Lectures on 'Collaborative Systems' Started

Max Kanovich, Professor of Computer Science, University College London and Andre Scedrov, Chair of the Mathematics Department, University of Pennsylvania deliver a course of lectures on 'Collaborative Systems' at the Faculty of Computer Science from December 16 to December 26.

The following topics will be analyzed during the course: 

1. Analysis of Network Security Protocols;
2. Kerberos Authentication Protocol;
3. Bounded Adversary;
4. Timed Collaborative Systems;
5. Resource reasoning in timed collaborative systems and program analysis;

• Basics, where the fundamental ideas of the resource logics (linear logic, separation logic) are presented in a semi-formal style.
• Foundations, where, for general resource models, on one hand, and for concrete heap-like models of practical interest, on the other hand, we get into the formalities, including the semantics of the assertion language and axioms and inference rules. Surprisingly, as for the assertion language of separation logic, even purely propositional separation logic turns out to be undecidable. What is more, whatever concrete heap-like model Hwe take, it is undecidable whether a purely propositional formula A is valid in this model H.
• Horn linear logic (a.k.a. multiset rewriting systems), where we research into the computational complexity of planning within real-time collaborative systems. A particular focus is on planning under uncertainty caused by actions with non-deterministic effects and/or quantitatively non-deterministic and continuous delayed effects.
• "New" logical principles for program analysis. Abduction, the problem of discovering hypotheses that support a conclusion, has mainly been studied in the context of philosophical logic and AI. Recently, the abduction principle — given A and B, find a non-trivial X such that A * X entails B, is one of the powerful practical tools for iterated deduction and hypothesis formation to `dig information out of bare code'. We study the complexity of abduction for a relevant fragment of separation logic over `symbolic heaps' which include a basic `points-to' predicate, and an inductive predicate for describing linked-list segments.

Schedule:

December 16, 16:40 – 18.00, 3 Kochnovsky Proezd, Room 300
December 22, 16:40 – 19:40, 3 Kochnovsky Proezd, Room 400
December 23, 16:40 – 18:00, 3 Kochnovsky Proezd, Room 400
December 25, 16:40 – 18:00, 3 Kochnovsky Proezd, Room 327
December 26, 18:10 – 19:30, 3 Kochnovsky Proezd, Room 327

The schedule is subject to change.