{"entities":{"Q1069312":{"pageid":1080064,"ns":120,"title":"Item:Q1069312","lastrevid":48890683,"modified":"2026-01-06T02:32:16Z","type":"item","id":"Q1069312","labels":{"en":{"language":"en","value":"Another generalization of Higman's well quasi order result on \\(\\Sigma ^*\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3934424"}},"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":"Q1069312$E143A3DD-8E5F-48D8-A912-25322BCF3D44","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"27a1547ea0d9eb7e29d44fbf3f927d4836b6f344","datavalue":{"value":{"text":"Another generalization of Higman's well quasi order result on \\(\\Sigma ^*\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1069312$1C498223-59F8-42B1-8915-3E23636F56EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0432c8dc494beec0bb8b07915fb8629ba2620794","datavalue":{"value":"0583.68039","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069312$75A8E827-FF75-40AE-BBD0-AD577B1E7637","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"606a69f5b4ae0d2990c2f36aeda3098e2bc16c4b","datavalue":{"value":"10.1016/0012-365X(85)90176-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069312$0425BB76-47CE-42EE-A091-BE143C4FEBBD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"bd2d3ae090b22c3a641be4fedb72aeccd09f0d74","datavalue":{"value":{"entity-type":"item","numeric-id":676241,"id":"Q676241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069312$7AB5ABC1-3AAE-467F-B7F9-7A4CFDDB199F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069312$73B51D5D-53E3-4555-882F-4A82FE79BC79","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3c94df5c9af0ede578c52141befd29044de13172","datavalue":{"value":{"time":"+1985-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":"Q1069312$A22BA1B8-8E92-4D5D-BA3C-11CC72E0D737","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fe9adb4c5571f06e97fa7d076366dbf95bf0133f","datavalue":{"value":"We present another generalization of \\textit{G. Higman}'s result [Proc. Lond. Math. Soc., III. Ser. 2, 326-336 (1952; Zbl 0047.034)] that the subsequence embedding relationship on a finitely generated free monoid is a well quasi order. Our result is analogous to the generalization of Higman's result given by \\textit{A. Ehrenfeucht}, \\textit{D. Haussler} and \\textit{G. Rosenberg} [Theor. Comput. Sci. 27, 311-332 (1983; Zbl 0553.68044)] in the following manner. In the quasi orders we consider, we are given a finite set S of non-null words from \\(\\Sigma^*\\) and we demand that \\(x_ 1\\ldots x_{k+1}\\) is less than or equal to \\(x_ 1a_ 1\\ldots x_ ka_ kx_{k+1}\\) for any words \\(x_ 1\\ldots x_{k+1}\\in \\Sigma^*\\) and any single word \\(a_ 1\\ldots a_ k\\in S\\), where \\(a_ i\\in \\Sigma\\), \\(1\\leq i\\leq k\\). The least quasi order obtained in this fashion is denoted \\(\\lesssim_ S\\). In contrast to the notion of subword unavoidability used by \\textit{A. Ehrenfeucht}, \\textit{D. Haussler} and \\textit{G. Rosenberg} [loc. cit.], S is said to be subsequence unavoidable (in \\(\\Sigma^*)\\) if and only if there exists a \\(k_ 0\\) such that any word longer than \\(k_ 0\\) has a (nonempty) subsequence of letters (not necessarily contiguous) which form a word in S. We show that \\(\\lesssim_ S\\) is a well quasi order on \\(\\Sigma^*\\) if and only if S is subsequence unavoidable in \\(\\Sigma^*\\). As an application of this result, we show that the iterated shuffle of a finite set S with itself is a regular language if and only if S is subsequence unavoidable.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069312$F6A960BF-5098-499B-B50E-0DF8D3A0DA8F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069312$726FDBD7-0F86-4D0F-BA5B-402945D529ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1f2d51749736d7a35abf742f9ac7394f1aeed58c","datavalue":{"value":"20M35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069312$C1FD4750-D359-49A5-8FEF-91035F3A4DEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"03468f1d5abafefed311cc9ccae9ddd73ff4dbd8","datavalue":{"value":"20M05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069312$60528074-5FC8-4D99-941B-A35C6CD72052","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8432d49355716c30833e127782ef32920e53050b","datavalue":{"value":"3934424","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069312$8ED0865E-82D0-424E-9166-C07B1C97C8D5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8ab4126af51fb1d8bff988e5ec9d2c4723dc5943","datavalue":{"value":"subsequence embedding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069312$6151D378-2367-45AC-8697-62FF2D0353BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19d62d6341e1fbaeb4bdb795d85fa5163962980b","datavalue":{"value":"finitely generated free monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069312$2A8571B4-5452-4839-9B2B-3983D4CBB7FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2977bda8220ccceab9112dd54c73384bf0be45e3","datavalue":{"value":"iterated shuffle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069312$B90F5D09-022C-4F94-8F27-66805B52A804","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3ea9b35a533d874f0a32d77e584c8b61e0e7c2fe","datavalue":{"value":"regular language","type":"string"},"datatype":"string"},"type":"statement","id":"Q1069312$C76439DB-2B73-4729-B1D6-F59F12667D1E","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":"Q1069312$E7884850-4E93-4050-A046-2B660BF367A1","rank":"normal"}],"P223":[{"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":"Q1069312$290CE965-160D-4F60-97CD-47869C6A6538","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":"Q1069312$0498FB1F-C1E4-4F0D-9515-3583ABA82FB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f256b121b5960183092d61923f4090ee7435150d","datavalue":{"value":{"entity-type":"item","numeric-id":1161057,"id":"Q1161057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069312$C0D855EE-0299-45C8-BCE6-4010EED49E08","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":"Q1069312$7EFEBA23-B89C-4D77-8C65-BE1D9D221D13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8107b480decc678c92b78dee11f4a9915c90692b","datavalue":{"value":{"entity-type":"item","numeric-id":5541339,"id":"Q5541339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069312$CBBA3BC2-2BAF-4794-9CD5-B9AD8A8C3437","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d3e79c1198a5adad0b28f20fcd66d4c98012ceb6","datavalue":{"value":{"entity-type":"item","numeric-id":4162475,"id":"Q4162475"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069312$24A321DD-6671-4410-8456-6F20D381594E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a200920fb3c87ae0a99bb88fd138bf2ad3736fa","datavalue":{"value":{"entity-type":"item","numeric-id":800086,"id":"Q800086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1069312$BA00CED2-9553-4896-9633-4BD38203FB8D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"7eac4b67c142219061f4f5e25f380d5b1fde1403","datavalue":{"value":"https://doi.org/10.1016/0012-365x(85)90176-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1069312$8C104BDE-31E2-4AFB-9D6C-C270779B493C","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b240eaedcca4b850f6a9f9c5951933391e39f910","datavalue":{"value":"W2078146321","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1069312$74130908-7B8F-4365-963C-DF344C18485B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"93ab39a622c9b9688b8edf75a5405489962af878","datavalue":{"value":{"entity-type":"item","numeric-id":1120606,"id":"Q1120606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5522140ea009b7d251142aec95f6ffc5bd918bd7","datavalue":{"value":{"amount":"+0.8008897304534912","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":"Q1069312$E33FCA5C-76C0-40A2-A1F8-E724AD386D3A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e8093139551ff0af572dd1fc5219711f72f3fdd2","datavalue":{"value":{"entity-type":"item","numeric-id":884464,"id":"Q884464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"399c538e3c1a03143187da20503073a70a232791","datavalue":{"value":{"amount":"+0.795986533164978","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":"Q1069312$D9DA9187-D3B5-4FA8-82B6-D950C128B74A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"420f2d90a84e42e09ee8510bb2e2e5291c22b099","datavalue":{"value":{"entity-type":"item","numeric-id":3533001,"id":"Q3533001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3a92e2fa8e8a7aeb88ebb1473fc09993062f6b3","datavalue":{"value":{"amount":"+0.7957471609115601","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":"Q1069312$E993635A-95F4-4036-B8A0-1736F8AB949E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd61075b7901f939396737670a55b11f958210a8","datavalue":{"value":{"entity-type":"item","numeric-id":1356526,"id":"Q1356526"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"18b7a2c26a9d050a9b4150a39b8f444650393ccc","datavalue":{"value":{"amount":"+0.794600248336792","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":"Q1069312$4EE9C9BC-E8AD-4A60-BAEE-57C03A9E2534","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc159a503ddb0bb38a29cf347e813b0e1ae823b0","datavalue":{"value":{"entity-type":"item","numeric-id":3617063,"id":"Q3617063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48794ca30b524c90af4aa25bf1c8a7fd609ab897","datavalue":{"value":{"amount":"+0.787472665309906","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":"Q1069312$F22F3636-ACAA-48FD-BBB8-93ECCE9096AD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1069312","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1069312"}}}}}