{"entities":{"Q1122597":{"pageid":1133346,"ns":120,"title":"Item:Q1122597","lastrevid":66174438,"modified":"2026-04-12T08:03:07Z","type":"item","id":"Q1122597","labels":{"en":{"language":"en","value":"Using unavoidable set of trees to generalize Kruskal's theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4106913"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$E8BF1BDF-A4B2-4E2D-AA98-6893AAA945D7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1294ef6b4a05ba8808fa74514c89f01ba55bf062","datavalue":{"value":{"text":"Using unavoidable set of trees to generalize Kruskal's theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122597$AE930911-9504-4E57-BC07-E6C4A08152F2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ecf75bd822bbc2f51e00bd96893c6bdbebbebd5c","datavalue":{"value":"0676.06003","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$C8A07DD1-4E30-4A3E-BEA0-B3A4778589D0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"437202b227afbe81bb26e62c5283482eaa8e8984","datavalue":{"value":"10.1016/S0747-7171(89)80035-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$6AC46E21-61B9-44CE-8964-57E5156BB8E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ecb7dd8f294a869555be9c745d2e1373d849ec7b","datavalue":{"value":{"entity-type":"item","numeric-id":1122596,"id":"Q1122596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$C4E82ECC-888E-467E-BC70-B0CF2FEB3DAB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ea72303f92787da89554ee5fa15621068821a762","datavalue":{"value":{"entity-type":"item","numeric-id":99061,"id":"Q99061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$D0E70029-72C1-4439-A771-EFAE3150790B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1122597$22822830-EE62-423C-B498-015F913947A3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6885b839d82ed4725d0557da92c32f12b6e8af07","datavalue":{"value":"Termination is an important property for term rewriting systems. To prove termination, \\textit{N. Dershowitz} [Theor. Comput. Sci. 17, 279-301 (1982; Zbl 0525.68054)] introduces quasi-simplification orderings that are monotonic extensions of the embedding relation. He proves that they are well quasi-ordered and a fortiori well-founded by using a theorem of \\textit{J. B. Kruskal} [Trans. Am. Math. Soc. 95, 210-225 (1960; Zbl 0158.270)], which shows that the simple tree insertion order TIO (defined below) is a well quasi-ordering over a certain set of trees. (Well-founded means that every nonempty set contains at least one minimal element; well quasi- ordered means that every nonempty set contains at least one and at most a finite number of noncomparable minimal elements.) Dershowitz's method is powerful, but cannot be used when the rewriting system contains a rule whose right hand side is embedded in the left hand side. The purpose of this paper is to overcome this constraint, when the rewriting system uses a finite ranked alphabet, by generalizing Kruskal's theorem to obtain a family of quasi-orders TIO(S,\\(\\omega)\\) that are strictly included in TIO but are still well quasi-orders.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122597$8E5BEA07-C7CD-4FF6-B581-7D552FAB5CEA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e037813de56311048f7e0a208650360505bf4d4e","datavalue":{"value":"06A06","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$F86DB576-DE35-4F09-8F20-C2C75B4C497B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"092d9a7dfbbaaa84ba458f8d83190fce94c9aa54","datavalue":{"value":"68Q65","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$AE94D1A1-E748-4969-BF76-67FDD828E6AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$6129C9EE-8111-408D-9D9F-4FC77B0DB52E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6be78f1bad1f2f19058dbde65eb124c0430a7d27","datavalue":{"value":"68W30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$D97BDFBF-0543-4713-A988-AEC6CF1CD90D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$CE05AA0D-A567-4C1B-B866-25C0B63B983A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"263754b04b2a33118f31a7db120e67f883035f9b","datavalue":{"value":"4106913","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122597$4112A660-8046-42E3-AF9F-03BEDEA435B9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58acf4952d5f9adc27bc95a2037859c88d48f9a6","datavalue":{"value":"term rewriting systems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122597$65E723C0-6142-4FF3-8E01-C1F746E89FA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b623ea48f1b78fe645368925b901f946ce54549f","datavalue":{"value":"tree insertion order","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122597$8000E79C-47B8-4D6D-910E-B36EC05733A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2d9eb066dec41058dbd05f2eca151916b9df45e","datavalue":{"value":"well quasi-orders","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122597$0CAEC92E-CDF2-4052-BD91-73D851DFA9FD","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$FF2FD67A-6399-4107-8FF0-42E01315BA2E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"378088a63ec20245823db74d6a8845609e39ce21","datavalue":{"value":{"entity-type":"item","numeric-id":593789,"id":"Q593789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$A30F091B-FEED-4E52-B9B1-F476730017FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5426167c36bf53d870bf29cf50b30925d1c9562","datavalue":{"value":{"entity-type":"item","numeric-id":759489,"id":"Q759489"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$F05D4700-DDB8-4990-A258-09B57376C983","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58709679cfff7718457ae5dbfaa34a4e9b17219c","datavalue":{"value":{"entity-type":"item","numeric-id":5812263,"id":"Q5812263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$075C32F4-8C75-4EAF-80F9-8B1640C416CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"599c5dbf52817fbbe5f2f15e33a96dc6ac97514e","datavalue":{"value":{"entity-type":"item","numeric-id":3908463,"id":"Q3908463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$D4EE4FB6-3D00-4838-9EC2-643CD0B05AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11e5b43c5f0e711ef91c4f8e7255199d25558fbd","datavalue":{"value":{"entity-type":"item","numeric-id":5541375,"id":"Q5541375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$7AC69779-451E-4289-A663-CCB5667189F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c57448c3511c30ed92e5fbbbe68c6f2b95237a20","datavalue":{"value":{"entity-type":"item","numeric-id":2554710,"id":"Q2554710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122597$5D6FF9A7-5C43-4377-99FF-ABF024364C01","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"366f3bb41652b556606a12660fd89e8094629896","datavalue":{"value":{"entity-type":"item","numeric-id":5015375,"id":"Q5015375"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b6e38f714a998dcfaef4d0d3e63dbc522feeb01","datavalue":{"value":{"amount":"+0.8145549297332764","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122597$58F36296-9BFC-423E-9B89-E31B3AFC13AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2f9fd41350749d8e8ad94fb3378ec60db0fc068","datavalue":{"value":{"entity-type":"item","numeric-id":3711760,"id":"Q3711760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cdd388c1382ac019c35dec31784b36dc13124c1","datavalue":{"value":{"amount":"+0.8115513324737549","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122597$B4A382DA-706D-4321-A0CA-4364F9DCABEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"977cd8b99fcaad1edf7fb7340f8f6465da6f310d","datavalue":{"value":{"entity-type":"item","numeric-id":3491541,"id":"Q3491541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82393084af044355b52b3998a606f387c024d76a","datavalue":{"value":{"amount":"+0.7972555756568909","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122597$F95DCCFA-3C78-4458-89D5-7D3990079B0C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"659392d67e938ae435c9ddea5a7f1a6c0bee2670","datavalue":{"value":{"entity-type":"item","numeric-id":1892123,"id":"Q1892123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85a4ee39e97e01e64d00da8aadef509f411572fb","datavalue":{"value":{"amount":"+0.784773588180542","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122597$47393869-1580-491A-9F65-57C3F189EA69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a131c71e76eddfd40c0ecb8e8ead92f9e2fdc410","datavalue":{"value":{"entity-type":"item","numeric-id":4202962,"id":"Q4202962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f3964a32b84c928a6a824ff27121822b5a598395","datavalue":{"value":{"amount":"+0.7831835150718689","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1122597$E6423117-128A-40FC-B4AB-1D1D8D39C9E7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Using unavoidable set of trees to generalize Kruskal's theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Using_unavoidable_set_of_trees_to_generalize_Kruskal%27s_theorem"}}}}}