{"entities":{"Q1820127":{"pageid":1830869,"ns":120,"title":"Item:Q1820127","lastrevid":71358360,"modified":"2026-04-13T21:42:57Z","type":"item","id":"Q1820127","labels":{"en":{"language":"en","value":"Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3993446"}},"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":"Q1820127$5AED52F6-9739-4027-B424-2944D8FB71D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8ea7e99a53bd1e5d10471ce82d7b9319ee20975a","datavalue":{"value":{"text":"Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1820127$E1ADD961-744D-471D-8449-8AC9DB5EFC9A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a0586684dae45ec1b96bbf5eda1ad12d43517dbc","datavalue":{"value":"0613.94006","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820127$96270DBC-6F6F-4F21-828F-52F8ED7518F1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b906dd3e69327cfccc6f1c244369ce690e434fa2","datavalue":{"value":{"entity-type":"item","numeric-id":174177,"id":"Q174177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1820127$98997EB2-3218-46A5-88E0-8EF66B85A5EC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-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":"Q1820127$E7EA13D8-A91B-47F4-9738-860433EAB353","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba980a136baa610e6a8daa1fe0f9e7fc276ca822","datavalue":{"value":"We consider the problem of noiseless coding of combinatorial (nonstochastic) sources. The cost of the optimal code is shown to equal to the Hausdorff dimension of the source. The same problem is solved with algorithmic constraints on the code in two settings: coding and decoding realized by Turing machines and by finite automata. The lower bounds on the cost of the code in these cases are expressed in terms of the Kolmogorov complexity and the quasi-entropy, respectively. Optimal codes are constructed for sources generated by formal grammars.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$6A2D5706-E185-4402-A32F-92536BB06CD3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5b666eafad69c33f38b5f75028993bcb016a6d06","datavalue":{"value":"94A29","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820127$24CD53D6-AAC5-4119-9F4B-C129221F9E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820127$5FD736BE-893D-4AB6-A18A-1B0BFE9F982D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820127$C8CE2204-83C0-4E61-B136-AFE19034EF78","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"dbc0d1391e667eba51689657b4a3c6ab9a32b6bf","datavalue":{"value":"3993446","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1820127$28672955-F5BC-4D71-9419-5A8BAB1CA9EF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2884d65c4df04b109d2bc593177dcbbc6be614c4","datavalue":{"value":"noiseless coding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$889DDDF7-D65D-4693-8586-219C470AA925","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f03b7aeddd20e83bfd6b2dfa76fcb5dc3f7fb14e","datavalue":{"value":"cost of the optimal code","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$747A20A3-051B-4370-8CA1-C623D3657247","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4b2518fecb1c0b57735793eae5817ca06057a14d","datavalue":{"value":"Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$679CC9DB-939A-495D-BFD8-CB63DBBC3A9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$3295B9A4-A6B4-4107-ABAD-CD11CF1F8740","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$08A1DB5B-5544-458F-BE7F-5D98A6930920","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6f9bb5fff59214538677fd3c23430d33d2e8f784","datavalue":{"value":"quasi-entropy","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$4E7A6B0D-3E4D-4C96-ADB8-D2AF72195DE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6e0e46546198556caf5915d83d9b5ae6980226b8","datavalue":{"value":"sources generated by formal grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q1820127$5538EDBC-993F-4956-A15A-54F391DF55C8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d3f8d1cee335cbbee1704671914a85e4c5a1c3e3","datavalue":{"value":{"entity-type":"item","numeric-id":522932,"id":"Q522932"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1820127$0278E43E-354A-443C-BA22-384CDECE3C21","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":"Q1820127$86036DCC-B820-4A17-965F-DE5C69E5F1F0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c1005f54a760f4636f3bde58ce73e79703a7482b","datavalue":{"value":{"entity-type":"item","numeric-id":3705346,"id":"Q3705346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"862e523f50dfa0e154d1fc77a0d77ea2c45d7a6a","datavalue":{"value":{"amount":"+0.898759663105011","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":"Q1820127$BB8410DF-9AED-430D-9DF5-48BAFB284BF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31d836174b040f8182b5c2195cbdf8c8d21a9fe4","datavalue":{"value":{"entity-type":"item","numeric-id":3547685,"id":"Q3547685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bdaf7e84e4514e74ea0ba7bb8d9c5b77d8f5031d","datavalue":{"value":{"amount":"+0.8694758415222168","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":"Q1820127$94543FA3-66DD-49DE-9893-72138BADE8C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8296c8a6313735317f9c9b2facaecd5ada706cbc","datavalue":{"value":{"entity-type":"item","numeric-id":3765699,"id":"Q3765699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8bc19a4c4a5ab578361eb73197f169f210c62d02","datavalue":{"value":{"amount":"+0.8101125359535217","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":"Q1820127$521F3F6E-6C90-48FD-BB95-E7AFCC5A24A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"891c285f8e6c234b33d720d903789d39c2b39ea4","datavalue":{"value":{"entity-type":"item","numeric-id":3758710,"id":"Q3758710"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9fad7333e8e5d1f720750e14a8ae773698938e7d","datavalue":{"value":{"amount":"+0.784335732460022","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":"Q1820127$3582CFA4-69A5-4CA4-8E85-C5DC8620BBFE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"16de165a48cb8b50104f30fd23fda6d974e9056c","datavalue":{"value":{"entity-type":"item","numeric-id":4770323,"id":"Q4770323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e5829976059491abfe24a7d2bb102cf8fd0dce4","datavalue":{"value":{"amount":"+0.7804317474365234","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":"Q1820127$2449DCB1-3DC4-4B6C-A0A7-5EEEBD7E70A7","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Noiseless coding of combinatorial sources, Hausdorff dimension, and Kolmogorov complexity","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Noiseless_coding_of_combinatorial_sources,_Hausdorff_dimension,_and_Kolmogorov_complexity"}}}}}