Supported Sets – A New Foundation for Nominal Sets and Automata

Wißmann T (2023)

Publication Type: Conference contribution

Publication year: 2023

Journal

LIPIcs : Leibniz International Proceedings in Informatics Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik

Publisher: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

Book Volume: 252

Conference Proceedings Title: Leibniz International Proceedings in Informatics, LIPIcs

Event location: Warsaw PL

ISBN: 9783959772648

DOI: 10.4230/LIPIcs.CSL.2023.38

Abstract

The present work proposes and discusses the category of supported sets which provides a uniform foundation for nominal sets of various kinds, such as those for equality symmetry, for the order symmetry, and renaming sets. We show that all these differently flavoured categories of nominal sets are monadic over supported sets. Thus, supported sets provide a canonical finite way to represent nominal sets and the automata therein, e.g. register automata and coalgebras in general. Name binding in supported sets is modelled by a functor following the idea of de Bruijn indices. This functor lifts to the well-known abstraction functor in nominal sets. Together with the monadicity result, this gives rise to a transformation process from finite coalgebras in supported sets to orbit-finite coalgebras in nominal sets. One instance of this process transforms the finite representation of a register automaton in supported sets into its configuration automaton in nominal sets.

Authors with CRIS profile

Thorsten Wißmann

Involved external institutions

Radboud University Nijmegen NL Netherlands (NL)

How to cite

APA:

Wißmann, T. (2023). Supported Sets – A New Foundation for Nominal Sets and Automata. In Bartek Klin, Elaine Pimentel (Eds.), Leibniz International Proceedings in Informatics, LIPIcs. Warsaw, PL: Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.

MLA:

Wißmann, Thorsten. "Supported Sets – A New Foundation for Nominal Sets and Automata." Proceedings of the 31st EACSL Annual Conference on Computer Science Logic, CSL 2023, Warsaw Ed. Bartek Klin, Elaine Pimentel, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023.

BibTeX: Download