{"entities":{"Q405191":{"pageid":406958,"ns":120,"title":"Item:Q405191","lastrevid":61642428,"modified":"2026-04-11T00:40:02Z","type":"item","id":"Q405191","labels":{"en":{"language":"en","value":"Application of entropy compression in pattern avoidance"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340174"}},"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":"Q405191$4197BF07-B82D-421E-8CCA-A1FE41F2CC87","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"479619ce92446598005c0b7db76f6df8601a73e9","datavalue":{"value":{"text":"Application of entropy compression in pattern avoidance","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405191$A1A54B50-703F-4ED3-8636-6FF9A6771784","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"41e0fbc9acc7646c20e1508bc13f9219cd5e0ffc","datavalue":{"value":"1299.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405191$2B4F6399-8917-464D-ABEA-B8E828717633","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2b3826c52088f4aa88f5af749aa0df3944c777e9","datavalue":{"value":{"entity-type":"item","numeric-id":244933,"id":"Q244933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$8FB56F84-9EC8-4600-A569-788CAB3B2A57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3fd2acd4c850efcd990f7986e7e150d8fca9a262","datavalue":{"value":{"entity-type":"item","numeric-id":317410,"id":"Q317410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$C8D984B6-A6A2-42BD-B3E3-5DBE76C9CDE9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$BFB97022-C22E-44DF-A778-6F01D2DE6EB8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405191$61C83C1E-9A94-4108-B0B0-D2C2DB2BE22B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e540823cc4884ae4ba63bc75e15708191d529cbb","datavalue":{"value":"https://arxiv.org/abs/1301.1873","type":"string"},"datatype":"url"},"type":"statement","id":"Q405191$67A24DD1-1C92-4946-942F-2D0A64762273","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"5766c61dcf705b92525a80a6f5e8fecb3af41d8c","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i2p7","type":"string"},"datatype":"url"},"type":"statement","id":"Q405191$23A246F1-219D-4AEC-89D6-5B3E0AFEC9D5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6a70d34f700edcd9cf6d4fd7bd12641d7036fb1c","datavalue":{"value":"Summary: In combinatorics on words, a word \\(w\\) over an alphabet \\(\\Sigma\\) is said to avoid a pattern \\(p\\) over an alphabet \\(\\Delta\\) if there is no factor \\(f\\) of \\(w\\) such that \\(f= h(p)\\) where \\(h: \\Delta^*\\to\\Sigma^*\\) is a non-erasing morphism. A pattern \\(p\\) is said to be \\(k\\)-avoidable if there exists an infinite word over a \\(k\\)-letter alphabet that avoids \\(p\\). We give a positive answer to Problem 3.3.2 in \\textit{M. Lothaire}'s book [Algebraic combinatorics on words. Cambridge: Cambridge University Press (2002; Zbl 1001.68093)], that is, every pattern with \\(k\\) variables of length at least \\(2^k\\) (resp. \\(3\\times2^{k-1}\\)) is 3-avoidable (resp. 2-avoidable). This conjecture was first stated by \\textit{J. Cassaigne} [Motifs \u00e9vitables et r\u00e9gularit\u00e9 dans les mots. Paris: Universit\u00e9 Paris VI (PhD Thesis) (1994)]. This improves previous bounds due to \\textit{J. P. Bell} and \\textit{T. L. Goh} [Inf. Comput. 205, No. 9, 1295--1306 (2007; Zbl 1127.68073)] and \\textit{N. Rampersad} [Electron. J. Comb. 18, No. 1, Research Paper P134, 8 p. (2011; Zbl 1219.68128)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q405191$DC9331B9-EB79-46F0-9604-B408CB5DA822","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405191$8388F497-145C-4B9D-AF6B-A1F528B722FA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"26147530d929c5e7355db1cb73343c267eb5f2c5","datavalue":{"value":"6340174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405191$C88508CF-F2D1-4B03-AFB6-1B40428F9CD3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2c9d10a3cc7e7a04e25f3a32ce40e8fbcfa3f461","datavalue":{"value":"word","type":"string"},"datatype":"string"},"type":"statement","id":"Q405191$29D7EA52-B616-49D4-B45C-174C22A044F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d589d1418bb454d0d57abd8c2020b4fc06552aa","datavalue":{"value":"pattern avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q405191$ACBA57C7-7A75-4796-A93C-CFDDCD80B9A1","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":"Q405191$659AD6F0-17B5-4072-A153-9ACA612E0499","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"6c7183512e2829a55f36b5e7ad58903f071c8748","datavalue":{"value":{"entity-type":"item","numeric-id":1137038,"id":"Q1137038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$5B193201-D90F-4967-8813-7CB75A35A0A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95fa878fb2c02613b94617992debe081ca5a953e","datavalue":{"value":{"entity-type":"item","numeric-id":2381499,"id":"Q2381499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$F6E0E3CF-D2D1-4A09-914F-6D556D078B01","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b059d98e87e125a4ec7586a7e05320642b9ba1b","datavalue":{"value":{"entity-type":"item","numeric-id":393106,"id":"Q393106"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$E24D4319-91BE-400C-9DE0-1506AB825BF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c7cb4580046e41e82474f129797f73e3c0a82f30","datavalue":{"value":{"entity-type":"item","numeric-id":524188,"id":"Q524188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$75FF17E5-84DF-435B-867F-53335A2C637D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbba895f8d0ef9e7d508881c55e2503f08f206db","datavalue":{"value":{"entity-type":"item","numeric-id":2444732,"id":"Q2444732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$0B2068CC-4DDA-43E5-ADD0-7502733BD9FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$1D15D6F5-2C17-4322-9E13-8B919B3BC5F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d06f971812093fe6317243e078dd346e71338f6","datavalue":{"value":{"entity-type":"item","numeric-id":3578191,"id":"Q3578191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$D5CF2FB9-92F9-464B-A215-586CDA4454B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7273c5b24ad72bbfbad8718f0b57ab619400c14c","datavalue":{"value":{"entity-type":"item","numeric-id":3421905,"id":"Q3421905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$5B266D49-7BDC-475F-A59E-AA1893B65A73","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd5291d4aaf0fe56994abe4132f5cb7c329d4895","datavalue":{"value":{"entity-type":"item","numeric-id":3768905,"id":"Q3768905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$0BA0F776-F914-4C70-B679-4D82DD725F4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"40afc6d6cf261b10a183c431434c5d0190bb4924","datavalue":{"value":{"entity-type":"item","numeric-id":547794,"id":"Q547794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$A30DF6BC-FDBF-4AFB-9C61-8E175F630274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef6397b0459e4b59017759e272fe7fd547caa52e","datavalue":{"value":{"entity-type":"item","numeric-id":1186515,"id":"Q1186515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$4ED70501-F0DB-4A85-B3FE-7C5BF0110361","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f414b9ea6adc0b4e47e61f4708d1d85e9b51232e","datavalue":{"value":{"entity-type":"item","numeric-id":3734729,"id":"Q3734729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405191$48FA8BCC-C2B8-4B65-B9BA-C4853E21A583","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"f6f44dfc8c9ed40dfeda013a429b6a16bf892f18","datavalue":{"value":"bafkreicx6znjrnnvh4qozoj3c3xalggv47eid5mkmcqb3ylt3wn4rzxi6u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405191$D32C7751-E4CD-4F62-B8A0-1E2BF24B8E8B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31efb7de0106a341aeb24053c33ca184b44f73c7","datavalue":{"value":{"entity-type":"item","numeric-id":547794,"id":"Q547794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5bbe0bb72dc344831afc73d5f7adbb02e47ac1a2","datavalue":{"value":{"amount":"+0.8515725135803223","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":"Q405191$2B906D35-B36E-4922-9863-3A1DC9AE4CE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08e9b206615ad0db2bc8550ae8b3c6231c1361b7","datavalue":{"value":{"entity-type":"item","numeric-id":2517160,"id":"Q2517160"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"08a56ff3c3ed38e33d7cb0e6ab150e3f2f26b482","datavalue":{"value":{"amount":"+0.8481023907661438","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":"Q405191$26F9AE20-0343-41A4-A63C-CD61C8E0A5E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b0d08b54a83694ff1ff383415c69079a07c18c2","datavalue":{"value":{"entity-type":"item","numeric-id":3774970,"id":"Q3774970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"240a1a928b9b430e7db7c9877aada9912dd96e4b","datavalue":{"value":{"amount":"+0.833166241645813","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":"Q405191$4A15C67C-CF7E-4808-8167-696AF56B6307","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcf7fe36a78637692581227d2c1abc41a3b83f96","datavalue":{"value":{"entity-type":"item","numeric-id":2635083,"id":"Q2635083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"db0c277320db7ba64adc0af849bd44f54a8a7a61","datavalue":{"value":{"amount":"+0.8298581838607788","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":"Q405191$E7FD3D65-9BE6-4894-9DE6-509E051D66EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3b868ce7997bce7b45b57f622edb73f1f225db6e","datavalue":{"value":{"entity-type":"item","numeric-id":2817400,"id":"Q2817400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f93bd57d1ac64173f266ec24fd55d608dde0cc61","datavalue":{"value":{"amount":"+0.8295474648475647","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":"Q405191$90A57E33-8BE6-463B-A367-B0CBF178F70D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Application of entropy compression in pattern avoidance","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Application_of_entropy_compression_in_pattern_avoidance"}}}}}