Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdulla, P., Delzanno, G., Van Begin, L.: A classification of the expressive power of well-structured transition systems. Information and Computation (in Press)
Ackermann, W.: Die Widerspruchfreiheit der allgemeinen Mengenlehre. Mathematische Annalen 114, 305–315 (1937)
Bang-Jensen, J., Gutin, G.: Digraphs Theory, Algorithms and Applications, 1st edn. Springer, Berlin (2000)
Bollobás, B.: Combinatorics. Cambridge University Press, Cambridge (1986)
Chudnovsky, M., Seymour, P.D.: A well-quasi-order for tournaments. J. Comb. Theory, Ser. B 101(1), 47–53 (2011)
Finkel, A., Schnoebelen, P.: Well-structured transition systems everywhere? Theoretical Computer Science 256(1-2), 63–92 (2001)
Higman, G.: Ordering by divisibility in abstract algebras. Proc. London Math. Soc. 3(2), 326–336 (1952)
Kruskal, J.B.: Well-quasi ordering, the tree theorem and Vászonyi’s conjecture. Trans. Amer. Math. Soc. 95, 210–225 (1960)
Levy, A.: Basic Set Theory. Springer, Berlin (1979)
Nash-Williams, C.S.J.A.: On well-quasi-ordering trees. In: Theory of Graphs and Its Applications (Proc. Symp. Smolenice, 1963), pp. 83–84. Publ. House Czechoslovak Acad. Sci. (1964)
Omodeo, E.G., Policriti, A.: The Bernays-Schönfinkel-Ramsey class for set theory: semidecidability. J. Symb. Log. 75(2), 459–480 (2010)
Parlamento, F., Policriti, A., Rao, K.: Witnessing Differences Without Redundancies. Proc. of the American Mathematical Society 125(2), 587–594 (1997)
Robertson, N., Seymour, P.: Graph minors. XX. Wagner’s conjecture. J. Combin. Theory, Ser. B 92, 325–357 (2004)
Robertson, N., Seymour, P.: Graph minors. XXIII. Nash–Williams’s immersion conjecture. J. Combin. Theory, Ser. B 100, 181–205 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Policriti, A., Tomescu, A.I. (2011). Well-Quasi-Ordering Hereditarily Finite Sets. In: Dediu, AH., Inenaga, S., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2011. Lecture Notes in Computer Science, vol 6638. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-21254-3_35
Download citation
DOI: https://doi.org/10.1007/978-3-642-21254-3_35
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-21253-6
Online ISBN: 978-3-642-21254-3
eBook Packages: Computer ScienceComputer Science (R0)