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 talk, nominal sets are related to nominal renaming sets, which involve arbitrary substitutions rather than permutations, through a categorical adjunction. Based on these results, we introduce the notion of separated nominal automaton. These automata can be exponentially smaller than classical nominal automata, if the semantics is closed under substitutions.
Joint work with Joshua Moerman (RWTH Aachen).