Well-Quasi-Ordering Hereditarily Finite Sets


© Springer-Verlag Berlin Heidelberg 2011. Recently, strong immersion was shown to be a well-quasi-order on the class of all tournaments. Hereditarily finite sets can be viewed as digraphs, which are also acyclic and extensional. Although strong immersion between extensional acyclic digraphs is not a well-quasi-order, we introduce two conditions that guarantee this property. We prove that the class of extensional acyclic digraphs corresponding to slim sets (i.e. sets in which every memebership is necessary) of bounded skewness (i.e. sets whose ∈-distance between their elements is bounded) is well-quasi-ordered by strong immersion. Our results hold for sets of bounded cardinality and it remains open whether they hold in general.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)