Moerman, Joshua;
Rot, Jurriaan;
(2020)
Separation and Renaming in Nominal Sets.
In: Fernández, Maribel and Muscholl, Anca, (eds.)
28th EACSL Annual Conference on Computer Science Logic.
(pp. 31:1-31:17).
Dagstuhl Publishing: Wadern, Germany.
Preview |
Text
LIPIcs-CSL-2020-31.pdf - Published Version Download (527kB) | Preview |
Abstract
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.
| Type: | Proceedings paper |
|---|---|
| Title: | Separation and Renaming in Nominal Sets |
| Event: | CSL 2020, January 13–16, 2020, Barcelona, Spain |
| ISBN-13: | 9783959771320 |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.4230/LIPIcs.CSL.2020.31 |
| Publisher version: | https://doi.org/10.4230/LIPIcs.CSL.2020.31 |
| Language: | English |
| Additional information: | This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC-BY 3.0): https://creativecommons.org/licenses/by/3.0 |
| Keywords: | Nominal sets, Separated product, Adjunction, Automata, Coalgebra |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Engineering Science > Dept of Computer Science |
| URI: | https://discovery-pp.ucl.ac.uk/id/eprint/10092769 |
Archive Staff Only
 |
View Item |
