Paper at CSL 2020

The paper entitled “Separation and Renaming in Nominal Sets” by Joshua Moerman and Jurriaan Rot (UCL, London and Radboud University, the Netherlands) has been accepted for the 28th edition in the series of Computer Science Logic (CSL 2020).

Nominal sets provide a foundation for reasoning about names. They are used primarily in syntax with binders, but also, e.g., to model automata over infinite alphabets. In this paper, nominal sets are related to nominal renaming sets, which involve arbitrary substitutions rather than permutations, through a categorical adjunction. In particular, the left adjoint relates the separated product of nominal sets to the Cartesian product of nominal renaming sets. Based on these results, we define the new notion of separated nominal automata. We show that these automata can be exponentially smaller than classical nominal automata, if the semantics is closed under substitutions.