Publication:
A heuristic for decomposing a problem into a sequence of subproblems.

Loading...
Thumbnail Image
Authors
Evans, Donald Vincent
Subjects
program synthesis
automatic program synthesis
top-down program synthesis
decomposing problems into subproblems
artificial intelligence
Advisors
Smith, Douglas R.
Date of Issue
1982-12
Date
December 1982
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Thesis
Description
Series/Report No
Department
Computer Science
Organization
Naval Postgraduate School (U.S.)
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
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