13. – 16. Oktober 2013, Dagstuhl-Seminar 13422

Nominal Computation Theory


Mikolaj Bojanczyk (University of Warsaw, PL)
Bartek Klin (University of Warsaw, PL)
Alexander Kurz (University of Leicester, GB)
Andrew M. Pitts (University of Cambridge, GB)

Auskunft zu diesem Dagstuhl-Seminar erteilt

Dagstuhl Service Team


Dagstuhl Report, Volume 3, Issue 10 Dagstuhl Report
Gemeinsame Dokumente
Programm des Dagstuhl-Seminars [pdf]


The short Dagstuhl seminar 13422 ``Nominal Computation Theory'' took place from October 13th to 16th, 2013. The topic of the seminar was the theory of nominal sets and their applications to Computer Science. The seminar arose from a recent exciting and unexpected confluence of the following three distinct research directions.

  • The research in automata theory on automata over infinite alphabets with applications to querying XML and databases.
  • The research in program semantics on nominal sets, with many applications to the syntax and semantics of programming language constructs that involve binding, or localising names.
  • The research in concurrency on nominal calculi ($\pi$-calculus, etc) with applications to the automatic verification of process specifications.

In each of these three topics, an important role is played by name (or atom) symmetries and permutations, albeit for a priori different reasons. In the first case they arise from the way automata use registers to store letters, in the second case they are used to define the notion freshness, in the third case they are needed to minimize automata. In all three cases there is a connection with mathematical model theory, which is aimed at studying classes of mathematical structures definable by logical theories. The permutations allowed on atomic names can be usefully understood as automorphisms of a relational structure on those names. Model-theoretic notions such as homogeneity, algebraic closure and oligomorphic groups turn out very useful in describing those relational structures on atoms that yield meaningful theories of nominal sets.

The aim of the seminar was to profit from the excitement created by the confluence described above and to explore new directions with a new mix of research communities from computer science and mathematical logic. The main topics of interest included: automata and complexity theory in nominal sets, verification of nominal automata, symmetry in domain theory,and nominal programming.

The seminar was attended by 30 participants from 8 countries; 19 of them gave presentations, whose abstracts are included in this document. Four of the presentations (A. Pitts, M. Bojanczyk, B. Klin and N. Tzevelekos) were extended tutorials that presented various points of view on the background topics of the meeting. Other speakers presented the current state of the art in the field, with topic varying from mathematical insights into the nature of nominal sets (A. Blass, D. Petrisan), to applications in automata theory (V. Ciancia, T. Colcombet, S. Lasota, T. Suzuki) and computation theory (A. Dawar, S. Torunczyk), semantics and domain theory (R. Crole, J. Gabbay, S. Loesch, A. Murawski), Petri nets (R. Lazic), logic programming (J. Cheney) and theorem proving (C. Urban).

  Creative Commons BY 3.0 Unported license
  Mikolaj Bojanczyk, Bartek Klin, Alexander Kurz, and Andrew M. Pitts


  • Programming Languages / Compiler
  • Semantics / Formal Methods
  • Verification / Logic


  • Nominal sets
  • Automata theory
  • HD-automata
  • Orbit-finiteness


Bücher der Teilnehmer 

Buchausstellung im Erdgeschoss der Bibliothek

(nur in der Veranstaltungswoche).


In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.


Download Übersichtsflyer (PDF).


Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.