{"entities":{"Q1122979":{"pageid":1133728,"ns":120,"title":"Item:Q1122979","lastrevid":66816144,"modified":"2026-04-12T13:03:08Z","type":"item","id":"Q1122979","labels":{"en":{"language":"en","value":"New bounds for perfect hashing via information theory"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4108143"}},"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":"Q1122979$8EB52F2B-BA1F-45D0-BAFE-ADC1DCF32B41","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5784abbc4ae7b54d8e307ec1557290920b89fdbf","datavalue":{"value":{"text":"New bounds for perfect hashing via information theory","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1122979$67918D19-0476-4DF4-AC05-15738E9BCD44","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28f7f63d73a184cc768051702840a2e97d972e68","datavalue":{"value":"0676.68007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122979$8FBF2903-AAE9-4BF3-8BD7-787F6C437AD2","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6295ec5718545f3fab78274e3270fc54bbbdcd94","datavalue":{"value":"10.1016/S0195-6698(88)80048-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122979$E5E655A4-95F6-4EAE-A8DA-F85207AC4C26","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aedf720352fcca932fab3523c4bbcafd7c4c7cdb","datavalue":{"value":{"entity-type":"item","numeric-id":1104176,"id":"Q1104176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122979$DB35AC51-516B-4D88-8A1F-26E981C31199","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122979$0C112A07-D573-480A-97BC-E0FB623A7078","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1122979$9953462B-2A1E-41F6-9A08-7F7C10398167","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5fcc1ba74f5c934a9599978b97b1cf8e981a80a2","datavalue":{"value":"K\u00f6rner and Marton consider the problem of finding bounds for the largest size of a k-separated subset for a family of perfect hash- functions. By extending an information theoretic bounding technique based on graph entropy to more general structures they are able to improve the Fredman-Koml\u00f2s [\\textit{M. Fredman} and \\textit{J. Koml\u00f2s}, On the size of separating systems and perfect hash functions, SIAM J. Algebraic Discrete Methods 5, 61-68 (1984; Zbl 0525.68037) bounds in several cases: They give a new lower bound for the size of a 3-separated subset on a 3- element alphabet, namely  \\[  1/t\\quad \\log N(t,3,3)\\gtrsim 1/4 \\log 9/5  \\]  and they present better bounds for a subclass of problems which includes a 3-separated subset on a 3-element alphabet as a special case. For all k-separated subsets on k-element alphabets with \\(k>3\\) they could not improve the Fredman-Koml\u00f2s bounds.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122979$0A5D4201-1D6A-4776-984D-9BFD811EB1C9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"14cf74de25853c940589b125137b792dfb2d092b","datavalue":{"value":"68P05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122979$9E3F2B97-DF54-4633-B76A-EB34802B13D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122979$CE916F7A-4420-4D28-8EA9-0680AF79FC7E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f7eeec2d04c0033bd26de98703f82575bb5e24ee","datavalue":{"value":"4108143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122979$76ED2E2D-0FE6-49DF-956B-321786C12206","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5d738ce07b4e2d927b4c22f360defbb5172d4f48","datavalue":{"value":"perfect hashing","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122979$6F1F0D82-AA1E-4D1D-A294-B112C25CAE31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88eb8389684a2f856fb60b2fc49309d8a3aeeca3","datavalue":{"value":"information theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1122979$60E7D2A8-824A-4F48-A767-97FFED48D5CE","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":"Q1122979$D7AA373D-8D6F-490F-B7CF-B69224D286A7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"49c68f48b66d4d04696fdb7856ffc7754b328bdb","datavalue":{"value":{"entity-type":"item","numeric-id":3038628,"id":"Q3038628"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122979$DFE5CA47-DF1C-475B-AD31-2FA4CCBE8C97","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fe1f566242e8ecf1db61864069dff52b7764a7f","datavalue":{"value":{"entity-type":"item","numeric-id":3739153,"id":"Q3739153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122979$59FD2C94-6DF3-4907-AF8A-D10D701C8A7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"34018e0596996ff05bb65cc90b8bc3b77ba0da66","datavalue":{"value":{"entity-type":"item","numeric-id":4053473,"id":"Q4053473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122979$71AA9361-7D80-4C47-8CF3-B4EDC201B3A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0d0b2fce2b242cc432634970b75f6a32544e3aaa","datavalue":{"value":{"entity-type":"item","numeric-id":4156696,"id":"Q4156696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122979$E3EA0C5F-9AE4-4DE1-8BC8-7DA68ACEEA24","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1e5088ff6615085aa7066258e3d7e05a4b6d90aa","datavalue":{"value":{"entity-type":"item","numeric-id":3726012,"id":"Q3726012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1122979$B2EEC368-0E88-4F21-AA83-B83754B50007","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"70000f1fa2f422ab09b117abb318b2f11d1d4cb0","datavalue":{"value":"https://doi.org/10.1016/s0195-6698(88)80048-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1122979$85392D8A-88AB-41F6-962E-131B41587126","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fe75ebfc38fba82db69884869c94f7431481a589","datavalue":{"value":"W2056884477","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1122979$1240F7B6-649E-4118-8AA5-2EE4798FCDA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33fde2892b6db45e8052ff6ede40b337aa826b22","datavalue":{"value":{"entity-type":"item","numeric-id":5939232,"id":"Q5939232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f48c1b0fac6b7843f379dd632d7d3c9fe9d5d643","datavalue":{"value":{"amount":"+0.8451754450798035","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":"Q1122979$6B12924C-C29C-452C-80D0-49912515BDA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ba3a75a4d70f2a7b43b43a3b9d911b38d852715c","datavalue":{"value":{"entity-type":"item","numeric-id":2217492,"id":"Q2217492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ff20d6b288f8cb7c65c8bf1f25ff4a0b5840e879","datavalue":{"value":{"amount":"+0.830856442451477","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":"Q1122979$2285C17D-C138-4D05-9F90-E6C4E7D0247E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b4ec9f12fab2d0d320f440eb72c0a93987304bd4","datavalue":{"value":{"entity-type":"item","numeric-id":2077264,"id":"Q2077264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f313a1425fe67135c84b2875ad0bef3271873a87","datavalue":{"value":{"amount":"+0.8278821110725403","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":"Q1122979$99C2C48D-39E8-4B1B-BF3D-75F9D8EC1D6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47063349843ebebb8a0ea56198d3f1f633ae0b9c","datavalue":{"value":{"entity-type":"item","numeric-id":3739153,"id":"Q3739153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23d35eb034c1456663a2d3fe71e9999b5476341e","datavalue":{"value":{"amount":"+0.8233562707901001","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":"Q1122979$6C55271C-EC31-4490-8341-C0BD170E7C9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed5465d74d35d335c8ba57c36774c513efb0bbf1","datavalue":{"value":{"entity-type":"item","numeric-id":369437,"id":"Q369437"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"119a6053bac1c23f4265d1df9b464f47dcd0a119","datavalue":{"value":{"amount":"+0.797999382019043","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":"Q1122979$9440A018-DF65-42D3-AEAD-A53213DD0A34","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"New bounds for perfect hashing via information theory","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/New_bounds_for_perfect_hashing_via_information_theory"}}}}}