Category Archives: Event

2nd Proof Society Workshop on Proof Theory and its Applications

Following the Summer School, we are really proud to host the 2nd Proof Society Workshop. The workshop was an opportunity to listen to a lot of interesting invited and contributed talks on proof theory and various areas of its application:

Adam Wyner: Computational Law – The Case of Autonomous Vehicles
Yong Cheng: Exploring the incompleteness phenomenon
Matthias Baaz: Towards a Proof Theory for Henkin Quantifiers
Sonia Marin: On cut-elimination for non-wellfounded proofs: the case of PDL
Gilles Dowek: Logical frameworks, reverse mathematics, and formal proofs translation
Benjamin Ralph: What is a combinatorial proof system?
William Stirton: Ordinal assignments correlated with notions of reduction
Oliver Kullmann: Practical proof theory: practical versions of Extended Resolution
Anton Setzer and Ulrich Berger on behalf of Ralph Matthes: Martin Hofmann’s case for non-strictly positive data types – reloaded
Laura Crosilla: Philosophy of mathematics and proof theory
Takako Nemoto: Recursion Theory in Constructive Mathematics
Arno Pauly: Combinatorial principles equivalent to weak induction
Antonina Kolokolova: The proof complexity of reasoning over richer domains
Joost Joosten: The reduction property revisited
Helmut Schwichtenberg: Computational content of proofs

Thanks to all the speaker and participants and we hope to see you all again soon.

Proof Society Workshop 2019

Summer School: Day 4

Congratulations to Iris van der Giessen for winning the best poster competition and special thanks to Andreas Weiermann for the beautiful picture of Wales that serves as our main prize.

Big thanks to all the speakers and the participants for joining our Summer School. We hope to see you again during the future events by the Proof Society.

Proof Society Summer School 2019

Summer School: Day 2 and 3

We were glad to welcome Takako Nemoto, who joined us on the second day of the Summer School and gave her course on Reverse Mathematics.

As a treat, the participants of the Summer School had a trip to Rhossili and enjoyed a walk along the Welsh coastal path with stunning views. Big thanks to Arved Friedemann and Melissa Antonnelli for the beautiful photos.

Proof Society Summer School

We are very glad to welcome all the participants of the 2nd International Summer School on Proof Theory.

The first day began with a lecture on Universal Proof Theory by Rosalie Iemhoff, followed by Wolfram Pohlers‘ talk on Ordinal Analysis, Bounded Arithmetic lecture from our own Arnold Beckmann, introduction to Proof Mining by Paulo Oliva, Paola Bruscoli’s talk on Structural Proof Theory and Anton Setzer’s lecture on MLTT.

We were lucky with both the lovely weather and the fact that Bay Campus is located right at the seafront, so the evening brought a nice treat for everyone in a form of a BBQ at the beach. Big thanks to Arnold, Faron for their grilling and Ulrich, Rosalie, Monika, Arved, Aled, Anton, Olga and everyone else who helped with the organisation.



Faron BBQ

Erisa Karafili on forensic analysis of cyber-attacks

Today Erisa Karafili from the Imperial College London has given a talk on “Helping Forensic Analysts to Analyze and Attribute Cyber-Attacks” as a part of our Theory seminars.

Abstract: The frequency and harmfulness of cyber-attacks are increasing every day, and with them also the amount of data that the cyber-forensics analysts need to collect and analyze. Analyzing and discovering who performed an attack or from where it originated would permit to put in act targeted mitigative and preventive measures. In my talk, I will present two techniques that help the forensics analyst to analyze and attribute cyber-attacks. The first technique is a formal analysis process that allows an analyst to filter the enormous amount of evidence collected and either identify crucial information about the attack (e.g., when it occurred, its culprit, its target) or, at the very least, perform a pre-analysis to reduce the complexity of the problem in order to then draw conclusions more swiftly and efficiently. The second technique is a novel argumentation-based reasoner (ABR) for analyzing and attributing cyber-attacks that includes in its reasoning technical and social evidence.

Logic Minisymposium at Swansea University

Tomorrow we are holding our end-of-summer logic minisymposium.

Speakers:

  • Åsa Hirvonen
  • Ken-etsu Fujita
  • Masahiko Sato

Schedule: 

2:00 Åsa Hirvonen (Helsinki University): On continuous logic
2:40 Coffee & Cake
3:00 Ken-etsu Fujita (Gunma University): A constructive proof of the Church—Rosser theorem
3:50 Masahiko Sato (Kyoto University): Unification of the Lambda-Calcululs and Combinatory Logic

On continuous logic, Åsa Hirvonen (Helsinki University)

Continuous first order logic in its current form was developed at the beginning of this millennium to offer a language for the model theoretic study of metric structures, such as Banach spaces and probability spaces. It is a many-valued logic but has a different motivation and semantic than, e.g., Lukasiewicz logic. Many model theoretical properties of first order logic generalise to it, such as compactness and Löwenheim-Skolem theorems. This talk is a general introduction to the syntax and semantics as well as some basic properties of continuous logic.

A constructive proof of the Church—Rosser theorem, Ken-etsu Fujita (Gunma University)

My motivation behind this talk comes from a quantitative analysis of reduction systems based on the two viewpoints, computational cost and computational orbit.

In the first part, we show that an upper bound function for the Church—Rosser theorem of type-free lambda-calculus with beta-reduction must be in the fourth level of the Grzegorczyk hierarchy. That is, the number of reduction steps to arrive at a common reduct is bounded by a function in the smallest Grzegorczyk class properly extending that of elementary functions. At this level we also find common reducts for the confluence property. The proof method developed here can be applied not only to type-free lambda-calculus with beta-eta-reduction
but also to typed lambda-calculi such as Pure Types Systems.

In the second part, we propose a formal system of reduction paths for parallel reduction, wherein reduction paths are generated from a quiver by means of three path-operators, concatenation, monotonicity, and cofinality. Next, we introduce an equational theory and reduction rules for the reduction paths, and show that the rules on paths are terminating and confluent so that normal paths are obtained. Following the notion of normal paths, a graphical representation of reduction paths is provided, based on which unique path and universal common-reduct properties are established. Finally, transformation rules from a conversion sequence to a reduction path leading to the universal common-reduct are given, and path matrices are also defined as block matrices of adjacency matrices in order to count reduction orbits.

Unification of the Lambda-Calcululs and Combinatory Logic, Masahiko Sato (Kyoto University):

The Lambda calculus and combinatory logic have been studied as two closely related but distinct systems of logic and computation. In this talk, however, we will argue that they are in fact one and the same calculus.

We substantiate our argument by introducing what we will call the external syntax and the internal syntax for the two calculi. The external syntax will be given as a natural common extension of syntax for the \lambda-calculus and combinatory logic.

The terms defined by the internal syntax will be characterized as the closed alpha eta normal terms of the external syntax. Thus, the external syntax provides us with human readable syntax containing all the traditional \lambda-terms and combinatory-terms, and the internal syntax is suitable for the infrastructure of a proof assistant.

This is an ongoing joint work with Takafumi Sakurai and Helmut Schwichtenberg.

Founding the Foundry Lecture series welcome Prof. Moshe Vardi (Rice University)

Professor Moshe Vardi from Rice University, Texas, will give a talk on The Automated-Reasoning Revolution: From Theory to Practice and Back Wednesday 27th June, 12-1pm, Computational Foundry Seminar Room (Talbot 909).

Abstract: 
For the past 40 years computer scientists generally believed that NP-complete problems are intractable. In particular, Boolean satisfiability (SAT), as a paradigmatic automated-reasoning problem, has been considered to be intractable. Over the past 20 years, however, there has been a quiet, but dramatic, revolution, and very large SAT instances are now being solved routinely as part of software and hardware design. In this talk I will review this amazing development and show how automated reasoning is now an industrial reality.

I will then describe how we can leverage SAT solving to accomplish other automated-reasoning tasks.  Counting the number of satisfying truth assignments of a given Boolean formula or sampling such assignments uniformly at random are fundamental computational problems in computer science with applications in software testing, software synthesis, machine learning, personalized learning, and more.  While the theory of these problems has been thoroughly investigated since the 1980s, approximation algorithms developed by theoreticians do not scale up to industrial-sized instances.  Algorithms used by the industry offer better scalability, but give up certain correctness guarantees to achieve scalability. We describe a novel approach, based on universal hashing and Satisfiability Modulo Theory, that scales to formulas with hundreds of thousands of variables without giving up correctness guarantees.
 

Amir Tabatabai and Rahele Jalali visiting

Amir Tabatabai and Rahele Jalali, both PhD students at the Institute of Mathematics of the Czech Academy of Sciences under the supervision of Pavel Pudlak, are visiting Swansea University 13 Nov – 6 Dec 2017.

Amir will give a talk on Computational Flows in Arithmetic on 16 November.

More information: A computational flow is a pair consisting of a sequence of computational  problems of a certain sort and a sequence of computational reductions among
them. In this talk we will explain the basics of the theory of computational
flows and how they make a sound and complete interpretation for bounded
theories of arithmetic. This property helps us to decompose a first order
arithmetical proof to a sequence of computational reductions by which we can
extract the computational content of the low complexity statements in some
bounded theories of arithmetic such as  I\Delta_0, T^k_n, I\Delta_0 + EXP \text{ and } PRA.

Arno Pauly joining our department

Photo of Arno PaulyWe would like to welcome Arno Pauly, who has recently joined the computer science department here in Swansea. Today he is going to give a talk on Noncomputability in analysis as a part of our Computational Foundry Seminar Series.

More information: Many theorems in analysis state the existence of a certain object depending on some parameter. Each such theorem has an associated computational task: Compute the object from the parameter. From the viewpoint of a constructivist, these tasks are intricately linked to the meaningful truth of the theorems. From a pragmatic perspective, the applicability of a theorem to fields like physics or economics is tied to the solvability of the associated computational task.

Jan Peleska and Wen-ling Huang visiting

Jan Peleska and Wen-ling Huang from the University of Bremen are visiting Swansea this week. Jan will give a talk on Safety-complete Test Suites as a part of Computational Foundry Seminar series.

More information: This presentation is about property-oriented testing. A novel safety-related variant of complete test suites for finite state machines is introduced. Under certain hypotheses which are similar to the ones used in the well-known complete testing methods like W-Method, Wp-Method, HSI-Method, or H-Method, the new method guarantees to uncover every safety violation, while erroneous outputs without safety-relevance may remain undetected. In well-defined situations that can be precisely pre-determined from the reference model, this leads to a substantial reduction of test cases in comparison to the size of the analogous W, WP, HSI, H-test suites. We advocate this new test strategy for situations, where exhaustive testing of the complete system is too expensive. In these cases, strong guarantees with respect to fault coverage should only be given for the errors representing safety violations, while it is considered as acceptable if less critical errors remain undetected. An original version of this material has been published at the ICTSS 2017 conference; in this talk, we present a refined test suite based on the H-method which can be shown to always produce less or equally many test cases as when applying the original H-method. We sketch how this strategy can be extended to safety-complete equivalence class testing for systems with infinite input domains but finitely many internal states and finite output domains.