2026-07-28T19:07:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11674 2024-03-06T10:48:45Z ddc:004 open_access

Separation and Renaming in Nominal Sets Moerman, Joshua Rot, Jurriaan Nominal sets Separated product Adjunction Automata Coalgebra 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Joshua Moerman and Jurriaan Rot 2020 Is Part Of LIPIcs, Volume 152, 28th EACSL Annual Conference on Computer Science Logic (CSL 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2020.31 urn:nbn:de:0030-drops-116744 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2020.31 eng https://creativecommons.org/licenses/by/3.0/legalcode