{"entities":{"Q2641235":{"pageid":2651978,"ns":120,"title":"Item:Q2641235","lastrevid":49468039,"modified":"2026-01-07T05:16:57Z","type":"item","id":"Q2641235","labels":{"en":{"language":"en","value":"Rounds versus time for the two person pebble game"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4189512"}},"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":"Q2641235$98E162D6-80F5-41DD-AED4-304AB66ADDE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c577ba5101c962b0b8a7311b60166177e9e92a4f","datavalue":{"value":{"text":"Rounds versus time for the two person pebble game","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2641235$CF1FE9A3-3FAD-42CC-AF0C-66191581C34A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8b79cac5efcfe335def4ae2da9e27dc984ed452b","datavalue":{"value":"0721.90096","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641235$1D833A58-7351-4C57-9205-9D436D6399B4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"948717a83f011a6fe974b6947201f90c68a826cf","datavalue":{"value":"10.1016/0890-5401(90)90002-Y","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641235$35898CB4-5995-49E7-83A1-475B7778CF36","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":"Q2641235$CE648868-0E29-48AE-9E94-EC3DD1ED4F3D","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":"Q2641235$9825E2FC-050B-42F7-B8FF-49E0C1542E7A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$96830956-DC16-4DFF-A556-4C218A49506B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-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":"Q2641235$7E6E8659-27D5-4106-B2C6-582B8B1C0209","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"9c9add08dddc60db785caf5231d5358913d3cfda","datavalue":{"value":"The two-person pebble game is played on a directed acyclic graph G of bounded fan-in, between two adversaries called Pebbler and Challenger. To begin, Challenger places a challenge on a vertex. Then Pebbler places some pebbles on vertices of G. In each round of the game, Challenger either retains the challenge, or challenges a vertex that has just been pebbled. The two adversaries alternate in this way until, at the beginning of Pebbler's move, all immediate predecessors of the challenged vertex are already pebbled, in which case Challenger has lost. The number R of rounds in a game is equal to the number of moves of Challenger. If, against optimal play by Challenger, Pebbler can win using at most t pebbles, one says that G can be pebbled in time t. The paper is concerned with rounds/time tradeoffs, and obtains the following results: (1) For every R and n \\((R=O(n/\\log n))\\), there is a bounded degree graph of n vertices for which Pebbler can win in R rounds only in time (n/log R). (2) There is a graph that exhibits almost tight round/time tradeoffs for all rounds. (3) There is no graph with tight round/time tradeoffs for all rounds. As a consequence the authors improve the simulation of bounded fan-in circuits by unbounded fan-in circuits, extending the size/depth tradeoff of Paterson and Valiant.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641235$281A630F-2C24-4954-98AF-6430577DE350","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"6cd669872d281c67042af939aa0a07de1efaf0d9","datavalue":{"value":{"entity-type":"item","numeric-id":227634,"id":"Q227634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$DDB0079E-5FDC-48BD-9DD1-861916145D50","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641235$C59F1AF8-44DE-4C95-8CE9-C84B01897C34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b98cb7058a1e8e644c33a49a426b651c0e594493","datavalue":{"value":"91A05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641235$8096F0B4-897D-4B40-BEA5-FB1DD45C1D3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641235$7ECF24CB-CA79-4585-A295-984D2686DA91","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8c57fad1093494daea5981f82d441c92ea522d2d","datavalue":{"value":"4189512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2641235$B480FE9A-80F4-46BF-9DB8-AE2D90D94205","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"289efe9f04da3454400c7429dd89c4893a9861b5","datavalue":{"value":"two-person pebble game","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641235$8654A768-8A8D-4082-9230-06D0A96A8B00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6b30413bdc80736aeecdc7f80229ac89c0446304","datavalue":{"value":"directed acyclic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641235$163DB44F-A2E4-49C9-99DB-C3300DDB5CED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36836094f54c21e99e8afabb0d8d211464db97b7","datavalue":{"value":"rounds/time tradeoffs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641235$05BBB3AF-70FA-4DEB-B21C-2349A17493BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e868dcfa68b063208873cf07b4b76de454f6ba64","datavalue":{"value":"size/depth tradeoff","type":"string"},"datatype":"string"},"type":"statement","id":"Q2641235$C8DBE3AE-4AEB-488D-9ACC-C764A76350A7","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":"Q2641235$91EC52CD-DFB1-455C-AB67-9B33E3A4C53C","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c1784a37414f1425361f20c3a37bcdeb603dc27","datavalue":{"value":{"entity-type":"item","numeric-id":1074339,"id":"Q1074339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$0FF1C3C3-4CFC-4EF7-98B7-ACA7BFB4A94A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"832fa1cedc75121f848164530be501a2e61a9f1e","datavalue":{"value":{"entity-type":"item","numeric-id":1226502,"id":"Q1226502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$1C44B0B3-3ABA-449A-97E4-0DEDDE7FFC8C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e876a74df4c5afd434282460ace786203847bd5c","datavalue":{"value":{"entity-type":"item","numeric-id":4131020,"id":"Q4131020"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$223BE541-D1C9-4904-B583-F94FEC09E2F4","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":"Q2641235$55A5C550-E9BB-49E1-838E-044CC0520C8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e65952835a82bfaca0801990e17c41081246b9a","datavalue":{"value":{"entity-type":"item","numeric-id":1233426,"id":"Q1233426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$238C74FD-FA59-4CAC-931E-3B69B8C7C4A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f99fc0604c1edf1b44f83c3b9538e477322458c","datavalue":{"value":{"entity-type":"item","numeric-id":4143082,"id":"Q4143082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$FBB8B816-A03C-4294-A7C0-B87DD06CF95D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4889dc56c7217c646e3175bcede965add157ef74","datavalue":{"value":{"entity-type":"item","numeric-id":4134003,"id":"Q4134003"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$5C0273CD-5C44-42E6-B30F-28CAC92556C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b212b773e1869564fd020e61f20b3ee99615428","datavalue":{"value":{"entity-type":"item","numeric-id":1050717,"id":"Q1050717"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$9E6AD117-3674-41B6-B084-22E2450D0611","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9920c3ac00d626f59f95283223bd4fb6ae680345","datavalue":{"value":{"entity-type":"item","numeric-id":1152951,"id":"Q1152951"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$2789D8D2-7429-4D56-AD87-C783BA1E3597","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb260c42284fc0f845cd0d42733f10b731a1d809","datavalue":{"value":{"entity-type":"item","numeric-id":1166928,"id":"Q1166928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2641235$75687D78-05EC-437A-ADDD-F5B9A8D11B3B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"891de60c78c1bc20d643aab40597cc710e89455c","datavalue":{"value":{"entity-type":"item","numeric-id":5096183,"id":"Q5096183"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"094d9f99110dd092075256a0592ade06a3f8f2d0","datavalue":{"value":{"amount":"+0.9587550759315492","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":"Q2641235$6482C026-6741-47E4-AB7C-9F92D1D6DC47","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9f734a8b58b824ba952e303a3aede4992b72a57","datavalue":{"value":{"entity-type":"item","numeric-id":4260386,"id":"Q4260386"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b0c16399a2ca7e3520d123b5156c14f9e00089fc","datavalue":{"value":{"amount":"+0.7836199998855591","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":"Q2641235$3C74E4DD-944A-470B-8F30-8023BE659DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"60f123b18ab2b31a3c8c7d508821ae3d2a1c9bce","datavalue":{"value":{"entity-type":"item","numeric-id":3741077,"id":"Q3741077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd856ca81249556907906a6fa9c714ce3fe19db0","datavalue":{"value":{"amount":"+0.7745704650878906","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":"Q2641235$8ED3E8A9-ECA3-4E64-9008-EC36D5D33675","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbebbc84afea588057134eceb14276abc5998f1b","datavalue":{"value":{"entity-type":"item","numeric-id":3196374,"id":"Q3196374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"639a570b9deb3921273233c4ea22c122731accf7","datavalue":{"value":{"amount":"+0.7727065086364746","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":"Q2641235$1978BCA5-2ADD-45C7-B2B3-F58B311D6C3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"82152c06eb98d16a447e340c444ddd23bf146c35","datavalue":{"value":{"entity-type":"item","numeric-id":1180416,"id":"Q1180416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dbba3bcc0eaf77f4366c82a2cfea4eaa84cd605f","datavalue":{"value":{"amount":"+0.7684007883071899","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":"Q2641235$BF341AF8-22BD-4B53-B376-8C25300B959D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2641235","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2641235"}}}}}