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. |