{"entities":{"Q1184988":{"pageid":1195737,"ns":120,"title":"Item:Q1184988","lastrevid":66791502,"modified":"2026-04-12T12:53:06Z","type":"item","id":"Q1184988","labels":{"en":{"language":"en","value":"Nonuniform complexity and the randomness of certain complete languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 35365"}},"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":"Q1184988$FBAE60A2-4C16-41CA-AA07-5FA6E030E6A5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"15acddc95ce2970a6e1f02ce9e5685d863520c6e","datavalue":{"value":{"text":"Nonuniform complexity and the randomness of certain complete languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1184988$5EAB8C37-71E8-445D-87E0-D95AF882D362","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0d22c0852972ad284fb63eb0fe39f5eac6600c02","datavalue":{"value":"0755.68078","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184988$5E92560B-9975-4E3D-9358-3022C7388146","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"55ea6e689d9204049a6d3d0c2da3ebe793ceaa70","datavalue":{"value":"10.1016/0304-3975(92)90340-L","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184988$756DD472-0807-48D4-9DBF-329C4CFCE612","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f11d29d2cbdb03c4d5ff90d92cbc2f1d658ba97d","datavalue":{"value":{"entity-type":"item","numeric-id":391197,"id":"Q391197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$A89D1B9C-A8D5-4135-AEE8-0D7157635CF4","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":"Q1184988$2AB68045-D50D-4101-9E2C-1464221CAD72","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1184988$58F36276-F847-4CB2-A7D8-7A5A1C6FAB7C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b92343a9a3770c6817e47753d1fbf535b49ced6","datavalue":{"value":"The author continues his investigations of the randomness properties of various languages. Using basic approaches of A. Church on infinite random sequences and A. N. Kolmogorov on finite random strings, the author exploits his earlier results on several concepts of random languages and properties of complete languages in terms of these randomness concepts from the complexity viewpoint rather than, say, the cryptography viewpoint.   The author proves several interesting results that clarify the difficult relationships between resource-bounded Kolmogorov complexity and other non-uniform complexity measures defined by grammars or automata size. In the process, the author vindicates the naturalness of the use of the notion of weakly random languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184988$C4AB6007-0566-4F4A-BB8C-E5D9242186DD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e243fd7c22ca7737465c92434b0b01e09fe89c42","datavalue":{"value":"68Q30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184988$01C74596-B988-4F7B-870D-C7E6BCDB1159","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c636094cc8b933189eabd7c009d327f829bc6ac4","datavalue":{"value":"68Q42","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184988$1F73C68A-4AB0-4C47-AA02-BFF4795F6C9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184988$4CC5130A-8C38-4B9B-908D-87549E268E8C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1cb8afc2700e646e1bbe6fb507be61083ed800b7","datavalue":{"value":"35365","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1184988$C8D6F717-6F1E-438D-9F8F-FF6A9C7BEA25","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ddfa678240d0c9420f3bb6d7b98370f90ca6be21","datavalue":{"value":"hard problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184988$04DFD52B-8B72-4893-8884-415ADA4B6817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"121b0a8ad973d06529e71ea15269ff6f159a0961","datavalue":{"value":"random sequences","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184988$06EDD8C5-C66E-4E85-874A-9B5D6D27B352","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e343c0d066d632a0b869d2dadad72cc8a3999e1","datavalue":{"value":"Kolmogorov complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1184988$2BCAD555-B846-473D-97FC-811283525E94","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"ba7232f3f7ae68133198ecf25821b70a187e9eaa","datavalue":{"value":{"entity-type":"item","numeric-id":704043,"id":"Q704043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$9A088D94-201A-43F8-8719-5C20FC597CD3","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":"Q1184988$060C50B2-317C-4BFA-9453-2240DF866545","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f8ae69f8ff95a1054d345672afc2549299a932f6","datavalue":{"value":{"entity-type":"item","numeric-id":3692867,"id":"Q3692867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$7FB79CFF-8F76-4A23-AB30-A0CC275070A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45543575358fa9f936229ea1980f01498db37989","datavalue":{"value":{"entity-type":"item","numeric-id":4128010,"id":"Q4128010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$E01FD568-00E5-49FB-8BDF-E95884CB173B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc58fb48063b63f2c168fecda121eb4a00ae957e","datavalue":{"value":{"entity-type":"item","numeric-id":2548174,"id":"Q2548174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$C6F5004D-AE0F-418B-951D-9E40AF3A7501","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a07ca75c7a05c977511c60d16886bb9357e8a1e6","datavalue":{"value":{"entity-type":"item","numeric-id":1157179,"id":"Q1157179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$14F29942-FAAE-439E-BC5F-5FB70752DD7A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"663c83b1b2405da7d703f0e171d190fef0cde5dd","datavalue":{"value":{"entity-type":"item","numeric-id":5541327,"id":"Q5541327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$06068549-B04F-4B6D-BAC2-C11D1DEE0E27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e4cda73737862ae25acf95e82a813fd5a18542be","datavalue":{"value":{"entity-type":"item","numeric-id":5525346,"id":"Q5525346"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$CE06D288-7E01-4F1D-B981-C43FB79F837E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bc3040b7348184db3eacf7d8b95da966aad979d","datavalue":{"value":{"entity-type":"item","numeric-id":4197339,"id":"Q4197339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$81E71AEF-520F-407C-971F-D72E702C3C4E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"85b401a441d540b803e2c66e8f6772fc7a68fab4","datavalue":{"value":{"entity-type":"item","numeric-id":4404463,"id":"Q4404463"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$2026221D-D4F1-4958-9083-1C4503996223","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"544f9d42a0a8acea09d2cbd1189f6a61d54cb466","datavalue":{"value":{"entity-type":"item","numeric-id":3926063,"id":"Q3926063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$61F5654D-3E4D-4D75-9446-F2002B28152C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$837FAA6D-B880-4904-B4C9-5A9077ECC91B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3bb9ae7a4d51bcc66e61116a729c20b41cd64f20","datavalue":{"value":{"entity-type":"item","numeric-id":3756525,"id":"Q3756525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$769D2C0B-FEFD-4AAE-9B3E-3D0B5FF9B8FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad60a730d7197c0e07353c23ef73b9d2e3d4a2dd","datavalue":{"value":{"entity-type":"item","numeric-id":3751001,"id":"Q3751001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$28C14E57-FF4B-4277-901E-A083CD3B0808","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c43b242e8d2a6febe28b4e1a41898561ecb7a1a8","datavalue":{"value":{"entity-type":"item","numeric-id":4138141,"id":"Q4138141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$6D2CD33B-2211-417B-8183-D4A6E368DB76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8e73c4b1eb952ce21189627f2e0b84dd36494db","datavalue":{"value":{"entity-type":"item","numeric-id":3771612,"id":"Q3771612"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$B7B53EC0-401A-4133-BFA1-ADF1ED2CF76F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59a71ee27fc06ad3b0b4b92d7dad58a5649789e7","datavalue":{"value":{"entity-type":"item","numeric-id":4158497,"id":"Q4158497"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1184988$63831C40-D9B2-4933-B5E1-165436099359","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d688c1239f46e6f287fd048f0db543cc1403034","datavalue":{"value":{"entity-type":"item","numeric-id":1179458,"id":"Q1179458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1274ac9f417b55fa9aeb2dcbb156b3406bdd1e51","datavalue":{"value":{"amount":"+0.8320636749267578","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":"Q1184988$DB1A8DA7-53D9-4039-9D81-3A8BB206A044","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dc475811baa166b0b10f576f0916032362b1da2b","datavalue":{"value":{"entity-type":"item","numeric-id":1392022,"id":"Q1392022"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1274ac9f417b55fa9aeb2dcbb156b3406bdd1e51","datavalue":{"value":{"amount":"+0.8320636749267578","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":"Q1184988$52DBA1C3-98A6-41FB-91AD-8443F864EEAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7cd427c4220a99a553a200ba084352fb12c24c7","datavalue":{"value":{"entity-type":"item","numeric-id":3751001,"id":"Q3751001"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5a569c0bedd1515979f567401ea605eb9dc67391","datavalue":{"value":{"amount":"+0.8212100863456726","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":"Q1184988$45B97AE1-6C9D-4CF3-925B-207F3C37D825","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f3a26b19e14ed5d20f14ba3691ab163627c5dcf","datavalue":{"value":{"entity-type":"item","numeric-id":1190985,"id":"Q1190985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1edc4f2d237697a3cf8e1a4f0138f9df620560a3","datavalue":{"value":{"amount":"+0.779509961605072","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":"Q1184988$E8F52925-EA0B-4B44-AE37-A98E8C21AF7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95d5cca443ebdafdb73c91e2fab56af3e14657d9","datavalue":{"value":{"entity-type":"item","numeric-id":4258589,"id":"Q4258589"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fbafe4e2811342f62ee57970d6ba46dab2c62da8","datavalue":{"value":{"amount":"+0.7780476212501526","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":"Q1184988$A1B4F94D-A3D3-41E8-959D-FE5D6DE82974","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Nonuniform complexity and the randomness of certain complete languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Nonuniform_complexity_and_the_randomness_of_certain_complete_languages"}}}}}