{"entities":{"Q2517160":{"pageid":2527903,"ns":120,"title":"Item:Q2517160","lastrevid":57049599,"modified":"2026-03-26T10:36:30Z","type":"item","id":"Q2517160","labels":{"en":{"language":"en","value":"Pattern avoidance in partial words over a ternary alphabet"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6472905"}},"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":"Q2517160$A45DC216-DDF3-4F2E-B09C-A4AD9CE583DC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"51022b2cd29c3939c04d73322297bcad712fc575","datavalue":{"value":{"text":"Pattern avoidance in partial words over a ternary alphabet","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2517160$6A1F1462-94EA-4FA1-9157-9C449343EB5D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d3edb57c1a696eb9b7575649c9c45b59b07bb199","datavalue":{"value":"1329.68198","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517160$E2BFBC7C-61A4-4B80-882A-5F58A0A26C86","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"971461748f5aee02f8ad691e9ead14422343074f","datavalue":{"value":{"entity-type":"item","numeric-id":504975,"id":"Q504975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$5F218FE5-E80F-4C0B-97C0-696324F88716","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f563e849d82b33747d8a072aeef69bd478f05b24","datavalue":{"value":{"time":"+2015-08-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2517160$028D3ED2-FFCD-482F-BBF2-1DF819129779","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e8dbd018b04e4cc4d42b8c499ded1d9ddf070a37","datavalue":{"value":"https://semanticscholar.org/paper/df82d376639abe77f6fc71e409caf3d93df0733c","type":"string"},"datatype":"url"},"type":"statement","id":"Q2517160$0476E63A-8B78-49EA-ADEB-94B22D7FA39A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab71993cf4d5f44db8c2576644d151c69824e7b1","datavalue":{"value":"A long-standing conjecture from [\\textit{J. Cassaigne}, Motifs \u00e9vitables et r\u00e9gularit\u00e9s dans les mots. Paris: Universit\u00e9 Paris VI (PhD Thesis) (1994)] states that for a pattern \\(p\\) with exactly \\(k\\) distinct variables, (1) if \\(p\\) is of length at least \\(2^k\\), then its avoidability index is at most 3, while (2) if \\(p\\) is of length at least \\(3 \\cdot 2^{k-1}\\), its avoidability index is 2. This conjecture was recently settled independently by \\textit{F. Blanchet-Sadri} and \\textit{B. Woodhouse} [Theor. Comput. Sci. 506, 17--28 (2013; Zbl 1301.68209)] and by \\textit{P. Ochem} and \\textit{A. Pinlou} [Electron. J. Comb. 21, No. 2, Research Paper P2.7, 12 p. (2014; Zbl 1299.68046)]. Furthermore, Blanchet-Sadri and Woodhouse conjectured that (1) is true for doubled patterns with \\(k \\geq 4\\) distinct variables when partial word avoidability is concerned. In this paper, the authors answer affirmatively this conjecture on partial words via entropy compression and the probabilistic method.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517160$FBB46D82-129A-423B-A607-1CE73966B863","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3f9e311a53969bed982204d1446a9d77dda26ac9","datavalue":{"value":{"entity-type":"item","numeric-id":591667,"id":"Q591667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$7ED99EFF-2B86-4039-9381-6C403E720B9F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517160$6450B8CA-7686-46D5-AF46-2923412C09FC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c5d32fba86db6ed1c0359c451617fb7bf82f51fc","datavalue":{"value":"6472905","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517160$D68DB9DB-92B7-4463-8741-FAB55F978927","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517160$79E96C85-01E1-44D9-BA12-B453F9B2E20C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8967d0a934eaa6194b5afbe1fbb4e78c8127645d","datavalue":{"value":"combinatorics on words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517160$166E0F3B-54F0-43F5-833D-EC901194F6BD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3d589d1418bb454d0d57abd8c2020b4fc06552aa","datavalue":{"value":"pattern avoidance","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517160$D32C42DA-FBF0-4615-BDEC-9664FC34129A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"665bb6b521670920ffccf875b8511ad8132838e1","datavalue":{"value":"partial words","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517160$BE39DF2F-EBF4-4E5D-A823-FE05B9A35BB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"13f37f55b2aa8ed3aeca864fa8be46306b3ae686","datavalue":{"value":"entropy compression","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517160$35DEB72A-1432-4B15-8174-3FBAFBB927F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e940ac37279303889e6f8c6cd8870094f89fb3aa","datavalue":{"value":"probabilistic method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2517160$05459D57-000C-4C82-8551-30D7AF2EC059","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":"Q2517160$1CE2FF6E-262E-4A90-A5B3-14966EA1FE6F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"44d184a0db67b0ac44923c7c149e9e049ace9c6c","datavalue":{"value":"W1155495284","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517160$3A786485-59D8-47D2-A633-41BEEAA735A2","rank":"normal"}],"P223":[{"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":"Q2517160$A7AE843D-BB84-47AD-BA6A-351DCE53BF2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51ef8fac80d379bd80260f843138869332bd9384","datavalue":{"value":{"entity-type":"item","numeric-id":3549563,"id":"Q3549563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$44AB3B28-F0CA-438B-8E24-5E3AB30D3688","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3aa71240eb33813f154bb4436730d5594fac8914","datavalue":{"value":{"entity-type":"item","numeric-id":4909201,"id":"Q4909201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$F8DAD85F-9026-4BD7-AC63-0BB8B910A889","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"363a2aa1156f8ebf0e86da73ecae7bd8774ca70d","datavalue":{"value":{"entity-type":"item","numeric-id":5428239,"id":"Q5428239"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$B43B3081-E5D6-47AB-AEDF-263DAE494A94","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":"Q2517160$2FC64D8B-AE4E-404B-8DBC-AD7FC7B2D5A8","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":"Q2517160$CEAC15BC-6A82-4E00-81F0-2FC001D21CB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3db50cc9b0933259e9a4a82636adcdcb84e1f2c4","datavalue":{"value":{"entity-type":"item","numeric-id":405191,"id":"Q405191"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$94429CFF-5F97-4EE1-94BE-2164A6E09F5C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f557334cc2065b50f0b095bea8e6b579d9071849","datavalue":{"value":"10.1515/UMCSMATH-2015-0013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2517160$D7AAA2D5-985D-4B09-9B42-CE49BB76BB07","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"e89726a136d708decc59da26b744d3a83ca1243b","datavalue":{"value":{"entity-type":"item","numeric-id":2953580,"id":"Q2953580"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$1E4D5C06-E5ED-4A90-BADB-52FCA75F358C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6222c3bb9ecfdd8a7e629afaef338028a72227a4","datavalue":{"value":{"entity-type":"item","numeric-id":3564853,"id":"Q3564853"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef757d9c545bd89d2b60ca2f3693eb219f3daa96","datavalue":{"value":{"amount":"+0.9206601","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$0748E653-9BF0-4910-914A-496D2CE78D1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca0d3a4a22c80bf4f6a2a1afbf66729049caea70","datavalue":{"value":{"entity-type":"item","numeric-id":766156,"id":"Q766156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef757d9c545bd89d2b60ca2f3693eb219f3daa96","datavalue":{"value":{"amount":"+0.9206601","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$FA479CA2-DCB2-4B91-9B7D-2CECFDD1DA71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ddaf1f130429aa1e569920b955d5b274a2bed9e","datavalue":{"value":{"entity-type":"item","numeric-id":2912721,"id":"Q2912721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c909bf956037c58a941ae2596d2776b17c36d460","datavalue":{"value":{"amount":"+0.9199336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$FC3A449C-7021-42A3-8C2F-5D1AAF158031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e2938b3927df7e9ac051c76be4b2b5ff39dd5dea","datavalue":{"value":{"entity-type":"item","numeric-id":2874640,"id":"Q2874640"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c909bf956037c58a941ae2596d2776b17c36d460","datavalue":{"value":{"amount":"+0.9199336","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$71E0ED61-E44E-4B1D-8263-C71A67838DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5144e1b05573ae94d68c32ea850574f36000ae1","datavalue":{"value":{"entity-type":"item","numeric-id":396699,"id":"Q396699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22edd77d7726102c17f6ccacfc7c72d0e9fc6670","datavalue":{"value":{"amount":"+0.91518307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$5CAD6709-F3A6-4FD1-9B9B-5489B2AD1E06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fc0d5dd60d5949ea3396978d274598776285b896","datavalue":{"value":{"entity-type":"item","numeric-id":2876575,"id":"Q2876575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22edd77d7726102c17f6ccacfc7c72d0e9fc6670","datavalue":{"value":{"amount":"+0.91518307","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$95BAAE40-2DE7-4666-A5D9-606CD8D56A59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0a4591696fc60501029712336497c65a4de390aa","datavalue":{"value":{"entity-type":"item","numeric-id":2635082,"id":"Q2635082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd1692b5369b051794c1ecb68a3fd5e9b289617f","datavalue":{"value":{"amount":"+0.9143363","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$7BC76B53-1697-4FB4-8099-DEE026F1AF54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cf05dc17162986cbd79981cebdf4e6662e1d9197","datavalue":{"value":{"entity-type":"item","numeric-id":5740407,"id":"Q5740407"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11ff36f55976ff75792c7819c813f36bc2047e5a","datavalue":{"value":{"amount":"+0.8918423","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$363892DC-E840-4731-875F-5ADB2598C37A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2dc74d0728358522ebb2816199afd3c4626eb60","datavalue":{"value":{"entity-type":"item","numeric-id":3004576,"id":"Q3004576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6b5e24a80e6a193cb490cedcefdf67f35ec717","datavalue":{"value":{"amount":"+0.8852902","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$E88FF56E-2CF4-44DA-A7CD-802D5DE54ED1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebac7db87e73909b88c74276ebcaebc4f19dc2fd","datavalue":{"value":{"entity-type":"item","numeric-id":3455038,"id":"Q3455038"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1c6879bd20313f5d19377fae75d053a7c37bdc9","datavalue":{"value":{"amount":"+0.88408446","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2517160$7D597916-3B51-4171-B1AB-304590A437F6","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"6e2260e47a2889770c9d5516a7c5ae827b188d2b","datavalue":{"value":{"entity-type":"item","numeric-id":6830563,"id":"Q6830563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2517160$FAF0F4BE-A566-4110-9A00-5C6A44E4C83C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2517160","badges":[]}}}}}