DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2023.87

Ordinal Measures of the Set of Finite Multisets

Authors: Isa Vialard

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract

Well-partial orders, and the ordinal invariants used to measure them, are relevant in set theory, program verification, proof theory and many other areas of computer science and mathematics. In this article we focus on a common data structure in programming, finite multisets of some well partial order. There are two natural orders one can define on the set of finite multisets of a partial order: the multiset embedding and the multiset ordering. Though the maximal order type of these orders is already known, other ordinal invariants remain mostly unknown. Our main contributions are expressions to compute compositionally the width of the multiset embedding and the height of the multiset ordering. Furthermore, we provide a new ordinal invariant useful for characterizing the width of the multiset ordering.

Cite as

Isa Vialard. Ordinal Measures of the Set of Finite Multisets. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 87:1-87:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vialard:LIPIcs.MFCS.2023.87,
  author =	{Vialard, Isa},
  title =	{{Ordinal Measures of the Set of Finite Multisets}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{87:1--87:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.87},
  URN =		{urn:nbn:de:0030-drops-186210},
  doi =		{10.4230/LIPIcs.MFCS.2023.87},
  annote =	{Keywords: Well-partial order, finite multisets, termination, program verification}
}

Search Results

Documents authored by Vialard, Isa

Ordinal Measures of the Set of Finite Multisets

Abstract

Cite as

Thanks for your feedback!

Could not send message