{"entities":{"Q4246963":{"pageid":6276564,"ns":120,"title":"Item:Q4246963","lastrevid":108452525,"modified":"2026-11-06T13:17:57Z","type":"item","id":"Q4246963","labels":{"en":{"language":"en","value":"Analysis of distributed-search contraction-based strategies"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1301749"}},"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":"Q4246963$189981D2-2FEE-474A-80F7-3BE25B6048C2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"11537cd2d9461676a4ddbed9223467372841a2ae","datavalue":{"value":"0936.03013","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4246963$E5F03460-62B7-4C6F-8A16-1D5E958AB353","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b455290f5b835c3773a6eb2262897ac70e7a163b","datavalue":{"value":{"entity-type":"item","numeric-id":287273,"id":"Q287273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4246963$62BBA265-34A5-47C3-8305-87EE8DE6AAB7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fdac7f8667945c3fb34e527fc5abbf5817818c79","datavalue":{"value":{"time":"+1999-06-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4246963$4D8254CE-2F8E-4880-B1F9-458F6864D2DF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"10eaeaf8bbf8231bbfc812aab8956e260b5a9f12","datavalue":{"value":"03B35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4246963$F6FAD2FA-11D4-4FBE-99C2-C0263C509B57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e6e7c2e9d67f9590a26e18c734f34db53ce5ec87","datavalue":{"value":"68T15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4246963$B87F75FD-7A04-4AE6-9108-56F918A3DF19","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3f0826e8979c61fecda885f1c87725736a9377d2","datavalue":{"value":"1301749","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4246963$FF9ECE87-5519-4A21-B0D4-29A8AF475D95","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e97175fd5d747e7d34cbcc625e3abab53d84653d","datavalue":{"value":"automated theorem proving","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$D3754709-A8AD-4500-A4A9-5517E48BFE5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae825cca93bbd40be3a29f025f781f23f8b04bd2","datavalue":{"value":"parallel search","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$6D6AE65C-146C-4B15-89F9-FA2CC16216A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d79d5fa3a7b1c094c25acef53cad8c652e86d0b","datavalue":{"value":"forward-reasoning strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$8FB7694C-B863-4394-9A68-99871578019E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ae30a0100574f6545cfe8b3938f1c53cfcf12667","datavalue":{"value":"distributed search","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$31917ADB-2882-4719-A174-9CB324E8C1A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5ec514c0efbc46d9f29d4886d8dffecc45353522","datavalue":{"value":"parallelization of contraction-based strategies","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$E0801369-5290-4906-AD4D-5E348EC26C20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bedd3323a2336895c57e697db34f5ffdfc09590c","datavalue":{"value":"parallel theorem proving","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$22273639-6F51-47C1-8E6A-27F2DDF43CFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ea2b88b2c41a95db9c97ad4063456d1d2477e604","datavalue":{"value":"search complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$99404E84-E720-4403-BEB1-9AC9AE41F797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9be4387a695f5cdfe11ffd641eae0f12fb67477f","datavalue":{"value":"bounded search spaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$37CFA6AA-137E-46D7-ACCA-BE9EE8FDC905","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":"Q4246963$7AF8AA19-554A-4EC1-8774-E65B0D9FD9D6","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c93ae142d165f90d61d468b1b58b365ef92147b","datavalue":{"value":{"entity-type":"item","numeric-id":1978033,"id":"Q1978033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d6c08c6d4837b1cb17efa4237aca5d44b98d12e","datavalue":{"value":{"amount":"+0.96529764","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$C1C0D646-ADB9-427C-9D4C-79DA2E9B35D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee42cb7e2aacc72152818a10b9266c10d1db8cfb","datavalue":{"value":{"entity-type":"item","numeric-id":2426590,"id":"Q2426590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ea8a02e95bc70a4a571b8a76c13cd1e09b3eb9b5","datavalue":{"value":{"amount":"+0.87760675","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$36CE4599-441F-4BB4-8C46-9F1574A62E4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8c710620d32787d7a785d5a90044f59864c30e96","datavalue":{"value":{"entity-type":"item","numeric-id":5092272,"id":"Q5092272"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a6b9839232775570936203b3105c896a953bac8a","datavalue":{"value":{"amount":"+0.87441677","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$8FEBE157-1F96-4719-BAD7-7081285D834E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aee2c395d4f93643a4bbc51ad981af17347c4b3e","datavalue":{"value":{"entity-type":"item","numeric-id":3524248,"id":"Q3524248"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e94c09ff185aaafd7c533c2631cece8ada7ccda","datavalue":{"value":{"amount":"+0.8715995","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$8C3D2E1C-6BC2-428A-ABFE-2EC419581F5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f200bf61e21fe145735f85ef9ac9ff9a9df9f9b","datavalue":{"value":{"entity-type":"item","numeric-id":5103647,"id":"Q5103647"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d978097975259227c6268c34f4c3419eb1a1e8d1","datavalue":{"value":{"amount":"+0.8647483","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$76EA3C5E-0B8C-43BC-AAB7-3457F4B00CCB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b02236efbf1b64c0a21d8589d6386881bbe80dcf","datavalue":{"value":{"entity-type":"item","numeric-id":5347859,"id":"Q5347859"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14591d2b5c8edf2b29bc469abe91804d2e6efbad","datavalue":{"value":{"amount":"+0.86301994","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$09E4BEE0-12E1-462B-A90B-9920458D1933","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"581ac6c284c6a8dd7fd4eec6c20febdb844266e2","datavalue":{"value":{"entity-type":"item","numeric-id":2457634,"id":"Q2457634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b89daed845dcebe73dee6693a9b673f4d4ca8741","datavalue":{"value":{"amount":"+0.8615229","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$0A8CE8D4-668C-4C4E-A8D9-FE6E4C1C99D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f4e1ce2bff1cec4860976b69621096824a16211","datavalue":{"value":{"entity-type":"item","numeric-id":5142938,"id":"Q5142938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cb62b15758370e79e22e65c1dca2f05dd996b86","datavalue":{"value":{"amount":"+0.8608647","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$2789EA3A-B8DD-4B41-9120-966C04E55A49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6dd580e5e84aa218c33a3e1d6d7d1331f382f17d","datavalue":{"value":{"entity-type":"item","numeric-id":286257,"id":"Q286257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f818ecbc19773e46e21c39106b6b0b9f4d993a8f","datavalue":{"value":{"amount":"+0.8583864","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4246963$B3864F37-0199-4CA5-9E02-7A7C8CE7A3EE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dd3be1e1d98e67ec756423f14cf9413af07ab7a0","datavalue":{"value":{"text":"Analysis of distributed-search contraction-based strategies","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4246963$511D3801-1D57-4097-B247-FEFBE1D5394B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5a89ae88194a189e7211508f762acce85a0484f3","datavalue":{"value":"10.1007/3-540-49545-2_8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4246963$1C380955-0D3F-43E1-875C-5262B72629FC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"88c88a70ac52e6d0368091ad011117963ca7357e","datavalue":{"value":"The paper presents a model of parallel search in theorem proving for forward-reasoning strategies, with contraction and distributed search. The parallelization of contraction-based strategies is difficult because of backward contraction: the clauses used as premises are subject to being deleted, the database is highly dynamic and backward contraction diminishes the degree of concurrency of the inferences. The author presents a framework of definitions for parallel theorem proving. Three important properties (monotonicity of the subdivision, fairness and eager contraction) of parallel search plans are developed and sufficient conditions to satisfy them are given. A model of parallel search presented in the paper uses the representation of the search space and the search process in a parallel marked search graph. On the basis of this model the author discusses the problem of measuring benefits and costs of parallelization in terms of search complexity. He presents a notion of distance for clauses and considers the bounded search space made of the clauses whose distance from the input is within a given bound. The infinite search space is reduced to an infinite succession of finite bounded search spaces and the obstacle of comparing infinite spaces is eliminated. This approach captures both the advantages of parallelization and its disadvantages (the cost of communication of parallel search processes). Theorems presented in the paper show that the bounded search spaces capture all relevant phenomena: pruning by contraction, subdivision and costs of communication. The author compares a sequential contraction-based strategy \\(?\\) with its parallelization \\(?'\\) and proves that under some conditions on \\(?'\\) its parallel bounded search spaces are smaller than those of \\(?\\). For the entire collection see [Zbl 0898.00025].","type":"string"},"datatype":"string"},"type":"statement","id":"Q4246963$071FD914-10F7-44C9-A56B-7D3E998CF3A3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"85c07c7737819bff773f78e2590a3bb761fe677b","datavalue":{"value":{"entity-type":"item","numeric-id":162374,"id":"Q162374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4246963$2233B231-F30A-4B31-84FD-625DF96B2775","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Analysis of distributed-search contraction-based strategies","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Analysis_of_distributed-search_contraction-based_strategies"}}}}}