Any hereditarily finite set S can be represented as a finite pointed graph –dubbed membership graph– whose nodes denote elements of the transitive closure of {S} and whose edges model the membership relation. Membership graphs must be hyper-extensional, that is pairwise distinct nodes are not bisimilar and (uniquely) represent hereditarily finite sets. We will see that the removal of even a single node or edge from a membership graph can cause “collapses” of different nodes and, therefore, the loss of hyper-extensionality of the graph itself. With the intent of gaining a deeper understanding on the class of hyper-extensional hereditarily finite sets, this paper investigates whether pointed hyper-extensional graphs always contain either a node or an edge whose removal does not disrupt the hyper-extensionality property.

Is Hyper-extensionality Preservable Under Deletions of Graph Elements?

CASAGRANDE, ALBERTO;
2016

Abstract

Any hereditarily finite set S can be represented as a finite pointed graph –dubbed membership graph– whose nodes denote elements of the transitive closure of {S} and whose edges model the membership relation. Membership graphs must be hyper-extensional, that is pairwise distinct nodes are not bisimilar and (uniquely) represent hereditarily finite sets. We will see that the removal of even a single node or edge from a membership graph can cause “collapses” of different nodes and, therefore, the loss of hyper-extensionality of the graph itself. With the intent of gaining a deeper understanding on the class of hyper-extensional hereditarily finite sets, this paper investigates whether pointed hyper-extensional graphs always contain either a node or an edge whose removal does not disrupt the hyper-extensionality property.
http://www.sciencedirect.com/science/article/pii/S1571066116300160?via%3Dihub
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S1571066116300160-main.pdf

accesso aperto

Tipologia: Documento in Versione Editoriale
Licenza: Creative commons
Dimensione 236.77 kB
Formato Adobe PDF
236.77 kB 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: http://hdl.handle.net/11368/2872089
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact