The celebrated Ackermann encoding of hereditarily finite sets is generalised to a parametric formula designed to map not only these sets but also hereditarily finite multisets and hypersets into the non-negative real numbers. This extension suggests a novel approach to the graph canonisation problem by reducing it to a simple comparison of real values. By suitably varying the sole parameter of this formula, both the original Ackermann encoding and another previously studied map emerge as special cases. When the parameter is chosen from the natural numbers, the function yields a bijective encoding of a subuniverse of hereditarily finite multisets into the natural numbers. If, instead, the parameter is chosen to be transcendental and lies within a specific interval on the positive real line, the function is conjectured to provide an injective encoding of both multisets and hypersets.

The Ackermann encoding and its siblings

Simone Boscaratto
;
Domenico Cantone
;
Eugenio Omodeo
;
Alberto Policriti
In corso di stampa

Abstract

The celebrated Ackermann encoding of hereditarily finite sets is generalised to a parametric formula designed to map not only these sets but also hereditarily finite multisets and hypersets into the non-negative real numbers. This extension suggests a novel approach to the graph canonisation problem by reducing it to a simple comparison of real values. By suitably varying the sole parameter of this formula, both the original Ackermann encoding and another previously studied map emerge as special cases. When the parameter is chosen from the natural numbers, the function yields a bijective encoding of a subuniverse of hereditarily finite multisets into the natural numbers. If, instead, the parameter is chosen to be transcendental and lies within a specific interval on the positive real line, the function is conjectured to provide an injective encoding of both multisets and hypersets.
In corso di stampa
File in questo prodotto:
File Dimensione Formato  
2507JLCv3.pdf

accesso aperto

Descrizione: JLC special issue on CILC 2024, 3rd version
Tipologia: Documento in Pre-print
Licenza: Creative commons
Dimensione 1.22 MB
Formato Adobe PDF
1.22 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/1314309
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact