Searching by elimination

DOI10.1016/0167-6423(90)90022-6MaRDI QIDQ920625zbMATH OpenOpenAlexFDO

Authors Anne Kaldewaij, Berry Schoenmakers

Publication date 1990

Published in Science of Computer Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6423(90)90022-6

zbMATH Keywords

left-to-right linear searchprogram derivationprogram schemessearching by eliminationsymmetric linear search

Mathematics Subject Classification ID

General topics in the theory of software (68N01) Searching and sorting (68P10) Specification and verification (program logics, model checking, etc.) (68Q60)

Review text

The paper presents a strategy, called searching by elimination and two refinements symmetric linear search and left-to-right linear search, for solving an extremely general searching problem. When faced to a specific problem, these abstract schemes evolve in a natural neat way to correct programs. For example, for the basic and elementary problem of finding the maximum value in an array, a new and elegant algorithm is found. The presentation is very instructive for the systematic approach by which correct programs are derived from general abstract schemes.

Recommendations

• Learning by the process of elimination
• Elimination methods
• Iterated elimination procedures
• On the Elimination Rule
• Eliminating disjunctions by disjunction elimination
• Eliminating disjunctions by disjunction elimination
• scientific article; zbMATH DE number 2085175
• scientific article; zbMATH DE number 1614705

Cited in

(3)

• The origin of a binary-search paradigm
• Learning by the process of elimination
• Incremental parametric development of greedy algorithms

This page was built for publication: Searching by elimination

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q920625)