### Further Results on the Problem of Finding Minimal Length Programs for Decision TablesFurther Results on the Problem of Finding Minimal Length Programs for Decision Tables

Access Restriction
Subscribed

 Author Pager, David Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1974 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Abstract In this paper it is shown that whatever the length function employed, the problem of finding the shortest program for a decision table with two (or more) entries is not recursively solvable (whereas for decision tables with a single entry the problem is solvable for some length functions and unsolvable for others). Moreover, it is shown that there is a pair of finite sets of programs and a single entry $\textit{E}$ such that the shortest program for the decision table formed by adding a single additional entry to $\textit{E}$ is in all cases in one of the two sets, but it is undecidable in which. Some consequences of these results are then presented, such as showing that for a wide range of restrictions the results remain true, even when the repertoire of possible programs for a decision table is narrowed by only considering programs which meet certain restrictions. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1974-04-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 21 Issue Number 2 Page Count 6 Starting Page 207 Ending Page 212

#### Open content in new tab

Source: ACM Digital Library