October 13 – 16, 2013, Dagstuhl Seminar 13422
Nominal Computation Theory
1 / 2 >
For support, please contact
Susanne Bach-Bernhard for administrative matters
Marc Herbstritt for scientific matters
The underlying theme of this seminar is nominal sets, also known as sets with atoms, or Fraenkel-Mostowski sets, or permutation models. The seminar arises from a recent exciting and unexpected confluence of the following three distinct research directions.
- Automata over infinite alphabets with applications to querying XML and databases.
- Program semantics using nominal sets, with many applications to the syntax and semantics of programming language constructs that involve binding, or localising names.
- Nominal calculi of concurrent processes (π-calculus, etc.), with applications to the automatic verification of process specifications.
The aim of the seminar is to profit from the excitement created by this confluence and to explore new directions with a new mix of research communities from computer science and mathematical logic. The central notion that underlies these new research directions is that of an orbit-finite set, a generalization and relaxation of the classical notion of finite set.
Such sets, although infinite, can be effectively represented and manipulated. For instance, alphabets and state spaces of register automata for data words, as well as values computed by programs that operate on nominal sets, are typically orbit-finite. This admits an effective realization of nominal computation.
The following gives a sample list of topics that will be of interest:
orbit-finite automata; computation theory in categories other than Set; applications to program verification; symmetry in domain theory; programming with orbit-finite sets; and computational complexity in the orbit-finite setting.
- Programming Languages / Compiler
- Semantics / Formal Methods
- Verification / Logic
- Nominal sets
- Automata theory