License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2023.28
URN: urn:nbn:de:0030-drops-174892
URL: https://drops.dagstuhl.de/opus/volltexte/2023/17489/
Jacobs, Bart ;
Stein, Dario
Counting and Matching
Abstract
Lists, multisets and partitions are fundamental datatypes in mathematics and computing. There are basic transformations from lists to multisets (called "accumulation") and also from lists to partitions (called "matching"). We show how these transformations arise systematically by forgetting/abstracting away certain aspects of information, namely order (transposition) and identity (substitution). Our main result is that suitable restrictions of these transformations are isomorphisms: This reveals fundamental correspondences between elementary datatypes. These restrictions involve "incremental" lists/multisets and "non-crossing" partitions/lists. While the process of forgetting information can be precisely spelled out in the language of category theory, the relevant constructions are very combinatorial in nature. The lists, partitions and multisets in these constructions are counted by Bell numbers and Catalan numbers. One side-product of our main result is a (terminating) rewriting system that turns an arbitrary partition into a non-crossing partition, without improper nestings.
BibTeX - Entry
@InProceedings{jacobs_et_al:LIPIcs.CSL.2023.28,
author = {Jacobs, Bart and Stein, Dario},
title = {{Counting and Matching}},
booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
pages = {28:1--28:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-264-8},
ISSN = {1868-8969},
year = {2023},
volume = {252},
editor = {Klin, Bartek and Pimentel, Elaine},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17489},
URN = {urn:nbn:de:0030-drops-174892},
doi = {10.4230/LIPIcs.CSL.2023.28},
annote = {Keywords: List, Multiset, Partition, Crossing}
}
Keywords: |
|
List, Multiset, Partition, Crossing |
Collection: |
|
31st EACSL Annual Conference on Computer Science Logic (CSL 2023) |
Issue Date: |
|
2023 |
Date of publication: |
|
01.02.2023 |