{"entities":{"Q1647840":{"pageid":1658581,"ns":120,"title":"Item:Q1647840","lastrevid":74026308,"modified":"2026-04-14T18:06:05Z","type":"item","id":"Q1647840","labels":{"en":{"language":"en","value":"Computing longest common extensions in partial words"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6894871"}},"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":"Q1647840$1FBA9456-2485-47FB-ACC7-2FCC3C954EE2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4295f3e610116a0e44442a173e4704fa1f483f09","datavalue":{"value":{"text":"Computing longest common extensions in partial words","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1647840$2425FC06-B371-473D-BC2C-A5C7DB791C41","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7fc2bc8840275cc89404f0a5f87df542a8c0c2a6","datavalue":{"value":"1393.68136","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1647840$C86753B5-89D9-42F3-A9AA-1521522C1774","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e53255bd22b5553843b3b4c1a51d83b6732157f4","datavalue":{"value":{"entity-type":"item","numeric-id":1621571,"id":"Q1621571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$1920C298-208C-4DF6-AC4C-E8D416FE62F8","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$D161C2AA-F66C-4C65-BDD2-6D17F6A32838","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c8a780e74b0fc20f5c27aee56d09c8997e1b03d9","datavalue":{"value":{"time":"+2018-06-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":"Q1647840$E908B36C-2ECD-4363-9874-24FCC41D9891","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"03d9906f5bf5b2d3a030b0dc44f59668b976ab37","datavalue":{"value":"The paper builds upon a conference paper by the first author et al. [Lect. Notes Comput. Sci. 9538, 52--64 (2016; Zbl 1393.68137)]. A partial word over a finite alphabet \\(\\Sigma\\) is a word over the extended alphabet \\(\\Sigma\\cup\\{\\diamond\\}\\), where the symbol \\(\\diamond\\) is referred to as a hole. Two partial words \\(a_1\\dots a_n\\) and \\(b_1\\dots b_n\\) are said to be compatible if for each \\(i=1,\\dots,n\\), either \\(a_i=b_i\\) or \\(\\diamond\\in\\{a_i,b_i\\}\\). The Longest Common Compatible Extension (LCCE) of a pair \\((i,j)\\) of positions in a partial word \\(w\\) is the longest factor of \\(w\\) starting at \\(i\\) that is compatible with a factor of \\(w\\) starting at \\(j\\). The average length of the longest common compatible extension in all partial words of length \\(n\\) over an alphabet of cardinality \\(\\sigma\\) with exactly \\(h\\) holes is denoted \\(\\mathrm{\\mathtt Avg\\_LCCE}(n,\\sigma,h)\\). The authors first prove (via direct but rather lengthy calculations) that for any fixed \\(\\sigma>1\\) and constant \\(h\\geq1\\), \\(\\lim_{n\\to\\infty}\\mathrm{\\mathtt Avg\\_LCCE}(n,\\sigma,h)=\\frac{1}{\\sigma-1}\\) (Theorem 3.11); this proof has already been outlined in [loc. cit.]. Then the authors consider a probabilistic model in which the holes in a partial word are identically and independently distributed, i.e., any given position is a hole with some probability \\(p_1\\). They prove that for large values of \\(n\\) and fixed \\(\\sigma\\), the average length of the LCCE over all partial words of length \\(n\\) over an alphabet of cardinality \\(\\sigma\\) approaches \\(\\frac1{\\sigma-1}\\) as \\(p_1\\) approaches 0 (Theorem 4.8). In particular, \\(\\lim_{n\\to\\infty}\\mathrm{\\mathtt Avg\\_LCCE}(n,\\sigma,h)=\\frac{1}{\\sigma-1}\\) whenever \\(h=o(n)\\). The paper also presents some experimental results.  Reviewer's remark: \\textit{B. Bollob\u00e1s} and \\textit{S. Letzter} [Eur. J. Comb. 68, 242--248 (2018; Zbl 1375.05006)] have established a similar result: \\(\\lim_{n\\to\\infty}\\mathrm{\\mathtt Avg\\_LCCE}(n,\\sigma,h)=\\frac1{\\sigma-1}\\) whenever \\(h=o(n^{1/3})\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1647840$6C032244-84F1-4EED-BC55-C9A8B6383F4C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1647840$9909A5F1-A826-4A8D-B1DE-84DEB9CA8ACB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1647840$DD181A7F-0D16-4EC3-89CA-B7445B067EDB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"165da8c3c481a6dc2d4b2facad1c79564200d6e5","datavalue":{"value":"6894871","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1647840$DB001C1A-8227-4E93-B17F-A4690C0B08A3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"665bb6b521670920ffccf875b8511ad8132838e1","datavalue":{"value":"partial words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1647840$9E328321-0D42-4603-8255-FB9FC99B3FDA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0ee04611d134923833d0dbcd806423b8bf04280e","datavalue":{"value":"longest common extensions","type":"string"},"datatype":"string"},"type":"statement","id":"Q1647840$294FD1DE-C884-4804-AD22-EC95DA9B6CDB","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":"Q1647840$73E4E468-7334-4EE2-AE01-DFF5B27E0D2B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"60a450693991f822ccb4ebd3e2e9f7c7b3e77fc6","datavalue":{"value":"https://doi.org/10.1016/j.dam.2016.06.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q1647840$DC6F02DF-025A-461B-AAFC-8A60E6C3F837","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"451a33af046f64d65184d4b7203a19311a070ded","datavalue":{"value":"W2472252664","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1647840$252DC4BF-99D6-4A4D-B21F-FA0CDCB605AD","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"972a8bf34e7833efe7d50db13efe7b7a685cc396","datavalue":{"value":{"entity-type":"item","numeric-id":4508365,"id":"Q4508365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$8801B085-356C-42AD-A6F6-637CB197EFDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"39a0a1b8afd8cd1d035a0e789447df73b70c8351","datavalue":{"value":{"entity-type":"item","numeric-id":4032934,"id":"Q4032934"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$159E8F2A-A344-4E56-8A8E-B69EC23DFB82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d594e497d0326ebbb421520b11fc2f462405bb4f","datavalue":{"value":{"entity-type":"item","numeric-id":2798218,"id":"Q2798218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$2B845E6A-612C-40D5-9B74-EDAEC14FD756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96c04d004105695103b8feb11f863615af002ffb","datavalue":{"value":{"entity-type":"item","numeric-id":4910455,"id":"Q4910455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$7F675CEC-51C3-4C73-B421-52F4068BC2BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3f4b1350b8ddd1c2490e736214ad948af23dda8c","datavalue":{"value":{"entity-type":"item","numeric-id":491152,"id":"Q491152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$9C8C59D2-CA55-4AC3-BB8F-BA3A24A3C4C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"023a72e5e5e999eae4a5008df1248fe59e8a4da2","datavalue":{"value":{"entity-type":"item","numeric-id":5307491,"id":"Q5307491"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$7EB16A1E-E4BA-4D41-8C5A-3293E5AA2CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8d4b82a0cf32ac8ebfb8553011dbf7c76c0842ac","datavalue":{"value":{"entity-type":"item","numeric-id":5369537,"id":"Q5369537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$2E6E30BF-ECB8-4FCE-9B04-B558432A95FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138d808c1a0d7bbfa300ea1020e86219b9fb4bf4","datavalue":{"value":{"entity-type":"item","numeric-id":4229812,"id":"Q4229812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$1C3ED030-76BC-481B-8027-68F48FE54CDE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"366ee523b5cdcd436b5b065c10d631b485dfc7c6","datavalue":{"value":{"entity-type":"item","numeric-id":1765295,"id":"Q1765295"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$15124CB2-7AE3-45A6-A704-71E165A4EA50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"05e150681c1d0241ecb463ace4c088cbd7d131cd","datavalue":{"value":{"entity-type":"item","numeric-id":3319776,"id":"Q3319776"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$A864D77D-C176-483D-8268-B67595AC9979","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1133aaa95f047d80bb310c4a44bce4b837abfc55","datavalue":{"value":{"entity-type":"item","numeric-id":616995,"id":"Q616995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$27C482AD-F07F-49BA-8C1D-E50304B69A23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c41e579a2f34380a95d05f378303a677e949e9e4","datavalue":{"value":{"entity-type":"item","numeric-id":4449231,"id":"Q4449231"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$500A7367-A7B5-45A8-B24E-2A554ADB59F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be14d5f113a4a5aff2137cc72f65204de28e4dd7","datavalue":{"value":{"entity-type":"item","numeric-id":4547749,"id":"Q4547749"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$BB9859E9-37D2-45D2-888E-5EF8A5BC91FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d51596fb91540050bedd3bf44f87390aa2b76f2","datavalue":{"value":{"entity-type":"item","numeric-id":4203810,"id":"Q4203810"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$E1935EEA-3DED-4D64-BF10-D61E0C8DB6BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d542fa11c132f1cf082a7e35ae97bc38e66c51f","datavalue":{"value":{"entity-type":"item","numeric-id":3339319,"id":"Q3339319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$0314455B-E709-4923-87DC-1D22CD51A46F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c855d6bb0d690e74f7619c66963fca7594379f9","datavalue":{"value":{"entity-type":"item","numeric-id":1099955,"id":"Q1099955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$3A166079-B4FD-4A76-9B3C-4BFF728E0335","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5837867e98a618d52ced5a6f2437b38b50f0adc4","datavalue":{"value":{"entity-type":"item","numeric-id":3823152,"id":"Q3823152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1647840$4C2ACF16-E086-4D81-B946-571E0A305F90","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c9afe5ae8cee3b01b09281aeb5ca7c77901fdf5b","datavalue":{"value":"10.1016/J.DAM.2016.06.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1647840$A708B34A-2C5E-46A6-87E6-259C1F7EC266","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d1b95409890bea502368873d25997cd973c1b38e","datavalue":{"value":{"entity-type":"item","numeric-id":2798218,"id":"Q2798218"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ae8c8f9d54cbcbdc405808e1b6572756f94eb13","datavalue":{"value":{"amount":"+0.9834097623825072","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":"Q1647840$082556A1-97D1-40A9-B7F3-9C73313FE03F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79e2ffeb5211fa110584c9ebea7b457ab5443a69","datavalue":{"value":{"entity-type":"item","numeric-id":491152,"id":"Q491152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d9f350816468e2bed9db1a70b163d6517662459","datavalue":{"value":{"amount":"+0.8656893968582153","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":"Q1647840$B305C85D-3F43-4EE9-86BC-80C1E20ACF67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9db005923b34d698a7b822da7c026a2c78dc4672","datavalue":{"value":{"entity-type":"item","numeric-id":1678103,"id":"Q1678103"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1dd343a9cf4def9403df0b2098297972ec99f458","datavalue":{"value":{"amount":"+0.8485654592514038","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":"Q1647840$A34043C2-A370-4EBD-BD5F-0801107DA601","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b582b030046fc65e271ff6956a521e293143bb1","datavalue":{"value":{"entity-type":"item","numeric-id":616995,"id":"Q616995"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"46e675e549305eb247b1637bf8bf56e9845bae25","datavalue":{"value":{"amount":"+0.8252660036087036","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":"Q1647840$9B88FFF4-D0C6-4362-9E6C-BED974FAA06C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04ebb1858a722368a0a62cfc63ce4a89d981bcc7","datavalue":{"value":{"entity-type":"item","numeric-id":4910455,"id":"Q4910455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9926d3eb662e8f9ad0d8e0ca53eda03cb34dc54d","datavalue":{"value":{"amount":"+0.7924700379371643","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":"Q1647840$7879C9B1-5A3C-4422-B20B-53F9556D506A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Computing longest common extensions in partial words","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Computing_longest_common_extensions_in_partial_words"}}}}}