Tree-search, Partial Orderings and a New Family of Uninformed Algorithms
Simon Brodt · 2009
First a new formalism for the analysis of (uninformed) search methods is developed. It connects search methods with partial orderings. In this way a characterization of the completeness of a search method and easier completeness checks become possible. Moreover it simplifies the formulation and the proof of further features. Second a new uninformed search algorithm is presented. It is complete and memory efficient and never re-expands nodes. The algorithm is analysed using the previously developed formalism. Finally advantages of the new method for the implementation of logic programming languages are briefly discussed. Especially the efficient processing of (almost) tail recursive progams and the definition of declarative semantics are addressed.