Separation and Renaming in Nominal Sets

Joshua Moerman, Jurriaan Rot

Research output: Chapter in Book/Report/Conference proceedingConference Article in proceedingAcademicpeer-review


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.
Original languageEnglish
Title of host publicationCSL
Subtitle of host publication28th EACSL Annual Conference on Computer Science Logic
EditorsMaribel Fernandez, Anca Muscholl
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Number of pages17
ISBN (Print)978-3-95977-132-0
Publication statusPublished - Jan 2020
Externally publishedYes
Event28th EACSL Annual Conference on Computer Science Logic - Barcelona, Spain
Duration: 13 Jan 202016 Jan 2020
Conference number: 28


Conference28th EACSL Annual Conference on Computer Science Logic
Abbreviated titleCSL 2020
Internet address


  • Adjunction
  • Automata
  • Coalgebra
  • Nominal sets
  • Separated product


Dive into the research topics of 'Separation and Renaming in Nominal Sets'. Together they form a unique fingerprint.

Cite this