October 13 – 16 , 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)

For support, please contact

Dagstuhl Service Team


Dagstuhl Report, Volume 3, Issue 10 Dagstuhl Report
Aims & Scope
List of Participants
Dagstuhl Seminar Schedule [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).

Summary text license
  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


In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.


Download overview leaflet (PDF).


Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.