The Proof Theory Summer School will be followed by the Workshop on September 11-13, 2019. For more information click below:
Federico Cerutti from Cardiff University is visiting us this Thursday. He will give a talk on Probabilistic Logic Programming with Beta-Distributed Random Variables.
Abstract: We enable aProbLog—a probabilistic logical programming approach—to reason in presence of uncertain probabilities represented as Beta-distributed random variables. We achieve the same performance of state-of-the-art algorithms for highly specified and engineered domains, while simultaneously we maintain the flexibility offered by aProbLog in handling complex relational domains.
Our motivation is that faithfully capturing the distribution of probabilities is necessary to compute an expected utility for effective decision making under uncertainty: unfortunately, these probability distributions can be highly uncertain due to sparse data. To understand and accurately manipulate such probability distributions we need a well-defined theoretical framework that is provided by the Beta distribution, which specifies a distribution of probabilities representing all the possible values of a probability when the exact value is unknown.
Philipp Schlicht is visiting us today from Bristol. He’ll give us an introduction to automatic structures in the theory seminar today (2pm, CoFo 201).
Today Matthew Luckcuck (Liverpool) is visiting us today. He will give a talk on “Robotics and Integrated Formal Methods: Necessity meets Opportunity“.
Abstract: Robotic systems are multi-dimensional entities, combining both hardware and software, that are heavily dependent on, and influenced by, interactions with the real world. They can be variously categorised as embedded, cyberphysical, real-time, hybrid, adaptive and even autonomous systems, with a typical robotic system being likely to contain all of these aspects. The techniques for developing and verifying each of these system varieties are often quite distinct. This, together with the sheer complexity of robotic systems, leads us to argue that diverse formal techniques must be integrated in order to develop, verify, and provide certification evidence for, robotic systems. Furthermore, we propose the fast evolving field of robotics as an ideal catalyst for the advancement of integrated formal methods research, helping to drive the field in new and exciting directions and shedding light on the development of large-scale, dynamic, complex systems.
Hideki will give a talk on “Infinite Adequacy Theorem through Coinductive Definitions” today at 14:00 as a part of our Theory seminar series and Kristijonas will speak on “Argumentation-enabled Explainable AI Applications” this Thursday at 15:00 at the CoFo.
Today Martin Caminada (Cardiff University) is visiting Swansea. He will give a talk about “A Logical Account of Dishonesty” as a part of out Theory seminar series.
Abstract: Although formal logic is usually applied to reason about truth, in the current resentation we apply it to reason about dishonesty. Based on work in philosophy, we provide a formalisation of different forms of dishonesty, including lies, half-truth and bullshit, and discuss their formal properties. We also provide maxims for dishonest communication, that agents should ideally try to satisfy, both for moral and self-interested reasons.
As a part of our Theory Seminars, today we welcomed Ryota Akiyoshi from Waseda University, who gave a talk on Takeuti’s finitism.
Abstract: In this talk, we address several mathematical and philosophical issues of Gaisi Takeuti’s proof theory, who is one of the most distinguished logicians in proof theory after Hilbert and Gentzen. He furthered the realization of Hilbert’s program by formulating Gentzen’s sequent calculus for higher-oder logics, conjecturing that the cut-elimination holds for it (Takeuti’s conjecture), and obtaining several stunning results in the 1950-60’s towards the solution of his conjecture.
This talk consists of two parts. (1) To summarize Takeuti’s background and the argument of the well-ordering proof of ordinals up to ε0 , (2) To evaluate it on philosophical grounds. Also, we will explain several mathematical and philosophical issues to be solved. This is joint work with Andrew Arana.
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.
Tomorrow we are holding our end-of-summer logic minisymposium.
- Åsa Hirvonen
- Ken-etsu Fujita
- Masahiko Sato
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.