{"entities":{"Q441859":{"pageid":443626,"ns":120,"title":"Item:Q441859","lastrevid":61850004,"modified":"2026-04-11T02:05:29Z","type":"item","id":"Q441859","labels":{"en":{"language":"en","value":"A linearly computable measure of string complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6064143"}},"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":"Q441859$ACCDA057-F860-4C95-9542-121DB7613EE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e3a28ae5827e27d55620f7ffc56596f557729656","datavalue":{"value":{"text":"A linearly computable measure of string complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q441859$896345E8-61D2-47E1-8DA6-570C20B2AD14","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"702265d1cfc74b33eeafe74e667a02fa10fb4307","datavalue":{"value":"1255.68117","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$A211CB4E-60E7-49C6-BC39-65A2CCA1E4FB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7320a75ca6c22146c5127eb4e552d8313e94241","datavalue":{"value":{"entity-type":"item","numeric-id":235738,"id":"Q235738"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$DC514AEA-734F-4379-99F0-4227E3C161CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"659391255f12d15a8d02f2036589aadd145bbdc6","datavalue":{"value":{"entity-type":"item","numeric-id":385999,"id":"Q385999"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$BADC649D-BC4E-4EE2-84C2-818DF284E8F0","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":"Q441859$B81B9858-47A9-48FD-A4B6-70FBD20BB245","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"44f3e8b83609cf4e3eda11fc160cf4b0b2caf1b7","datavalue":{"value":{"time":"+2012-08-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q441859$C5C29250-3896-495E-BF1F-BBFA80C1BB5A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"d88999d16f9ee96585ecbdb7273517d02c350245","datavalue":{"value":"In this very interesting paper, the authors introduce the notion of the \\(I\\)-complexity of a given string, which counts the number of distinct substrings in it, and investigate its properties. They prove that this measure of string complexity is computable in linear time and space from the well-known longest common prefix array (LCP array), the companion data structure of the suffix array. They also introduce the repetitions array, which is a permutation of the LCP array, and develop its properties. It is shown that the number of strings with \\(I\\)-complexity up to a given value is bounded and a large family of strings with almost maximal complexity is presented. The authors prove that most strings have high \\(I\\)-complexity. Their measure of complexity is compared with the Lempel-Ziv complexity, their main differences are discussed, and it is shown that in spite of their very distinct behavior on infinitely many strings, their values are close. Finally, the authors discuss a number of open problems and ongoing research on \\(I\\)-complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q441859$002CFCCF-5427-4890-8EC6-4BAB7C6ECFEA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"3f9e311a53969bed982204d1446a9d77dda26ac9","datavalue":{"value":{"entity-type":"item","numeric-id":591667,"id":"Q591667"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$9097A8A3-2F23-48FA-B2A4-FD3EEBE79885","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$B76522E4-C52A-4052-A67A-93C93FD4048B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$7380A8FB-D51A-4451-8202-095A4AF3F39C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"9f6e12b05d81562621a24e261902662d41f3feb0","datavalue":{"value":"6064143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$C04230DD-B200-4DC0-A306-3DA3BA63F7F9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ca610e144594d9d4e3b6974a51e4b3ddf69c3bf2","datavalue":{"value":"string complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q441859$388D3CF6-5A11-4BE7-B282-C1B84CB3E404","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9dd5f26409163ea00d953c452775bbb96da624ca","datavalue":{"value":"description complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q441859$7EA8C6ED-35E4-48D7-9188-F1EE54A452F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"25ea58eacfffa2b23d702383ed3ad622dd47c3ae","datavalue":{"value":"Lempel-Ziv complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q441859$705EA7DF-D507-4875-86CE-E39193304A48","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":"Q441859$DFD0DD79-4036-4691-93C9-1C63C7743472","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"49b08c12cb2e861af12a3c00461c42836e2bc128","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.03.007","type":"string"},"datatype":"url"},"type":"statement","id":"Q441859$4FE5103A-75DD-4A69-ABBB-857C151C5F05","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4f88f494d329220ba8786b23834b59d70f21045f","datavalue":{"value":"W2078711260","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$A51A5A83-D492-4940-BBB3-0746F48598F8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"2964d6e361565a9f0add653f5c042cc0476b1825","datavalue":{"value":"Q61927022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$7F269E1B-5D52-46D4-AD73-44638F8B0E65","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8554198dba2e251d5f8524099f9569103d0e33c7","datavalue":{"value":{"entity-type":"item","numeric-id":3648816,"id":"Q3648816"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$B92D807A-CDBC-4822-898C-0D1B0D83F488","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c203909888fabf711e68a9afc67d2ca542da015","datavalue":{"value":{"entity-type":"item","numeric-id":3184666,"id":"Q3184666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$489912B9-7CCD-46BE-850F-8DFC91CBE9C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad72cac6df6c33dbeaea4ebb60f705206d729368","datavalue":{"value":{"entity-type":"item","numeric-id":1944170,"id":"Q1944170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$F4A854F5-BCA7-4929-8D2D-3D34BB7EDEE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a350a646df05af2cd765c289d28ce10d45e83b7d","datavalue":{"value":{"entity-type":"item","numeric-id":5834367,"id":"Q5834367"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$96391CE4-705E-47C7-AB6E-3F4E819E8D79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a2cb68d056b7b24e2a1fddc7d2a62a01a702744d","datavalue":{"value":{"entity-type":"item","numeric-id":2784486,"id":"Q2784486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$1E935F57-A8B1-4E4B-913E-1148618383A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"58bf0e27e1f13841a1d85e6f5666c81dca4c1528","datavalue":{"value":{"entity-type":"item","numeric-id":4964008,"id":"Q4964008"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$E3D9845C-5C45-4727-BFA6-A14E5F71906C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"688e530530b2aa80b106b3a8c0a385dbe89600f0","datavalue":{"value":{"entity-type":"item","numeric-id":4068087,"id":"Q4068087"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$3BF41CE7-9087-463D-B2D6-1FAF676DE49E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"08b0a309745c64acb47841d6e624171f61a9cfed","datavalue":{"value":{"entity-type":"item","numeric-id":3546722,"id":"Q3546722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$2B179737-04BF-4A32-ABB2-9065DE719942","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beac106230d15c7a88c85d207655035344307537","datavalue":{"value":{"entity-type":"item","numeric-id":2871083,"id":"Q2871083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$EBA2A058-7D91-4631-A841-13D8A39D5B78","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":"Q441859$3A785CC4-D8E1-41A7-B6D4-034F067A7D0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2c5f4a456f9910b4c4f2a1d73e4561be8a5dbc2","datavalue":{"value":{"entity-type":"item","numeric-id":3214803,"id":"Q3214803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$97605A04-DC9A-4E04-981A-154A1D58CB2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"51121593637420160072233354b18084ed2e40e8","datavalue":{"value":{"entity-type":"item","numeric-id":4105595,"id":"Q4105595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$AEB0AD69-978F-477D-9BFF-AC4D9B7D2732","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"550115941bea61e6912dfe13f182fc4df3a1d9c5","datavalue":{"value":{"entity-type":"item","numeric-id":5756683,"id":"Q5756683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$19307440-1D27-4806-B95D-E355E7D0B289","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"765e1a7b0cd5402f72cc273dc87f1f94470d841f","datavalue":{"value":{"entity-type":"item","numeric-id":3142586,"id":"Q3142586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$0F2597C6-F5DE-42E1-BA88-70BE3DB55A8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9ee90301292f993937476af8a941fa54b3796566","datavalue":{"value":{"entity-type":"item","numeric-id":2264549,"id":"Q2264549"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$9C4E952C-B02E-4DA0-A80D-B4B3AC7ECF92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b8425e8209e6312a4bbffa91ef01a2b5e5a251f","datavalue":{"value":{"entity-type":"item","numeric-id":4531381,"id":"Q4531381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$99964147-312C-4586-8807-3C5D513667B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"78f0cf2b8270f6087b7bc3862da42dbac9e1bf1f","datavalue":{"value":{"entity-type":"item","numeric-id":88168,"id":"Q88168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$D4C9C216-9DED-4DD5-80B8-50EB381BC490","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76e81b94e303e3a7768dfb4c39576c7d108a43e7","datavalue":{"value":{"entity-type":"item","numeric-id":4879210,"id":"Q4879210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$0FAD1D89-6E25-43AE-8187-46902E15AB1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bd5becf6b269d2da73d5affe1d576ca0555ebccf","datavalue":{"value":{"entity-type":"item","numeric-id":4337021,"id":"Q4337021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$3181005C-82AD-40F2-A57A-32704895FD2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0e57fccc8c00238fd458ec81341321c0921c881c","datavalue":{"value":{"entity-type":"item","numeric-id":4174617,"id":"Q4174617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$6E11BADF-B8C1-4960-A50E-CFF6624724E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55cfc0ff9590d7beb1ccb038cddeb12787b6740f","datavalue":{"value":{"entity-type":"item","numeric-id":5626617,"id":"Q5626617"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q441859$D22887FD-F322-45D7-AF12-65310AB44CE6","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"b32d93810a0d41bb892fbf9cbf98a727b1a5234c","datavalue":{"value":"journals/tcs/BecherH12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$723256C4-1E07-46F6-A7AD-085336D5DADC","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"95df45b43eeeebc20301eb3f284bc14b8d7c6ba1","datavalue":{"value":"10.1016/J.TCS.2012.03.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q441859$30400871-EB12-4D69-A3BB-DA473E3DC97A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff96dac6610beccbad4a123e63b648201cdcd9f2","datavalue":{"value":{"entity-type":"item","numeric-id":4531381,"id":"Q4531381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f34112d119d186d694ca3b7002c848659e39d24","datavalue":{"value":{"amount":"+0.8561321496963501","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":"Q441859$5CEC6EDE-228A-4E15-8957-9730AB19B463","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f020e64778d5b3d6886469cf918930006ac9205","datavalue":{"value":{"entity-type":"item","numeric-id":4681318,"id":"Q4681318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"35098d0ef27d5d1ce080eb347f4c574d5e5ed7a2","datavalue":{"value":{"amount":"+0.8078150153160095","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":"Q441859$D19CD5FB-4881-4460-ADB0-091DDCCCAD70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"43b98a98d6048ea4eb25854e9d0a80075f8e23a6","datavalue":{"value":{"entity-type":"item","numeric-id":2804173,"id":"Q2804173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6686f9d5d611616f6776c2c5c3656ccc043018f8","datavalue":{"value":{"amount":"+0.7858566045761108","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":"Q441859$9069D2DE-14D9-4A83-990A-22317A4005A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6780a473f2531033ed9ff794b00f2c819392e060","datavalue":{"value":{"entity-type":"item","numeric-id":4258669,"id":"Q4258669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8923fcdda1d2669949cc21d80771fbae2ab430e4","datavalue":{"value":{"amount":"+0.7717869281768799","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":"Q441859$1EF2A686-477F-401B-ADC7-0254341FFB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0d35318af26f6ae732442c1b3773196b9ade0786","datavalue":{"value":{"entity-type":"item","numeric-id":3814828,"id":"Q3814828"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8691e9286d580edb658d0cb0d9ab5cc1d8392203","datavalue":{"value":{"amount":"+0.7683757543563843","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":"Q441859$942276CF-7C0F-400D-BA84-56FE7131CD83","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A linearly computable measure of string complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_linearly_computable_measure_of_string_complexity"}}}}}