http://www.dagstuhl.de/13422

# Nominal Computation Theory

## Organizers

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)

1 / 2 >

## Summary

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 and Bartek Klin and Alexander Kurz and Andrew M. Pitts

## Classification

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

## Keywords

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

## Book exhibition

Book exhibition in the library, 1st floor, during the seminar week.

## Documentation

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.