article

Free access

Extending the infomation theory approach to converting limited-entry decision tables to computer programs

Author:

Keith ShwayderAuthors Info & Claims

Communications of the ACM, Volume 17, Issue 9

Pages 532 - 537

https://doi.org/10.1145/361147.361117

Published: 01 September 1974 Publication History

PDF eReader

Abstract

This paper modifies an earlier algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program.

The algorithms considered in this paper perform limited search and, accordingly, do not necessarily result in globally optimal solutions. However, the greater search effort needed to obtain a globally optimal solution for complex decision tables is usually not justified by sufficient savings in execution time.

There is an analogy between the problem of converting decision tables into efficient flowcharts and the well-understood problem in information theory of noiseless coding. The results of the noiseless coding literature are used to explore the limitations of algorithms used to solve the decision table problem.

The analogy between the two problems is also used to develop improvements to the information algorithm in extending the depth of search under certain conditions and in proposing additional conditions to be added to the decision table.

Finally, the information algorithm is compared with an algorithm proposed in a recent paper by Verhelst.

References

[1]

Ash, R. information Theory, Wiley, New York, 1965.

Google Scholar

[2]

Chapin, N. Parsing of decision tables. Comm. ACM 10, 9 (Aug. 1967), 507-510, 512.

Digital Library

Google Scholar

[3]

Ganapathy, S., and Rajaraman, V. Information theory applied to the conversion of decision tables to computer programs. Comm. ACM 16, 9 (Sept. 1973), 532-539.

Digital Library

Google Scholar

[4]

Huffman, D.A. A method for the construction of minimum redundancy codes. Proc. IRE 40, 10 (Oct. 1952), 1098-1101.

Crossref

Google Scholar

[5]

King, P.J.H., and Johnson, R.G. Comments on the algorithms of Verhelst for the conversion of limited-entry decision tables to flowcharts. Comm. ACM 17, 1 (Jan. 1974), 43-44.

Digital Library

Google Scholar

[6]

Pollack, S.L., Hicks, H.T., and Harrison, W.J. Decision Tables: Theory and Practice. Wiley, New York, 1971.

Google Scholar

[7]

Pollack, S.L. Conversion of limited-entry decision tables to computer programs. Comm. ACM 8, 11 (Nov. 1965), 677-682.

Digital Library

Google Scholar

[8]

Shwayder, K., Kenney, A.A., and Ainslie, R.J. Decision tablesa tool for tax practitioners. Ttle Tax Adviser 3, 6 (June 1972), 336-345.

Google Scholar

[9]

Shwayder, K. Conversion of limited-entry decision tables to computer programs--a proposed modification to Pollack's algorithm. Comm. ACM 14, 2 (Feb. 1971), 69-73.

Digital Library

Google Scholar

[10]

Verhelst, M. The conversion of limited-entry decision tables to optimal and near-optimal flowcharts: two new algorithms, Comm. ACM 15, 11 (Nov. 1972), 974-980.

Digital Library

Google Scholar

Cited By

View all

Zaki A(2007)Conversion of limited entry decision tables to computer programsInternational Journal of Computer Mathematics10.1080/0020716840880339815:1-4(3-22)Online publication date: 19-Mar-2007
https://doi.org/10.1080/00207168408803398
Jiang ZMookerjee VSarkar S(2005)Lying on the WebInformation Systems Research10.1287/isre.1050.004616:2(131-148)Online publication date: 1-Jun-2005
https://dl.acm.org/doi/10.1287/isre.1050.0046
Colomb RYi-Ping Chen P(2005)Use of partial functional dependencies to make practical approximate translations among forms of propositional expert systemsAdvanced Topics in Artificial Intelligence10.1007/3-540-63797-4_69(167-176)Online publication date: 30-Jul-2005
https://doi.org/10.1007/3-540-63797-4_69
Show More Cited By

Index Terms

Recommendations

Conversion of limited-entry decision tables to computer programs—a proposed modification to Pollack's algorithm

Pollack has proposed an algorithm for converting decision tables into flowcharts which minimize subsequent execution time when compiled into a computer program. Two modifications o this algorithm are proposed. The first relies on Shannon's noiseless ...
Combining decision rules in a decision table
The techniques for minimizing logic circuits are applied to the simplification of decision tables by the combining of decision rules. This method is logically equivalent to the Quine-McCluskey method for finding prime implicants. If some of the decision ...
Information theory applied to the conversion of decision tables to computer programs

Using ideas from information theory, this paper develops a heuristic algorithm that converts a limited entry decision table to a tree structured computer program with near minimum average processing time. The method is applicable to any limited entry ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 17, Issue 9

Sept. 1974

61 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/361147

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago,IL

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 September 1974

Published in CACM Volume 17, Issue 9

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

16
Total Citations
View Citations
373
Total Downloads

Downloads (Last 12 months)71
Downloads (Last 6 weeks)17

Reflects downloads up to 19 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zaki A(2007)Conversion of limited entry decision tables to computer programsInternational Journal of Computer Mathematics10.1080/0020716840880339815:1-4(3-22)Online publication date: 19-Mar-2007
https://doi.org/10.1080/00207168408803398
Jiang ZMookerjee VSarkar S(2005)Lying on the WebInformation Systems Research10.1287/isre.1050.004616:2(131-148)Online publication date: 1-Jun-2005
https://dl.acm.org/doi/10.1287/isre.1050.0046
Colomb RYi-Ping Chen P(2005)Use of partial functional dependencies to make practical approximate translations among forms of propositional expert systemsAdvanced Topics in Artificial Intelligence10.1007/3-540-63797-4_69(167-176)Online publication date: 30-Jul-2005
https://doi.org/10.1007/3-540-63797-4_69
Pop DNegru V(2002)Knowledge Management in Expert System CreatorArtificial Intelligence: Methodology, Systems, and Applications10.1007/3-540-46148-5_24(233-242)Online publication date: 21-Aug-2002
https://doi.org/10.1007/3-540-46148-5_24
Mookerjee VMannino M(1997)Sequential Decision Models for Expert System OptimizationIEEE Transactions on Knowledge and Data Engineering10.1109/69.6347479:5(675-687)Online publication date: 1-Sep-1997
https://dl.acm.org/doi/10.1109/69.634747
Kolaskar ANaik P(1996)Concerted Use of Multiple Databases for Taxonomic InsightsThe Information Revolution: Impact on Science and Technology10.1007/978-3-642-85248-0_33(263-270)Online publication date: 1996
https://doi.org/10.1007/978-3-642-85248-0_33
Khuri SBatarekh A(1991)A binary decision algorithmInformation Sciences: an International Journal10.1016/0020-0255(91)90039-W53:3(251-270)Online publication date: 1-Feb-1991
https://dl.acm.org/doi/10.1016/0020-0255%2891%2990039-W
Yue OLirov Y(1989)MetadiagnosisProceedings IEEE International Symposium on Intelligent Control 198810.1109/ISIC.1988.65448(303-306)Online publication date: 1989
https://doi.org/10.1109/ISIC.1988.65448
Vroomen LZsombor-Murray PBaracos PHudson R(1989)Comments on 'Algorithmic State Machine Design and Automatic Theorem ProvingIEEE Transactions on Computers10.1109/12.2429938:6(880-881)Online publication date: 1-Jun-1989
https://dl.acm.org/doi/10.1109/12.24299
(1985)Binary-decision-based Programmable ControllersIEEE Micro10.1109/MM.1985.3045695:3(58-72)Online publication date: 1-Jun-1985
https://dl.acm.org/doi/10.1109/MM.1985.304569
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Conversion of limited-entry decision tables to computer programs—a proposed modification to Pollack's algorithm

Combining decision rules in a decision table

Information theory applied to the conversion of decision tables to computer programs

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations