A heuristic for decomposing a problem into a sequence of subproblems.
heuristicfordeco00evan.pdf (5.812Mb)Abstract
This thesis presents a method for decomposing a specification of a problem into a sequence of subproblem specifications. The method uses the specification to build a tree-like structure called a semantic net. The net is then used to construct a sequence of subspecifications. Each subspecification of the sequence represents a subproblem. Composition of the solutions of the subproblems results in a solution to the given problem specification.
In this work, we present an intuitive approach to what Artificial Intelligence and program synthesis is, define the sequence problem associated with program synthesis, and present the method for deriving a sequence of subspecifications. When this has been done, the method is then applied to a specific problem domain called the Blocks World. We then consider the method in a non-Blocks World domain and follow with a summary.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Automated network protocol reachability analysis with supertrace algorithm and TESTGEN : automated generation of test sequence for a formal protocol specification
(Monterey, California. Naval Postgraduate School, 1994-03);The automation of reachability analysis is an important step in verification of network protocols. The memory size needed for the full state analysis of complex protocols is usually very large and not available on most of ... -
On Lagrangian meshless methods in free-surface flows
(Monterey, California. Naval Postgraduate School, 2005-01);Classically, fluid dynamics have been dealt with analytically because of the lack of numerical resources (Yeung, 1982). With the development of computational ability, many formulations have been developed which typically ... -
Top-down synthesis of simple divide and conquer algorithms
(Monterey, California. Naval Postgraduate School, 1982-11-12); NPS-52-82-011A new method is presented for the deductive synthesis of computer programs. The method takes as given a formal specification of a user's problem. The specification is allowed to be incomplete in that some or all of the ...
