{"entities":{"Q1566745":{"pageid":1577485,"ns":120,"title":"Item:Q1566745","lastrevid":70727283,"modified":"2026-04-13T16:21:56Z","type":"item","id":"Q1566745","labels":{"en":{"language":"en","value":"A variant of inductive counting"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1454577"}},"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":"Q1566745$FED7E638-1BEF-4D2F-8DA5-1E2516070B05","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"0089aec7bdd8aa4475ee37b8c4736148ebd04b33","datavalue":{"value":{"text":"A variant of inductive counting","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1566745$551E041F-D294-40BC-A230-1A1FA67F59BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"97f56a0a2394b9a16c7339db085c423ffcc04f68","datavalue":{"value":"0939.68050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566745$63667270-3DF5-457C-8010-68C005DE6933","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d86b77658ae06c8ab69f8dc9b18783f48e212740","datavalue":{"value":"10.1016/S0304-3975(99)00338-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566745$7C684A55-D586-463E-AF42-19FAC469DFC1","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":"Q1566745$02C12F7E-5FC2-419A-B2FF-F8F1B8232106","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cea4e04940bd3504f3c0f2b605e025bc106fb722","datavalue":{"value":{"time":"+2000-06-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1566745$02AA5C51-3AA2-41F9-BE16-087ACEF749B5","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"947e4fc8e1979c008339f05adddc8a724498be86","datavalue":{"value":"We present a new version of the inductive counting, accepting the complement of an   NSPACE\\((s(n))\\) language nondeterministically in space \\(O(s(n))\\), independent of whether \\(s(n)\\geqslant\\log n\\), but using an additional ``one-way pebble'' -- a movable marker placed on the input tape. This reduces the space used by inductive counting to \\(\\log n+O(s(n))\\) bits on the binary work tape and gives the weakest known nondeterministic device accepting a co\\(-\\)NSPACE\\((o(\\log n))\\) language.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566745$6FC5B060-3559-46EA-800D-1979DF8510D0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566745$CBCA21F5-B2E3-4A75-86B6-5A382E1164B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"052266b1ce6a615d4ab7190a5549189436e8c6cb","datavalue":{"value":"1454577","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566745$0DFDC3FA-F4F8-4FEF-ACFB-CEF5F70CA767","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da67da54e89e7c80f20f3f95c3ceec18bb927753","datavalue":{"value":"Computational complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566745$54C87726-DAD1-4638-AE09-7FD67B050EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"42fc8564d58745c245f1d406df494e1ddb816602","datavalue":{"value":"Space complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566745$66C5EF43-327B-42E6-A46D-9F88579B6E2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3fa4820f6617ca0b11dfcdcac2cd9f2f9ba6e62","datavalue":{"value":"Sublogarithmic space","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566745$9D0738A7-72BF-45A0-A3C6-CFF03415D427","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c54f807c15148ccbe9b891899d7f8cb99e16527f","datavalue":{"value":"Inductive counting","type":"string"},"datatype":"string"},"type":"statement","id":"Q1566745$2B132636-1CE5-4DAC-9385-D0D31166851B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3336a40cc821600c2cc57c5ef4dc532be5780cea","datavalue":{"value":{"entity-type":"item","numeric-id":442278,"id":"Q442278"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$8A9AEACA-8091-4911-8432-47F78566AE97","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":"Q1566745$BCC6B994-524A-44AC-B102-AF0AFBBF16EB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a09ad45c310ccddabe10568a0ab5d8e2fa77be68","datavalue":{"value":{"entity-type":"item","numeric-id":3569021,"id":"Q3569021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$9E9707A9-F880-41D1-ACED-6C8A9721D1C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7094262f8feb2868c674f638629cd77cc8e3413","datavalue":{"value":{"entity-type":"item","numeric-id":1312177,"id":"Q1312177"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$E0ADF709-F197-4449-B691-F3511693C826","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"222cb760457cfe632ac1c0d453dcdf94955dc708","datavalue":{"value":{"entity-type":"item","numeric-id":1207953,"id":"Q1207953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$DC816168-5253-4EBE-BFEC-5F85DF993375","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09e94fb25b2e238532c7bf0cb732cebfc49b58d7","datavalue":{"value":{"entity-type":"item","numeric-id":675225,"id":"Q675225"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$FFB5083B-7467-427F-A785-E4BE2DAF12B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cea6d2ab79d3ca908a76dfbaf32a69dccd1e2412","datavalue":{"value":{"entity-type":"item","numeric-id":4037687,"id":"Q4037687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$57746FCC-7152-4DAD-8A1A-D8906B5ADE06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"324c1d1f92659c3d6b16030614de35454a5e3473","datavalue":{"value":{"entity-type":"item","numeric-id":4365021,"id":"Q4365021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$0F0CE4D9-25F5-40AC-9705-765200363A02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc5f17664ccdc92ae0309d18ea708585665856bd","datavalue":{"value":{"entity-type":"item","numeric-id":1271619,"id":"Q1271619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$FF7DB0FB-0B6B-43CE-A9FC-A17589E0711D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$ACE3E076-A93F-4635-8223-215ED3586EA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"50a8a835ccfd27d2e878f473bb2cd5a24bb869ea","datavalue":{"value":{"entity-type":"item","numeric-id":4895832,"id":"Q4895832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$B44B041A-7FE3-4DFD-9CC3-233B2A39FFAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcaa8b55397625a2950f7d798fc80eeb38eeafc9","datavalue":{"value":{"entity-type":"item","numeric-id":1168735,"id":"Q1168735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$FCD6C220-A268-4AEE-8DFD-217E4E1930E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$2B23233D-AA18-4D8C-B374-D158092B1D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"186efa9cbcaad91d0d4ad1f36de56ca7d39bfe2e","datavalue":{"value":{"entity-type":"item","numeric-id":1099620,"id":"Q1099620"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$262A7972-14C1-425A-A973-0B4830621D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1773944a7d4d6796e22b1946d005c264e51a2586","datavalue":{"value":{"entity-type":"item","numeric-id":1338452,"id":"Q1338452"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1566745$275A6A42-A0BE-41F1-AE7C-11B424B18B66","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9046d7a5c1fe78b607c679f82137cd28f62dff80","datavalue":{"value":"https://doi.org/10.1016/s0304-3975(99)00338-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1566745$C76AF824-E634-4CD3-9832-8A21C3203717","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b8c1e42ed6a52617543309aecfffde64fd492645","datavalue":{"value":"W2044713592","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1566745$8E169CDF-42EC-4927-869E-EA041B36A545","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3d9a0f517af93d4a1ee7407549b497a9da5cf15","datavalue":{"value":{"entity-type":"item","numeric-id":5096885,"id":"Q5096885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1642585142ae20beeb41cad521512b57702b04cd","datavalue":{"value":{"amount":"+0.8051685094833374","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":"Q1566745$DA1C2758-9A09-4F7B-8660-803C7BF5E52F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"759274953bde32599512b371d1c77fa75ef6ad61","datavalue":{"value":{"entity-type":"item","numeric-id":3976031,"id":"Q3976031"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e61547160808918a78280930a1347c8c455f6aa","datavalue":{"value":{"amount":"+0.7882578372955322","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":"Q1566745$F0872A5D-0F74-429B-8F5F-06CE4E2E65AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"644c16fa31a95b2029ddd776bee234481a005aad","datavalue":{"value":{"entity-type":"item","numeric-id":3000290,"id":"Q3000290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c6618367f8bc40872c8283dc1d73edfd272bc7e","datavalue":{"value":{"amount":"+0.7872044444084167","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":"Q1566745$21E4F7BD-0FA2-46D8-B758-36B872CAD11F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"987c8f2d4fca85f98ad371fc8faf11890e7b6630","datavalue":{"value":{"entity-type":"item","numeric-id":1207953,"id":"Q1207953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"29bb014b19921e0a4c5daf82773b1390eda23000","datavalue":{"value":{"amount":"+0.771899938583374","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":"Q1566745$F069383E-BEDE-4B4E-8C97-C61EB0A6AFE4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63eb3b70d26a08dcec6ad7636aa3fa07c51450e8","datavalue":{"value":{"entity-type":"item","numeric-id":3835019,"id":"Q3835019"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"170634c6f8889dd93d5178cd291ec007b98821a5","datavalue":{"value":{"amount":"+0.7631269097328186","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":"Q1566745$43852B3E-4FDC-4577-8B16-1676FE01590B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A variant of inductive counting","badges":[]}}}}}