{"entities":{"Q782596":{"pageid":784445,"ns":120,"title":"Item:Q782596","lastrevid":64294614,"modified":"2026-04-11T18:53:53Z","type":"item","id":"Q782596","labels":{"en":{"language":"en","value":"Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7225138"}},"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":"Q782596$02031C61-5370-4D9E-909F-B960ED35CAA2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"14e1a4fa8f31bf3e7f634cda1997ee627df88049","datavalue":{"value":{"text":"Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q782596$DA7356A9-657D-471A-A6CE-546F6EEAF795","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cfa7135c9490f56334e4875db316fd3cdf1ac438","datavalue":{"value":"1446.68130","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782596$E18E4BF4-37C5-424F-8F18-47E33D33BD36","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"3a227e7fdfbef68c1fec9efd7104b58f748cb75f","datavalue":{"value":"10.1007/978-3-030-40608-0_27","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782596$8163B3C6-8E7A-4D9D-B847-1916DE032394","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a12141a30b62e30eb0fdbf8f3a0b0c8897ffbef3","datavalue":{"value":{"entity-type":"item","numeric-id":243591,"id":"Q243591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782596$2DC7672A-1E12-4EBE-8EF6-87169487A811","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"22458278ec74a314b6135bdc3f737fdfc6b96f8c","datavalue":{"value":{"entity-type":"item","numeric-id":243830,"id":"Q243830"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782596$1CC9E60C-E60C-43F6-847D-98CF89036E1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b670a29fa887ae64f28e8fd2374637d5f53c09b2","datavalue":{"value":{"entity-type":"item","numeric-id":728276,"id":"Q728276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782596$09096264-2469-4083-A78D-CCA1A3A98208","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3593513fb886b848beb0e54fe4dc7d6c5ab33879","datavalue":{"value":{"entity-type":"item","numeric-id":243832,"id":"Q243832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782596$6CE8769A-0DCC-4B73-8A3B-88DCD3E7C8FE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e23cd61fb52044c0fb2903ade6fe3c7d224eeaf1","datavalue":{"value":{"time":"+2020-07-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q782596$E11FBA31-ADC2-4FD4-8EE3-58A92E9EDFE7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"015aa3a80393c706aff126f44bb03bf36f582d12","datavalue":{"value":"The paper deals with the Lyndon factorization (CFL) and the canonical inverse Lyndon factorization (ICFL) of words.   A Lyndon word is one which is primitive (not a power) and the smallest one in its conjugacy class (obtained by cyclic shift) for the lexicographic order. The Lyndon factorization is a factorization of a word into a sequence of Lyndon words in non-increasing lexicographic order. Such a factorization always exists and is unique. For an inverse Lyndon word (which is strictly greater than each of its proper suffixes) a new factorization, called inverse Lyndon factorization, was introduced by the authors in [Adv. Appl. Math. 101, 281--319 (2018; Zbl 1402.68143)]. A canonical inverse Lyndon factorization is one which uses inverse words as factors.  As the main result of the paper (Proposition 6), the authors ``prove an upper bound on the length of the longest common extension (or longest common prefix) for two factors of a word \\(w\\). This bound is at most the maximum length of two consecutive factors of \\(\\operatorname{ICFL}(w)\\).''   Apart from this result, among others, the paper states ``a property showing that substrings of the same word could share common factors of the Lyndon factorization (Lemma 5). This property could be extended to two words that share a common overlap to capture the suffix-prefix relationship between them. It is an open problem if Lemma 5 extends to \\(\\operatorname{ICFL}(w)\\).''  For the entire collection see [Zbl 1435.68034].","type":"string"},"datatype":"string"},"type":"statement","id":"Q782596$F0589C07-40F0-4A46-B955-87423C9B30DA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"88721db91438e5a4a75e8688d7b2c4f241fceae9","datavalue":{"value":{"entity-type":"item","numeric-id":590553,"id":"Q590553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q782596$39BAA3F1-B893-4164-A0D0-1CEB208FC6A1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782596$1ACD2F08-7FA6-4944-BBC6-F1CCB6FEE56E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4c2e03702daebccceae8196be8b8e65b5af4e27b","datavalue":{"value":"7225138","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782596$72FEC069-5FCE-4465-9D5F-1680CA0AD8C0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"09314b97c41035fd5c3138a114d545fb151a9c95","datavalue":{"value":"Lyndon words","type":"string"},"datatype":"string"},"type":"statement","id":"Q782596$CA076F1E-360B-4F2D-BCFA-7C68EB1F5CA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88fa40ef7fccc550b4c7d1004335ce6c676205c6","datavalue":{"value":"Lyndon factorization","type":"string"},"datatype":"string"},"type":"statement","id":"Q782596$93A7F71E-6973-4506-8C20-D65CF63648C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c2460a4ace89491b90caa93e816e60991d6c8719","datavalue":{"value":"combinatorial algorithms on words","type":"string"},"datatype":"string"},"type":"statement","id":"Q782596$B34D7F80-A033-457F-956E-35DC7E8CE8DD","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":"Q782596$B2B5FEA7-1302-4390-8BCA-B198A8EC5485","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4de9a8887b7e1cb83511a66ac19680c8d069ade4","datavalue":{"value":"https://doi.org/10.1007/978-3-030-40608-0_27","type":"string"},"datatype":"url"},"type":"statement","id":"Q782596$5A8EB21E-C0E7-4BBA-874F-B8945BC56F7B","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"16d3c63b0a45a789b14a5c8df9fb8c7752edf6ca","datavalue":{"value":"W3009111940","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q782596$FBDD75DA-58D0-42C8-AD87-29A7C904EB15","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60879a807b23dde495999c91ac88e8cb94304435","datavalue":{"value":{"entity-type":"item","numeric-id":1998861,"id":"Q1998861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2faee0b40370d93a761bc4ed3bfdd4600e01855d","datavalue":{"value":{"amount":"+0.88737124","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$CB8052F8-CD95-4130-9B1D-6409A7648A66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"194c0757a73151ab1e4fd9736ab67269402fbf30","datavalue":{"value":{"entity-type":"item","numeric-id":1795498,"id":"Q1795498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"04a9bfbda82d0a648f5b70172ff5cda42dc7d484","datavalue":{"value":{"amount":"+0.85865533","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$03618C13-C7E9-493C-8882-C1F7A972FD78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcbf71a728b2400b7a5dd3067862964faaea5a56","datavalue":{"value":{"entity-type":"item","numeric-id":3315005,"id":"Q3315005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2f59af15eb458f2386b5037c3b61ec57fb67691b","datavalue":{"value":{"amount":"+0.7900157","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$7CF2548B-9C8A-42D2-9884-DD0C7E22FD82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"da20802a017c6700219e002620319237afd07298","datavalue":{"value":{"entity-type":"item","numeric-id":1183603,"id":"Q1183603"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"720b79fd1e40e2f4cc42236b070e338a2e9cd7ab","datavalue":{"value":{"amount":"+0.7714158","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$CD7C4E3A-BBE6-4902-94A1-11B3F852586B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e33e3e9566ab16a02c5418f5a6fa890de643647","datavalue":{"value":{"entity-type":"item","numeric-id":4636645,"id":"Q4636645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c605d81bd513cc97836796eabc23e6b727918723","datavalue":{"value":{"amount":"+0.764602","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$D7708275-0F2C-4E7F-9AF0-21D9A068BFC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1855860e9560cf2301ad4ac256e037e3e131a26","datavalue":{"value":{"entity-type":"item","numeric-id":4412123,"id":"Q4412123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"86d10ad2107810efe6e691df3d166cc033b9445b","datavalue":{"value":{"amount":"+0.7631508","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$AADB9305-DD0E-4CE3-A1BD-71BAB7B02DAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3c6f1fc921b18ea1a3b737a1f9a4a655e75d795","datavalue":{"value":{"entity-type":"item","numeric-id":3758253,"id":"Q3758253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09a69c67ac9eb51ebceebc0a26b4dcac5ff4a667","datavalue":{"value":{"amount":"+0.75030375","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$94AE73CE-4C1A-4F83-B5FF-95C8DF84CB06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"451350f307c22752826389cfb09ce70296c2e148","datavalue":{"value":{"entity-type":"item","numeric-id":405567,"id":"Q405567"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7767f00313369a7199b24c6ed22056b9b4afc90a","datavalue":{"value":{"amount":"+0.7385084","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$322294D5-669A-4343-9290-AAC2F339426B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c7befcae10b5015c156b2d94ca4176ca604aa05","datavalue":{"value":{"entity-type":"item","numeric-id":4876360,"id":"Q4876360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"07da8f48f05963e21debb4a311f45e783f1d090b","datavalue":{"value":{"amount":"+0.7375071","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$348A537C-0147-4EA4-B36B-92DAA21E3A6F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0d47e95270f6ce0b4350cc512c9beedae37ad71","datavalue":{"value":{"entity-type":"item","numeric-id":3451100,"id":"Q3451100"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"de0d4335fff4a49c5fe585d08c622b4bf7aad183","datavalue":{"value":{"amount":"+0.73590857","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q782596$E9D1D7C8-5893-478F-BC42-29C6F6194915","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Lyndon words versus inverse Lyndon words: queries on suffixes and bordered words","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Lyndon_words_versus_inverse_Lyndon_words:_queries_on_suffixes_and_bordered_words"}}}}}