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.
Titolo: | Is Hyper-extensionality Preservable Under Deletions of Graph Elements? |
Autori: | |
Data di pubblicazione: | 2016 |
Rivista: | |
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. |
Handle: | http://hdl.handle.net/11368/2872089 |
Digital Object Identifier (DOI): | http://dx.doi.org/10.1016/j.entcs.2016.03.008 |
URL: | http://www.sciencedirect.com/science/article/pii/S1571066116300160?via%3Dihub |
Appare nelle tipologie: | 1.1 Articolo in Rivista |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
1-s2.0-S1571066116300160-main.pdf | Documento in Versione Editoriale | ![]() | Open Access Visualizza/Apri |