Evènement pour le groupe Séminaire Méthodes Formelles

Date 2019-06-04  11:00-12:00
TitreLambdaY-calculus with priorities 
RésuméWe will start with another view on alternating automata over finite ranked trees. We will see an automaton as powerset algebra with a monotone operation for each letter of the alphabet. Every automaton determines a finite powerset algebra with operations, and every finite powerset algebra determines an automaton. The advantage of powerset algebras is that they can be easily made to interpret simply typed lambda terms, while it is not obvious how to run an automaton on a lambda-term. The correspondence between automata and finite powerset algebras shows that finite powerset algebras can recognize exactly the properties of simply-typed lambda-terms expressible by tree automata. The goal of this talk is to present a similar correspondence but for parity automata and simply-typed lambda-terms with fixpoints, known as lambdaY-terms. For this we need to restrict lambdaY-terms to lambdaY-terms with priorities. As a counterpart of finite powerset algebras we obtain not all parity automata but only visibly-parity automata. The talk will not assume a familiarity with the lambda-calculus. 
OrateurIgor Walukiewicz 

Aucun document lié à cet événement.

Retour à l'index