License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2020.31
URN: urn:nbn:de:0030-drops-116744
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11674/
Go to the corresponding LIPIcs Volume Portal

Moerman, Joshua ; Rot, Jurriaan

Separation and Renaming in Nominal Sets

pdf-format:
LIPIcs-CSL-2020-31.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{moerman_et_al:LIPIcs:2020:11674,
  author =	{Joshua Moerman and Jurriaan Rot},
  title =	{{Separation and Renaming in Nominal Sets}},
  booktitle =	{28th EACSL Annual Conference on Computer Science Logic (CSL 2020)},
  pages =	{31:1--31:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-132-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{152},
  editor =	{Maribel Fern{\'a}ndez and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11674},
  URN =		{urn:nbn:de:0030-drops-116744},
  doi =		{10.4230/LIPIcs.CSL.2020.31},
  annote =	{Keywords: Nominal sets, Separated product, Adjunction, Automata, Coalgebra}
}

Keywords: Nominal sets, Separated product, Adjunction, Automata, Coalgebra
Collection: 28th EACSL Annual Conference on Computer Science Logic (CSL 2020)
Issue Date: 2020
Date of publication: 06.01.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI