{"entities":{"Q557912":{"pageid":559679,"ns":120,"title":"Item:Q557912","lastrevid":57103407,"modified":"2026-03-26T15:47:59Z","type":"item","id":"Q557912","labels":{"en":{"language":"en","value":"Avoiding large squares in infinite binary words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2184108"}},"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":"Q557912$25C6441C-31EA-4F04-BDCA-597FE82B64E9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4d8e7fc4e281eaf0be8799b448ba2604384a36bc","datavalue":{"value":{"text":"Avoiding large squares in infinite binary words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q557912$FDAE76F8-9A88-45F5-B416-5F7740E9D8BE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba3b42017a8aab50b4b5f4e93ae02c9db03fe762","datavalue":{"value":"1099.68080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557912$6886EB50-746F-4EFB-A624-FE9A04CF3A92","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"fb8579d08d02888dcfc6c4a0d1e7ad3780689962","datavalue":{"value":{"entity-type":"item","numeric-id":284844,"id":"Q284844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$6C6AF72B-313C-4949-9EBD-5EE74069AE93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"acbe3fcdaa2e72f3bce067779bfee150bff0b503","datavalue":{"value":{"entity-type":"item","numeric-id":405317,"id":"Q405317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$53CECF53-3794-4E0D-BA71-C637B3291891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"022e09a763cee1618c51c8e037cdf2557e0134f9","datavalue":{"value":{"entity-type":"item","numeric-id":161496,"id":"Q161496"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$23982F34-88C2-45C1-B8A0-37709E166F26","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$10399567-7AD2-45AA-B70B-F04CBA4CD8EF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3be35b99bc40d25914143aa31268a19fcdde1b9d","datavalue":{"value":{"time":"+2005-06-30T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q557912$8A0AA2AE-4010-4817-9FAE-6EC07247801A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4fa3321a6090c078a6ec54fb8f8c791e6a8eeb64","datavalue":{"value":"https://arxiv.org/abs/math/0306081","type":"string"},"datatype":"url"},"type":"statement","id":"Q557912$0A8C69E6-7E1A-4D46-BE22-5EA4EA30AB18","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7d5642d7ae23329e4bea180190c1c21dcf7029c9","datavalue":{"value":"A square is a nonempty word of the form \\(xx\\); a cube is of the form \\(xxx\\). Every binary sequence is known to contain a square, but there exist explicit examples of sequences with no \\(xx\\) such that the length of \\(x\\) satisfies \\(| x| \\geq 3\\). There exist also examples with no cube \\(xxx\\) and no square \\(yy\\) such that \\(| y| \\geq 4\\). Other sequences are proved to contain no square except \\(0^2\\), \\(1^2\\) and \\((01)^2\\). The authors give new proofs of these results by exhibiting constant length iterated morphisms. Using such morphisms allows them to prove that the number of finite binary words of length \\(n\\) with such avoidance properties is bounded by \\(1,002^n\\) and \\(1,178^n\\).  Finally, the authors exhibit an example of two infinite words \\((a_i)_i\\), \\((b_i)_i\\) avoiding squares \\(ww\\) with \\(| w| \\geq 4\\) and such that the sequence \\(a_1b_1a_2b_2 \\dots\\) has unbounded large squares. The method consists in exhibiting a constant length substitution on four letters whose fixed point avoids a given set of finite words. Combinatorial properties based on the set of forbidden subwords imply that the morphism maps square free finite words to square free words. An explicit infinite binary sequence with the expected properties is obtained as a projection on a two-letters alphabet of the fixed point of the four-letters iterated morphism.","type":"string"},"datatype":"string"},"type":"statement","id":"Q557912$787DE15D-E69F-41F1-9F78-A457B1599AA4","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557912$25283ADD-B90A-4F49-A96D-BA8EB77D1111","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557912$7D2DEE15-941E-4EED-AFA2-BF9C20E0331E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"80d3daff8b4ccfa680e788bf5bda41b6c23a8e25","datavalue":{"value":"2184108","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557912$756E50EA-6F54-4D04-BE72-2846DDAA51FC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"33f3a01e8586590fdf8cce006566a19a6ef18199","datavalue":{"value":"squarefree word","type":"string"},"datatype":"string"},"type":"statement","id":"Q557912$74E285AB-A04C-4FBC-92A4-5421C6BD9174","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a637358e1c8476c6de797ee8404350aea4083c5","datavalue":{"value":"cubefree word","type":"string"},"datatype":"string"},"type":"statement","id":"Q557912$3789F55A-A3AA-48C4-B155-D9B6A04D1CF3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8e273a5d9115cf1126333847d338692cb10b53ce","datavalue":{"value":"constant-length iterated morphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q557912$79F30F06-2138-4B15-A0AB-95393FA4B2F7","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":"Q557912$DE6434C2-C311-4D67-A1C8-08295DC4CADA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ae6a96726a8d13d2dc02f7495538152bf2e8ff3d","datavalue":{"value":"W2086666778","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557912$6AF7D7DD-253B-414C-804F-48679228D9AF","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"950f3bf0951443eb1e5bcbf62abe86752f7308ef","datavalue":{"value":{"entity-type":"item","numeric-id":4431260,"id":"Q4431260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$D2E08889-8EE5-4942-8C5E-CBEB497A6CC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6642d3922cf034533d4c1b604756f165194105e5","datavalue":{"value":{"entity-type":"item","numeric-id":1225054,"id":"Q1225054"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$3664E00C-AFDB-45D7-A139-8D0044C0EAC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55f9ca5907940f83f89f1617231572df8cbec4ef","datavalue":{"value":{"entity-type":"item","numeric-id":1394229,"id":"Q1394229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$388B58F8-F1D8-4118-B96E-5013DC912EFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eba8ed73dd1b442c38aeee6c8a4684d89ee39d7b","datavalue":{"value":{"entity-type":"item","numeric-id":1346736,"id":"Q1346736"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$73CC92F1-2334-4E10-B8C4-AF16C8E268A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$CA85CFF1-DABC-4CA9-960E-824CEB831B6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"88797e08049fec61a460a37d3c71918873ac101d","datavalue":{"value":{"entity-type":"item","numeric-id":598459,"id":"Q598459"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$A4D1402E-307B-477E-A6ED-E00AB764E5E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7fad8df311d3e7673c1d325c6bba2781d099247","datavalue":{"value":{"entity-type":"item","numeric-id":4700080,"id":"Q4700080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$313BD8CF-0DA5-41E6-84AD-F59DFF1F0DA4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5947edecc7132e864fdc0501ccbcc532c59b591a","datavalue":{"value":{"entity-type":"item","numeric-id":1132880,"id":"Q1132880"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q557912$2547D98D-D1AA-40D0-B391-F0D217599135","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8a50be83bc4522f29204d56615512eeafc134a07","datavalue":{"value":"10.1016/J.TCS.2005.01.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q557912$8DB13D01-14C7-49C8-80FB-B08E482B1964","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3cc1bfbe672dff2d6b83dc3450ddf1266cf03b7","datavalue":{"value":{"entity-type":"item","numeric-id":4453455,"id":"Q4453455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eecf05434a6f9b3f5c8049598e46eb6654ea8b3c","datavalue":{"value":{"amount":"+0.9957234859466552","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":"Q557912$876304B2-2FA5-4A65-ACC5-06C8F831544B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f396ec9d83034feb34d2c7e23e7c88d86daa6ccf","datavalue":{"value":{"entity-type":"item","numeric-id":3022001,"id":"Q3022001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecb3b310ff34c4bf92def5c39029335f17426e69","datavalue":{"value":{"amount":"+0.8752653002738953","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":"Q557912$70B9925C-0475-4075-8C55-125336BF63DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aef787e6cccc6d9066b23bbbc9782ff830c08d1e","datavalue":{"value":{"entity-type":"item","numeric-id":551207,"id":"Q551207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d8a87ec43b13f8e6910046fae6135354c5beb90","datavalue":{"value":{"amount":"+0.8449869751930237","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":"Q557912$A8AB8FEE-40D2-4531-84EE-547406535E42","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eed69ee9cbbc79a9abb0269ba4dc910d38dcd2e5","datavalue":{"value":{"entity-type":"item","numeric-id":5190080,"id":"Q5190080"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e17c96b74a638f7fe7e16fdbb29bf464136760e","datavalue":{"value":{"amount":"+0.8167435526847839","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":"Q557912$221C40FE-7DA4-42BE-B840-2558D4C3E7EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3301cdf43aab1497062b532bbc5cc5a43cc59178","datavalue":{"value":{"entity-type":"item","numeric-id":2333047,"id":"Q2333047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6bb5951bd3ee19e27e1608881200df6d88642328","datavalue":{"value":{"amount":"+0.8054597973823547","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":"Q557912$E9F17AA4-AC3A-4C40-BA0F-98BA11134239","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:557912","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:557912"}}}}}