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
      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

      Identifiers