Access Restriction

Author Schumacher, Helmut ♦ Sevcik, Kenneth C.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Decision tables ♦ Optimal programs ♦ Dynamic programming ♦ Decision trees
Abstract Previous approaches to the problem of automatically converting decision tables to computer programs have been based on decomposition. At any stage, one condition is selected for testing, and two smaller problems (decision tables with one less condition) are created. An optimal program (with respect to average execution time or storage space, for example) is located only through implicit enumeration of all possible decision trees using a technique such as branch-and-bound. The new approach described in this paper uses dynamic programming to synthesize an optimal decision tree from which a program can be created. Using this approach, the efficiency of creating an optimal program is increased substantially, permitting generation of optimal programs for decision tables with as many as ten to twelve conditions.
Description Affiliation: Univ. of Toronto, Ont., Canada (Schumacher, Helmut; Sevcik, Kenneth C.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 19
Issue Number 6
Page Count 9
Starting Page 343
Ending Page 351

Open content in new tab

   Open content in new tab
Source: ACM Digital Library