{"entities":{"Q2203606":{"pageid":2214349,"ns":120,"title":"Item:Q2203606","lastrevid":57775713,"modified":"2026-04-02T11:50:08Z","type":"item","id":"Q2203606","labels":{"en":{"language":"en","value":"On the longest common subsequence of Thue-Morse words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7256116"}},"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":"Q2203606$0A6EF111-CBA5-49A2-952F-816215197D50","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"86221febe710306d5ae84ea2eba46b9c7266c823","datavalue":{"value":{"text":"On the longest common subsequence of Thue-Morse words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2203606$90C23691-850B-47B3-9761-DE165A7BFD3F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2de8a9f40c676fb43ca56688bb95d71d2a05ab89","datavalue":{"value":"1477.68248","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2203606$2B81F529-FE49-41BD-97D4-C49D49BFE415","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e342cce2e3c7a719d61b2598a3f0faa2f1e687b","datavalue":{"value":{"entity-type":"item","numeric-id":2203605,"id":"Q2203605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2203606$071EAE48-06AB-4A98-9AA0-1C0C0F2ADF76","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2203606$1ECC5375-B94E-4D4D-896C-8DF04BAB0621","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7781abd2a97958fd1da5210c5f6f23fc30a06aa4","datavalue":{"value":{"time":"+2020-10-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2203606$B7FE9DDF-1D3B-4408-9015-415576876128","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5da9865d8149c4c2d3d15223aeaec4d5a7f420e","datavalue":{"value":"https://arxiv.org/abs/1904.00248","type":"string"},"datatype":"url"},"type":"statement","id":"Q2203606$611BAA5F-8B9F-4049-B299-8808E5DF90A0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"710ca8cafcb19a5cb7b9469934a5b8e525f37c9b","datavalue":{"value":"Let \\(t_n\\) be the \\(n\\)-th Thue-Morse word (that is, the prefix of length \\(2^{n-1}\\) of the infinite Thue-Morse word). Let \\(\\overline{t_n}\\) be the bitwise complement of \\(t_n\\), and let \\(a(n)\\) be the length of the longest common (scattered) subsequence (LCS) of \\(t_n\\) and \\(\\overline{t_n}\\). For example, the LCS of \\(t_4=01101001\\) and \\(\\overline{t}_4=10010110\\) is \\(01010\\), of length \\(5\\), hence \\(a(4)=5\\). The first few values of the sequence \\(a(n)\\) are \\(0, 1, 2, 5, 12, 26, 54, 110, 226, 462, 942, 1908,\\ldots\\).  In 2006, Jean Berstel asked whether a formula for \\(a(n)\\) exists. In the current paper, the author proves that \\(a(n)\\) can be lower-bounded by \\(2^n(1-o(1))\\), that is, the fraction of omitted letters in the longest common subsequence of the \\(n\\)-th Thue-Morse word and its bitwise complement goes to 0 as \\(n\\) goes to infinity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2203606$05AE2D24-7350-46AE-9CFF-3DC995CE012B","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"130d97dc1ca643e8efa64f9b07a28af4e0a2454b","datavalue":{"value":{"entity-type":"item","numeric-id":243831,"id":"Q243831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2203606$BD33791F-D1EE-427B-876A-EBE8F0019ACB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2203606$DF7FCA7D-A895-48A4-906C-FA46C8E3B1E7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"64ac56b8827b7d78a1e911d2332689abe79ac37b","datavalue":{"value":"7256116","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2203606$7D10CCFE-179E-467C-A42B-9068827E906D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1484d9165527900f2ecd9e3b2a7c6e8b90cf1370","datavalue":{"value":"Thue-Morse sequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2203606$63063160-BD88-4F8D-98DA-9EDB2740C2E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f0a0bf79411772273f5086c3d5a2f297706f321","datavalue":{"value":"longest common subsequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q2203606$48507D93-F42F-4A61-BE44-1DD724C4F857","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b93d69ebc1c51cfee06b00c8b748e2b4275c0266","datavalue":{"value":"combinatorial problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q2203606$5A1DA7E8-78A3-40F6-8CCD-06961549E089","rank":"normal"}],"P1463":[{"mainsnak":{"snaktype":"value","property":"P1463","hash":"650e761a5f418c574655712b35b1fe882f756011","datavalue":{"value":{"entity-type":"item","numeric-id":19297,"id":"Q19297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2203606$723E19E5-121D-47D3-81E9-7D5F7B0A9AB5","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":"Q2203606$766FFBCF-100B-4F69-9174-21DA208975CA","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9687ae032c833c6e2a28b1404a69f578583fdf37","datavalue":{"value":"W3047315976","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2203606$FC5CED56-5D3C-493F-9EFD-4329C4DB652C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"223550176370d5043c2c4ccaed292fb5cb47cccf","datavalue":{"value":{"entity-type":"item","numeric-id":4330617,"id":"Q4330617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2203606$6663A86E-6C18-4CFB-BCF7-CE1418C86DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bbfe8b3db045c3af5bd936077fb2e74b1125b562","datavalue":{"value":{"entity-type":"item","numeric-id":4443440,"id":"Q4443440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2203606$CB86788C-D04C-469A-AF9C-0F374874C5DD","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7b56cf81ce1bc75b3831f9edfa855432c6b8e54c","datavalue":{"value":"10.1016/J.IPL.2020.106020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2203606$D01DC0AC-E594-4983-86FA-6680BFB07E1A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"518820a6ccaf41815e2fa4cf4ce88e082cf45352","datavalue":{"value":{"entity-type":"item","numeric-id":5246103,"id":"Q5246103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cda69f5f8bc381d4079796f6757600875ffef9c6","datavalue":{"value":{"amount":"+0.772743821144104","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":"Q2203606$159BDA3F-D6E7-4FAC-B759-57F0A5606160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b1fddfbe8b5ad1c00b5ae4d22718e5da10abeef1","datavalue":{"value":{"entity-type":"item","numeric-id":2143625,"id":"Q2143625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc97f4e17abe1100e2824e9e6edbca87421607a2","datavalue":{"value":{"amount":"+0.7456541061401367","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":"Q2203606$F18014B9-FFAA-467D-A123-EE38C39BDF0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f1b30aa0b3a1e021c1a26b99b9b1c4cc86af3a15","datavalue":{"value":{"entity-type":"item","numeric-id":5463567,"id":"Q5463567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d52710fdfbd74bc43ecdc3b329d18a78742f8a92","datavalue":{"value":{"amount":"+0.7430983185768127","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":"Q2203606$AC20684B-6F0D-4FD5-A180-18252932011C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2eb4281a9b9a700fe77f69475a70f455e0c957ac","datavalue":{"value":{"entity-type":"item","numeric-id":2327559,"id":"Q2327559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"598178de84ad6dd5920848e2e411f3d2db923a7a","datavalue":{"value":{"amount":"+0.7412285804748535","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":"Q2203606$20E2E792-1C1E-4695-85EE-8D54A47E46EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12d8e7c8f359b1a3530573998b6cfb543f6ce896","datavalue":{"value":{"entity-type":"item","numeric-id":671435,"id":"Q671435"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"54cf38c0ea71ec12a0f9075dba32d300bd51ee63","datavalue":{"value":{"amount":"+0.7406839728355408","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":"Q2203606$2545DC9B-68C8-4726-8A08-55D0B522ADD1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2203606","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2203606"}}}}}