The Activity of a Variable and Its Relation to Decision Trees

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The Activity of a Variable and Its Relation to Decision Trees

Full text

Pdf (790 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 2 , Issue 4 (October 1980) table of contents

Pages: 580 - 595

Year of Publication: 1980

ISSN:0164-0925

Authors

B. E. Moret	Department of Computer Science, University of New Mexico, Albuquerque, NM
M. Thomason and R. C. Gonzalez	Department of Computer Science, University of Tennessee, Knoxville, TN and Department of Electrical Engineering, University of Tennessee, Knoxville, TN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 29, Citation Count: 5

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/357114.357120 What is a DOI?

ABSTRACT

The construction of sequential testing procedures from functions of discrete arguments is a common problem in switching theory, software engineering, pattern recognition, and management. The concept of the activity of an argument is introduced, and a theorem is proved which relates it to the expected testing cost of the most general type of decision trees. This result is then extended to trees constructed from relations on finite sets and to decision procedures with cycles. These results are used, in turn, as the basis for a fast heuristic selection rule for constructing testing procedures. Finally, some bounds on the performance of the selection rule are developed.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	AKERS, S.B. Binary decision diagrams. IEEE Trans. Comput. C-27, 6 (June 1978), 509-516.
	2	BOZOYAN, SH.YE. Certain properties of Boolean differentials and the activities of the arguments of Boolean functions and questions of construction of reliable schemes that have unreliable elements. Eng. Cybern. 13, 5 (Sept. 1975), 108-120.
	3	BREITBART, Y., AND REITER, A. Algorithms for fast evaluation of Boolean expressions. Acta Inf. 4 (1975), 107-116.
	4	BREITBART, Y., AND RE~TER, A. A branch-and-bound algorithm to obtain an optimal evaluation tree for monotonic Boolean functions. Acta Inf. 4 (1975), 311-319.
	5	CERNY, E., MANGE, D., AND SANCUEZ, E. Synthesis of minimal binary decision trees. IEEE Trans. Comput. C-28, 7 (July 1979), 472--482.
	6	S. Ganapathy , V. Rajaraman, Information theory applied to the conversion of decision tables to computer programs, Communications of the ACM, v.16 n.9, p.532-539, Sept. 1973 [doi>10.1145/362342.362348]
	7	GAREY, M.R. Optimal identification procedures. SIAM J. Appl. Math. 23, 2 (1972), 173-186.
	8	HYAFIL, L., AND RIVEST, R.L. Constructing optimal binary decision trees is NP-complete. Inf. Proc. Letters 5, 1 (1976-1977), 15-17.
	9	LEE, C.R. Representation of switching circuits by binary decision programs. Bell Syst. Tech. J. 38 (July 1959), 945-999.
	10	Alberto Martelli , Ugo Montanari, Optimizing decision trees through heuristically guided search, Communications of the ACM, v.21 n.12, p.1025-1039, Dec. 1978 [doi>10.1145/359657.359664]
	11	Bruce H. Barnes , John R. Metzner, Decision Table Languages and Systems, Academic Press, Inc., Orlando, FL, 1977
	12	PAYNE, H.J., AND MEISEL, W.S. An algorithm for constructing optimal binary decision trees. IEEE Trans. Comput. C-26, 9 (Sept. 1977), 905-916.
	13	PICARD, C.F. Graphes et Questionnaires, Volume 2: Questionnaires. Gauthier-Villars, Paris, 1972.
	14	Solomon L. Pollack, Conversion of limited-entry decision tables to computer programs, Communications of the ACM, v.8 n.11, p.677-682, Nov. 1965 [doi>10.1145/365660.365681]
	15	Lewis T. Reinwald , Richard M. Soland, Conversion of Limited-Entry Decision Tables to Optimal Computer Programs I: Minimum Average Processing Time, Journal of the ACM (JACM), v.13 n.3, p.339-358, July 1966 [doi>10.1145/321341.321343]
	16	ROUNDS, E.M. A combined non-parametric approach to feature selection and binary tree design. Proc. Conf. on Pattern Recognition and Image Processing, Chicago, Ill., 1979, pp. 38-43.
	17	Keith Shwayder, Extending the infomation theory approach to converting limited-entry decision tables to computer programs, Communications of the ACM, v.17 n.9, p.532-537, Sept. 1974 [doi>10.1145/361147.361117]
	18	Robert O. Winder, Chow Parameters in Threshold Logic, Journal of the ACM (JACM), v.18 n.2, p.265-289, April 1971 [doi>10.1145/321637.321647]
	19	Toshio Yasui, Some aspects of decision table conversion techniques, ACM SIGPLAN Notices, v.6 n.8, p.104-111, September 1971 [doi>10.1145/953368.953382]
	20	You, K.C., AND FU, K.S. An approach to the design of a linear binary tree classifier. Proc. Symp. on Machine Processing of Remotely Sensed Data, Lafayette, Ind., 1976, pp. 3A1-3A10.

CITED BY 5

	J. R. B. Cockett , J. A. Herrera, Decision tree reduction, Journal of the ACM (JACM), v.37 n.4, p.815-842, Oct. 1990
	Bernard M. E. Moret, Decision Trees and Diagrams, ACM Computing Surveys (CSUR), v.14 n.4, p.593-623, Dec. 1982
	J R B Cockett , J Herrera, Prime rule-based methodologies give inadequate control, Proceedings of the ACM SIGART international symposium on Methodologies for intelligent systems, p.441-449, October 22-24, 1986, Knoxville, Tennessee, United States
	Masahiro Miyakawa, Criteria for Selecting a Variable in the Construction of Efficient Decision Trees, IEEE Transactions on Computers, v.38 n.1, p.130-141, January 1989
	Sreerama K. Murthy, Automatic Construction of Decision Trees from Data: A Multi-Disciplinary Survey, Data Mining and Knowledge Discovery, v.2 n.4, p.345-389, December 1998