Analysis of distributed-search contraction-based strategies (Q4246963)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1301749
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Analysis of distributed-search contraction-based strategies |
scientific article; zbMATH DE number 1301749 |
Statements
16 June 1999
0 references
automated theorem proving
0 references
parallel search
0 references
forward-reasoning strategies
0 references
distributed search
0 references
parallelization of contraction-based strategies
0 references
parallel theorem proving
0 references
search complexity
0 references
bounded search spaces
0 references
0.96529764
0 references
0.87760675
0 references
0.87441677
0 references
0.8715995
0 references
0.8647483
0 references
0.86301994
0 references
0 references
0.8608647
0 references
Analysis of distributed-search contraction-based strategies (English)
0 references
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].
0 references