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.
Wordpress is loading infos from uni-bonnPlease wait for API server guteurls.de to collect data from
Ulrich, Monika and Olga attended Hausdorff Trimester Program Types, Sets and Constructions in Bonn, Germany. During this research trip they have participated in the Constructive Mathematics workshop and had a chance to collaborate with partners from the past and existing projects, including COMPUTAL, CONRCON and CID.
Irina and Markus attended SPIN symposium that took place in Malaga, Spain, where they gave a tutorial on Software Model Checking for Mobile Security.
The 23rd International Workshop on Algebraic Development Techniques (WADT 2016) took take place in Gregynog, Wales, from 21st to 24th September, 2016. The workshop was organised by Markus Roggenbach and Phil James.
The workshop “Continuity, Computability, Constructivity – From Logic to Algorithms” (CCC 2015) was held in Schloss Aspenstein, Kochel am See, near Munich, 14-18 September 2015.
This was the fourth and final workshop of the EU FP7 project ” COMPUTAL (Computable analysis – theoretical and applied aspects), a research network between Europe, Russia, South-Africa,and Japan.
The event was organised by Monika Seisenberger and colleagues from Swansea.
More information about the event including abstracts and links to previous CCC workshops can be found at http://www.cs.swan.ac.uk/ccc2015/