You are not logged in | Log in

Nominal Computation

Speaker(s)
Mikołaj Bojańczyk
Affiliation
Uniwersytet Warszawski
Date
May 11, 2011, 2:15 p.m.
Room
room 5870
Seminar
Seminar Automata Theory

I will present a programming language that manipulates nominal sets.
In the programming language, an orbit finite set behaves like a finite
set. One can execute in finite time a loop over all elements of an
orbit finite set, such as the rational numbers.

Using the programming language, one can write single piece of code,
which, when compiled by three different compilers, does the following
tasks:
1. test for emptiness an alternating automaton on finite words over a
finite alphabet.
2. test for emptiness a one-register alternating automaton on data
words, with data values compared for equality.
3. test for emptiness a one-register alternating automaton on data
words, with linearly ordered data values.