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.

---