{"entities":{"Q314398":{"pageid":316165,"ns":120,"title":"Item:Q314398","lastrevid":60927408,"modified":"2026-04-10T20:02:51Z","type":"item","id":"Q314398","labels":{"en":{"language":"en","value":"Twins in words and long common subsequences in permutations"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6627900"}},"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":"Q314398$96856B12-2512-476D-A914-8E5DB990DBBB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2e1d36cb06cfc4909583384863c7aaaaa8ac86c3","datavalue":{"value":{"text":"Twins in words and long common subsequences in permutations","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q314398$216E61F4-0E9E-4DBB-B4C7-CA1225272836","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d4f6eb716431f3e5e8e9defa930b56e9e731e2e","datavalue":{"value":"1354.68213","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q314398$E2040618-AA9C-4E51-B603-2FE4DDA7CDBA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"518e0f7acf819031e0f364a9043c47b119d7fa2e","datavalue":{"value":{"entity-type":"item","numeric-id":314396,"id":"Q314396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$5B186E77-DC39-4CCC-B190-ECC5CC39EC9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a07622aaa7f989808487d2045fc6fbd28f8efe4","datavalue":{"value":{"entity-type":"item","numeric-id":314397,"id":"Q314397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$75404C16-95A0-4D66-AB90-688FE986B6E1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$FBEE68F6-5A69-4EFA-A09D-F87F61C4DCA1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4b754de66362aae284dabb1b78cfda06e1f60d64","datavalue":{"value":{"time":"+2016-09-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q314398$ABBB51C0-7F33-46BC-AEBD-95B7A68D2F00","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"15b79d77a69af2878ff6f194ce1e87ba370741bc","datavalue":{"value":"https://arxiv.org/abs/1307.0088","type":"string"},"datatype":"url"},"type":"statement","id":"Q314398$8D846F33-F40D-4783-A77D-92BEB50F361C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c00afb0209d268fed5f1dfe1c324f7167cd7e84f","datavalue":{"value":"Two subsequences of a word \\(w\\) are said to be twins if they are equal as words, and they do not contain a letter from the same position in \\(w\\). Let \\(\\mathrm{LT}(w) \\) be the length of the longest twins contained in a word \\(w\\) and \\(\\mathrm{LT}(k,n) \\) be the minimum of the values \\(\\mathrm{LT}(w) \\) for words \\(w\\) over a \\(k\\)-letter alphabet. The twin problem of Axenovich-Person-Puzynina is to determine how large \\(\\mathrm{LT}(k,n)\\) is. The authors show that \\(\\mathrm{LT}(k,n)\\geq3^{-4/3}k^{-2/3}n-3^{-1/3}k^{1/3}\\) and, for \\(k\\geq3\\), \\(\\mathrm{LT}(k,n)\\geq\\frac{1.02}{k}n-o\\left( n\\right)\\), the former being a better lower bound for large values of \\(k\\). Further they prove that \\(\\mathrm{LT}(k,n)\\leq\\alpha n\\) for a constant \\(\\alpha\\) depending on \\(k\\). They use in their proofs a generalization of the result of Beame and Huynh-Ngoc, which asserts that for any three words being permutations of the letters of a \\(k\\)-letter alphabet, the longest common subsequence of any two of them is of length at least \\(k^{1/3}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q314398$7EC78764-A343-4F20-88EF-02FCE970CC21","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q314398$CC1DF796-A4D8-4337-ADEA-823915FB84B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6247f04fad65d359a20e559b3e9499d6219d492e","datavalue":{"value":"05A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q314398$4B370462-980A-4060-AAE4-E581C475AA9A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9d2bbcda92552ae479cbd79a9d2dd9ce2f3346fa","datavalue":{"value":"6627900","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q314398$963888D9-FE85-485E-9D56-BE7DDBF6643A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7927a0b55e08c3b5cc4ab15b6c8712a0b3c27484","datavalue":{"value":"word twins","type":"string"},"datatype":"string"},"type":"statement","id":"Q314398$4FB17BDD-BB03-4A3D-BADB-D0B3E256A9C5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4d5251c07b1862f0aa75175702ebd2e7c1923d32","datavalue":{"value":"bounds for twin problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q314398$56A374C0-1B89-4C72-BDAC-48398E51E342","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3c4dd8869ddda693ef8d2da6d96c7c4dce2e5744","datavalue":{"value":"permutation word","type":"string"},"datatype":"string"},"type":"statement","id":"Q314398$A8DB6BBE-34BB-4681-B5B3-A8B519349991","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"1709c704ca283e54ed81f03ca60bb288bae9e53d","datavalue":{"value":{"entity-type":"item","numeric-id":355508,"id":"Q355508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$D8E4ACC6-6CA5-4172-A1A7-266D4F19067E","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":"Q314398$D72CCB43-6646-40C6-B203-31DF62143D40","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac9efccfd5e50736ec44e7dc37b5212d068e0cc8","datavalue":{"value":"W1793292512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q314398$0596F8B3-7BE1-4DC3-A75A-E60451A6989E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8cb61edaa43e8a9d26ed06403cb95d1cb5ce3b7","datavalue":{"value":{"entity-type":"item","numeric-id":1946730,"id":"Q1946730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$9EC5CFC3-45C2-445A-8C67-A75F63057EDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"52afa7bd6bb478f700f9914e8cf74ba8028fe212","datavalue":{"value":{"entity-type":"item","numeric-id":2766428,"id":"Q2766428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$92B5B8A6-A62F-410F-9C81-4009D4FF5408","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d1644967e2dbbe7733ee66148e02bfa124d28aa","datavalue":{"value":{"entity-type":"item","numeric-id":2947560,"id":"Q2947560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$0303BAB2-AB0E-45A2-9333-DB984E3520EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50e5deba5a3accd2c72a5574a35e965a31ef0061","datavalue":{"value":{"entity-type":"item","numeric-id":5246103,"id":"Q5246103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$0314B773-E8F6-45F7-9E00-6CFA0468DA6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b9df05cfadd429c919e2c6f49687688f6d1327d","datavalue":{"value":{"entity-type":"item","numeric-id":5759552,"id":"Q5759552"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$3F26C9BE-82BC-4DB5-BEF3-CC0268799311","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7ffc8e5e3ba907200afefe4289c919f680caf88","datavalue":{"value":{"entity-type":"item","numeric-id":2573406,"id":"Q2573406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$27063DEE-06AB-4996-864B-B65EC4FCFB59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f28c269329b95a99d792f6efe0146cde9c720d22","datavalue":{"value":{"entity-type":"item","numeric-id":1240509,"id":"Q1240509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q314398$AC8E8D21-B517-41B6-92C5-7663776DB68D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"e331658deaf54913153627599ff359335f29b79f","datavalue":{"value":"10.1007/S11856-016-1323-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q314398$555C2EF4-08AF-4D5E-8B0E-77C0ACCE9719","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f19c3e0d094fe1ec3d170ca8b99310fa312e713b","datavalue":{"value":{"entity-type":"item","numeric-id":5130571,"id":"Q5130571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a07a2fbe74e012979332ba39e49ea978f7a4059c","datavalue":{"value":{"amount":"+0.8338800668716431","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":"Q314398$653F26D8-2CB3-46C3-A150-E332F4E10C4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4190a89df1d89985f0e9dd61b3a4c91fed83b469","datavalue":{"value":{"entity-type":"item","numeric-id":2048547,"id":"Q2048547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a37d92955c3664cc4524947bfe4c1a78ac3b84a","datavalue":{"value":{"amount":"+0.8319270610809326","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":"Q314398$C46DEBE1-DB88-44B7-BB42-2B6A2EEB3D28","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"15ed2812438757c054db6fe88334d51d39e39334","datavalue":{"value":{"entity-type":"item","numeric-id":825967,"id":"Q825967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f1b1dd74b06049b13413145ebc0eaa405d8a8dc4","datavalue":{"value":{"amount":"+0.7899885177612305","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":"Q314398$46786D3A-A26D-446D-BF53-C1D73CB62256","rank":"normal"},{"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":"dd2c22fd683dce2197ccaa534f6abf43cc501337","datavalue":{"value":{"amount":"+0.7663775086402893","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":"Q314398$6F2AC641-1A42-41D4-BE06-C1573F179DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5679770552de89aa4457a074d586507734fd747b","datavalue":{"value":{"entity-type":"item","numeric-id":1946730,"id":"Q1946730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9d2251b97b76b854ed5fb4cb7c4e18351b80547","datavalue":{"value":{"amount":"+0.7568660974502563","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":"Q314398$C4955E62-D254-4EE1-850F-6FC5D0EF8BEC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Twins in words and long common subsequences in permutations","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Twins_in_words_and_long_common_subsequences_in_permutations"}}}}}