{"entities":{"Q1180416":{"pageid":1191165,"ns":120,"title":"Item:Q1180416","lastrevid":66773049,"modified":"2026-04-12T12:46:06Z","type":"item","id":"Q1180416","labels":{"en":{"language":"en","value":"On the power of white pebbles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 25767"}},"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":"Q1180416$60677E4D-1EC9-4398-B7FC-9653D887DEA8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8d8ac1d9753e38fe0ff41ae63d04f423d3d899ba","datavalue":{"value":{"text":"On the power of white pebbles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1180416$B9A11D1A-F5CF-4259-80DE-A8F5F2D6EF68","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5e4d7bb538de7738031d9f196b2a6abb5ab4c196","datavalue":{"value":"0788.68044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$1ECC8A3F-08E8-458F-840B-9E5F7F37A9D8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bb8674f2a7079d2fcfa6f04441a05091aa10c554","datavalue":{"value":"10.1007/BF01206359","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$A0A41A16-C6BF-4E50-BA4F-31AEBEF949F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"132fc8c32c01e2a3872c6f4289739e2418a74876","datavalue":{"value":{"entity-type":"item","numeric-id":230555,"id":"Q230555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$D08D28C4-9BF7-4151-8518-664B497EA8E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ea84784d0ec02c56a3f38dfe8d621cdc682004f","datavalue":{"value":{"entity-type":"item","numeric-id":436320,"id":"Q436320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$EF7B5DA3-277A-4FBA-8E19-7D0F84AB88F7","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$C0954A3D-6B62-4956-BC6C-FF2AF6EF7BCA","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70844ffc4666eabac4e20376c648613dbe8620f7","datavalue":{"value":{"time":"+1992-06-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1180416$DFC3DE00-9C77-4233-B98F-0616B8744B03","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b540a00f4bcce8a84634140746034b09521faf37","datavalue":{"value":"Pebble games are played on directed acyclic graphs by placing and removing pebbles according to certain rules. The Black pebble game was introduced by Hewitt and Paterson to model the deterministic evaluation of straight-line programs where the pebbles correspond to the space used in the evaluation process. Cook and Sethi introduced the Black-White pebble game to model the nondeterministic evaluation of straight-line programs. The white pebbles are intended to model the nondeterministic choice.   The rules of the Black pebble game are:   (1) A black pebble may be placed on a vertex \\(v\\) if and only if all immediate predecessors of \\(v\\) have pebbles.   (2) A black pebble can be removed from a vertex at any time.   For the Black-White pebble game two extra rules are added:   (3) A white pebble can be placed on a vertex at any time.   (4) A white pebble can be removed from node \\(v\\) if and only if all immediage predecessors of \\(v\\) have pebbles.   Starting with a pebble-free graph the goal is to pebble all the vertices while attempting to use as few pebbles as possible. A strategy is a sequence of moves that achieves this goal. By comparing the two games we learn about the trade-offs between nondeterminism and space resources.   The authors construct a family of directed acyclic graphs \\((G_ p | p)\\) such that any Black pebble game strategy for \\(G_ p\\) requires \\(p^ 2\\) pebbles, whereas \\(3p+1\\) pebbles suffice when white pebbles are allowed.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180416$8DDD50EF-69DB-44E1-8222-D515A5A0F690","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$A84FF0A0-A34B-4870-AE6C-81A125634F3C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$5C4A15AF-E563-42D2-9F49-EA2F89B1C11C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"4a5372688a0d668805df5d9ffd1da58833a0f595","datavalue":{"value":"68R05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$2A1165EA-DE97-4C33-9498-875BA76EFE50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$68A40521-6591-4F05-8CC0-A6756705C1C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$46300C40-554E-41EE-A5DB-E8F2A0CEA80F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8f3d36beacab84fa9d59933d15a36dd03f14c0b1","datavalue":{"value":"25767","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$977EDDC5-9230-46A5-847B-C505F1F677F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"52ba6d968a7617d9b56b80603a9b30974da2b918","datavalue":{"value":"determinism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180416$C3402DAD-17F5-45DD-B2D3-6CAC5A0C88FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4c2155b1f0f1b7934ea2f00e74be522bfbe52774","datavalue":{"value":"directed acyclic graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180416$18950D9E-3BB6-4001-B414-FAC817652AB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1b95970dbbafca6a8b13371dabe0dccec26c445","datavalue":{"value":"pebble game","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180416$C0D6F56A-43A1-448A-96A5-6C1A17D75786","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8acef8c5412877d7ff45210ae9d119deab5ead4b","datavalue":{"value":"straight-line programs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180416$E330B515-B414-47E5-81FA-DBFAA1969076","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f532e2b08234dd6967fc70eafbf0c8f20a836d3e","datavalue":{"value":"nondeterminism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1180416$C5D5C248-F609-41DE-B0F0-EB88DE96DC8D","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":"Q1180416$251005F9-A6D2-4067-A7D8-BEA3D9614E64","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"038a7e4418ac17f21ed0f4437cc57844c7dfca4e","datavalue":{"value":{"entity-type":"item","numeric-id":1230508,"id":"Q1230508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$1EB167CE-E238-4409-AA21-002CF2A1E6FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a00040d8554770d1821de600986e67f018fde51d","datavalue":{"value":{"entity-type":"item","numeric-id":3769962,"id":"Q3769962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$B16D6F3C-7B9A-41D0-BA26-721C31755835","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3868dbf56bd7e8d60550e371f494d2e9172a76b","datavalue":{"value":{"entity-type":"item","numeric-id":3959426,"id":"Q3959426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$D794991C-D8A1-4110-81E7-E06408ACE6E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7240aba3392d9a3fa2165cd99316a70c1d4c7340","datavalue":{"value":{"entity-type":"item","numeric-id":1149448,"id":"Q1149448"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$0FA41A4C-9FFF-47B3-9351-DACB15CCC08E","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":"Q1180416$545DB6B9-3C79-470E-A997-0D929CA3E741","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f881f02dfbfbcea83db155d8ce4d46379ac9d0a0","datavalue":{"value":{"entity-type":"item","numeric-id":1111025,"id":"Q1111025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1180416$0FE89C54-0240-4243-9141-1570E94B0967","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c934911d6ce6c4ef58a0b8474097e0ee54926803","datavalue":{"value":"https://doi.org/10.1007/bf01206359","type":"string"},"datatype":"url"},"type":"statement","id":"Q1180416$85FEC00F-8309-4E1D-83BC-7B7CB05326DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6a4e1155866e0f61faac6b6a6ebd3d84e13e0f82","datavalue":{"value":"W2611481948","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1180416$3EE3DFE1-760B-42CA-9703-D4C06E7961F0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"703948efc7091c6f74cfb89394daa1f024814a14","datavalue":{"value":{"entity-type":"item","numeric-id":1111025,"id":"Q1111025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"635d4b68ec6f3b2238ffd729f9b63c416b3dda55","datavalue":{"value":{"amount":"+0.85983646","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$DE224C2B-7F82-4626-8C22-AD4A1EB89F69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e339f47f2a6ccb858d8ab7a6d909e9aee0bce90b","datavalue":{"value":{"entity-type":"item","numeric-id":1378486,"id":"Q1378486"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8866b4109db4380c7e56a74967e67d1218a067fd","datavalue":{"value":{"amount":"+0.7575249","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$26CD52CB-FB05-495F-A9C8-ADC0A7BE4DE5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c8ba23703909f2cbb3715e47ede1e0a2d25eb881","datavalue":{"value":{"entity-type":"item","numeric-id":1178189,"id":"Q1178189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c10d3c9d0fe5ee11fe1b18e7b012652f4e87bb4","datavalue":{"value":{"amount":"+0.72960526","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$76D52F51-8518-4118-87C5-1FC0C3396178","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b7b29f3fe72a579c2b50356d9ea843cb19dec6b","datavalue":{"value":{"entity-type":"item","numeric-id":4392906,"id":"Q4392906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"28e840152c21d1342b071c142b3d7574593cc5ea","datavalue":{"value":{"amount":"+0.7223294","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$FE31614E-3B71-4B0A-B9F3-9B3172F76575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55820431f6d3f454cae57fa6f1bc430df844d602","datavalue":{"value":{"entity-type":"item","numeric-id":2822877,"id":"Q2822877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"391ac6e61fa173dfaec32b2a58794683ff6a0693","datavalue":{"value":{"amount":"+0.7149419","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$C533AD1D-9C6E-4941-A8EF-E82A4724F88C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b47dc340b33633ac221ddf9635d087dc056198b6","datavalue":{"value":{"entity-type":"item","numeric-id":4541132,"id":"Q4541132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fd05cf1b5236b93143c65535475a3d8828b385be","datavalue":{"value":{"amount":"+0.7086649","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$C39DEF77-9A84-48CA-97E8-DAE498FA1918","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"19c48af6a3c9287f130a216caa3d89f157ed7705","datavalue":{"value":{"entity-type":"item","numeric-id":2226123,"id":"Q2226123"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f2a1d084ca5e5ae2b74fe90744994fe0cceb2fb0","datavalue":{"value":{"amount":"+0.7052827","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$C36097C8-90F7-4E0E-8DB8-10F913E097AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c0e186dfcb869e98e80d47bbef73c9bf14182ee","datavalue":{"value":{"entity-type":"item","numeric-id":848928,"id":"Q848928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2450e6b8fd0b9b3e322623bc224ad6bdaeb7dffd","datavalue":{"value":{"amount":"+0.7044872","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1180416$55837563-860B-47D6-8D1D-4BED99E6A682","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the power of white pebbles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_power_of_white_pebbles"}}}}}