Decision Trees and Diagrams

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.

	AKER78	AKERS, S.B. "Binary decision diagrams.'' iEEE Trans. Comput. TC-27, 6 (1978), 509-516.
	AKER79	AKERS, S.B. "Probabilistic techniques for test generation from functional descriptions." in Proc. 9th Syrup. Fault- Tolerant Computing. IEEE, New York, 1979, pp. 113-116.
	BARL75	BARLOW, R. E., FUSSELL, J. B., AND SINGPURWALLA, N. D., EI)s. Reliability and Fault Tree Analysis. SIAM Press, Philadelphia, Pa., 1975~
	BAYE73	BAYES, A.J. "A dynamic programming algorithm to optimize decision table code." Austral. Comput. J. 5, 2 (1973), 77-79.
	BELL78	BELL, D.A. "Decision trees, tables, and lattices." In Pattern Recognition: Ideas in Practice, B. G. Batchelor, Ed. Plenum Press, New York, 1978. Chap. 5.
	BLUM80	BLUM, M., CIqL~NDRA, A. K., AND WEG- MAN, M.N. "Equivalence of free Boolean graphs can be decided probabilistically in polynomial time." Inf. Process. Lett. 10, 2 (1980), 80-82.
	BREI75a	BREITBART, Y., AND REITER, A. "Algorithms for fast evaluation of Boolean expressions." Acta inf. 4 (1975), 107-116.
	BREI75b	BREITBART, Y., AND REiTER, A. "A branch-and-bound algorithm to obtain an optimal evaluation tree for monotonic Boolean functions." Acta Inf. 4 (1975), 311-319.
	BREI78	BREITBART, Y., AND GAL, S. "Analysis of algorithms for the evaluation of monotonic Boolean functions." IEEE Trans. Comput. TC-27, 11 (1978), 1083-1087.
	BROW77	BROWN, P.J. "Functions for selecting tests in diagnostic key construction." Biometrika 64 (1977), 589-596.
	CERN79a	CERNY, E., MANGE, D., AND SANCHEZ, E. "Synthesis of minimal binary decision trees." IEEE Trans. Comput. TC- 28, 7 (1979), 472-482.
	CERN79b	CERNY, E., ANO MOREAU, T. "Test evaluation with a decision machine." In Proc. 9th Symp. Fault-Tolerant Com. puting. IEEE, New York, 1979, pp. 117-120.
	CHAN65	CHANG, H.Y. "An algorithm for selecting an optimal set of diagnostic tests." IEEE Trans. Comput. EC-14, 5 (1965), 706-711.
	CHAN70	CHANG, H. Y., MANNING, E., AND METZE, G. Fault Diagnosis of Digital Systems. Wiley, New York, 1970.
	DALL74	DALLWITZ, M.J. "A flexible computer program for generating identification keys." Syst. ZooL 23 (1974), 50-57.
	DATT81	DATTATREYA, G. R., ANO SARMA, V. V. S. "Bayesian and decision tree approaches for pattern recognihon mcluding feature measurement costs." IEEE Trans. Patt. Anal. Mach. Intell. PAMI- 3, 3 (1981), 293-298.
	DAVI80	DAVIO, M., DESCHAMPS, J.-P., AND TXAYSE, A. Dzscrete and Switching Functions. McGraw-Hall, New York, 1978.
	EGLE63	J. F. Egler, A procedure for converting logic table conditions into an efficient sequence of test instructions, Communications of the ACM, v.6 n.9, p.510-514, Sept. 1963 [doi>10.1145/367593.367595]
	FORT78	Steven Fortune , John E. Hopcroft , Erik Meineche Schmidt, The Complexity of Equivalence and Containment for Free Single Variable Program Schemes, Proceedings of the Fifth Colloquium on Automata, Languages and Programming, p.227-240, July 17-21, 1978
	GANA73	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]
	GARE70	Michael Randolph Garey, Optimal binary decision trees for diagnostic identification problems, 1970
	GARE72a	OAREY, M.R. "Optimal binary identification procedures." SIAM J. Appl. Math. 23, 2 (1972), 173-186.
	GARE72b	GAREY, M.R. "Simple binary identification problems." IEEE Trans. Comput. TC-21, 6 (1972), 588-590.
	GARE74	GARE~, M. R., AND GRAHAM, R. L. "Performance bounds on the sphttmg algorithm for binary testing." A cta Inf. 3 (1974), 347-355.
	GARE79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	GOWE71	GOWER, J. C., AND BARNETT, J. A. "Selecting tests in diagnostic keys with unknown responses." Nature 232 (1971), 491-493.
	GOWE75	GOWER, J. C., AND PAYNE, R.W. "A comparison of different criteria for selecting binary tests in diagnostic keys." Biometrika 62 (1975), 665-672.
	GYLL63	GYLLENBERG, H. G. "A general method for deriving determination schemes for random collections of microbial isolates." Ann. A cad. Sci. Fenn. A IV, 69 (1963), 1-23.
	HALP74	HALPERN, J. "Evaluating Boolean functions with random variables." Int. J. Syst. ScL 5, 6 (1974), 545-553.
	HANA77	Michael Z. Hanani, An optimal evaluation of Boolean expressions in an online query system, Communications of the ACM, v.20 n.5, p.344-347, May 1977 [doi>10.1145/359581.359600]
	HARR65	HARRISON, M. A. introduction to Switching and Automata Theory. McGraw-Hill, New York, 1965.
	HART82	HARTMANN, C. R. P., VARSHNEY, P. K., MEHROTRA, K. G., AND GERBERICH, C. L. "Application of information theory to the construction of efficient decision trees." iEEE Trans. Inf. Theory IT-28, 4 (1982), 565-577.
	HAUS75	HAUSKA, H., AND SWAIN, P. "The decision tree classifier Design and potential.'' In Proc. 2nd Syrup. Machine Processing of Remotely Sensed Data (Lafayette, Ind.). IEEE, New York, 1975, pp. 1A38-1A48.
	HORO81	HOROWlTZ, E., AND ZORAT, A. "The binary tree as an interconnection network: Applications to multiprocessor systems and to VLSI." IEEE Trans. Comput TC-30, 4 (1981), 247-253.
	HULM75	HULME, B. L., AND WORRELL, R. B "A prime implicant algorithm with factoring." IEEE Trans. Comput. TC-24, (1975), 1129-1131.
	HUNG74	HUNG, T.Q. "La construction des clefs de diagnostic." M.S. thesis, University of Montreal, 1974
	HYAF76	HYAFIL, L., AND RIVEST, R. L. "Constructing optimal binary decision trees is NP-complete." Inf. Process. Lett. 5, i (1976), 15-17.
	IANO60	IANOV, i. "The logical schemes of algorithms.'' In Problems and Cybernetics, vol. 1. Pergamon Press, New York, 1960, pp. 82-140.
	JARD71	JARDINE, N., AND SIBSON, R. Mathematical Taxonomy. Wiley, New York, 1971.
	JOHN56	Jo~msoN, S. M. "Optimal sequential testing." Project RAND Res. Mem. RM- 1652, 1956.
	KANA79	KANAL, L.N. "Problem-solving models and search strategies for pattern recognition." IEEE Trans. Patt. Anal. Mach. Intell. PAMI-1, 2 (1979), 193-201.
	KAND80	KANDEL, A., AND FRANCIONI, J. H. "On the properties and applications of fuzzy-valued switching functions." IEEE Trans. Comput. TC-29, 11 (1980), 986-993.
	KING73	P. J. H. King , R. G. Johnson, Some comments on the use of ambiguous decision tables and their conversion to computer programs, Communications of the ACM, v.16 n.5, p.287-290, May 1973 [doi>10.1145/362041.362195]
	KLET60	KLETSKY, E.J. "An applict~on of the information theory approach to failure diagnosis." IRE Trans. Reliability Quality Control RQC-9 (1960), 29-39.
	KNUT71	KNUTH, D. E "Mathematical analysis of algorithms." In Proc. IFIP Congress 71, vol. 1. Elsevier-North Holland, New York, 1971, pp. 135-143.
	KNUT73	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	KULK76	KULKARNI, A. V., AND KANAL, L N. "An optimizahon approach to hierarchical classifier design." In Proc. 3rd Int. Jt. Conf. Pattern Recognztion (San Diego, Calif.). IEEE, New York, 1976.
	KULK78	KULKARNI, A.V. "On the mean accuracy of h~erarchical classifiers." IEEE Trans. Comput. TC-27, 8 (1978), 771-776.
	LAWL66	LAWLER, E., AND WOOD, D. "Branchand-bound methods' A survey." Oper Res. 14, 4 (1966), 699-719.
	LEE59	LEE, C.Y. "Representation of switching crrcuits by binary-decision programs." Bell Syst. Tech. J. 38 (1959), 985-999.
	LOVE79	LOVELAND, D.W. "Selecting optimal test procedures from incomplete test sets." Tech. Rep. CS, 1979-7, Duke Univ, Durham, N. C, 1979.
	MANB82	Udi Manber , Martin Tompa, Probabilistic, nondeterministic, and alternating decision trees (Preliminary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.234-244, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802197]
	MAND64	MANDELBAUM, D. "A measure of efficiency of diagnostic tests upon sequential logic." IEEE Trans. Comput EC-13 (1964), 630.
	MART78	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]
	MASE82	MASEK, W J. "Some NP-complete set covering problems" (to appear m Theor. Comput. Scl.).
	MEIS73	MEISEL, S. W., AND MICHALOPOULOS, D.A. "A partitioning algorithm with apphcatwn m pattern classification and the optnmzation of decision trees" IEEE Trans. Comput. TC-22, 1 (1973), 93-103.
	METZ77	Bruce H. Barnes , John R. Metzner, Decision Table Languages and Systems, Academic Press, Inc., Orlando, FL, 1977
	MICH78	MICHALSKI, R. S. "Designing extended-entry decision tables and optimal decision trees using decision diagrams" Tech. Rep. UIUCDCS-R-78-898, Univ. of Illinois at Urbana-Champalgn, 1978; also IEEE Comput Rep. R78-126, 1978.
	MISR72	MmRA, J. "A study of strategies for multistage testing" Ph.D. dissertatwn, The Johns Hopkins Univ., Baltimore, Md., 1972
	MOLL62	MOILER, F. "Quantitative methods in the systematlcs of the ~ctinomycetales IV. The theory and.~p~ication of a probabilistic identification key." G. Microbiol. 10 (1962), 29-47.
	MONT62	MONTALBANO, M. "Tables, flow charts, and program logic." IBM Syst. J. 1 (1962), 51-63.
	MORE80a	Bernard Marcel Edmond Moret, The representation of discrete functions by decision trees: aspects of complexity and problems of testing, 1980
	MORE80b	B. E. Moret , M. Thomason and R. C. Gonzalez, The Activity of a Variable and Its Relation to Decision Trees, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.580-595, Oct. 1980 [doi>10.1145/357114.357120]
	MORE81a	MORET, B. M. E., THOMASON, M. G., AND GO~ZALEZ, R.C. "The use of activity in testing digital and analog systerns." In Proe. 1st Automatic Test Pro. gram Generation Workshop (Philadelphia, Pa.,). IEEE, New York, pp. 120- 127.
	MORE81b	MORET, B. M. E., THOMASON, M. G., AND GONZALEZ, R. C. "Optimization criteria for decision trees." Tech. Rep. CS81-6. Dep. of Computer Science, Univ. o~ New Mexico, Albuquerque, N Mex., 1981.
	MORE82	MORET, B. M. E., AND SHAPIRO, H. D. "Experience with the minimum test set problem." Tech. Rep. CS82-4, Dep. of Computer Scien~, Univ. of New Mexico, Albuquerque, N. Mex., 1982.
	MORS71	MoRsp., L.E. "Specimen identification and key construction with time-sharing computers." Taxon 20 (1971), 269-282.
	OSBO63	OSBORNE, D.V. "Some aspects of the theory of dichotomous keys." New Phytol. 62 (1963), 111-160.
	PANK70	PANKItURST, R. J. "A computer program for generating diagnostic keys." Comput. J. 13, 2 (1970), 14{t-151.
	PAYH77	PAYNE, H. J., AND MEISEL, W.S. "An algorithm for constructing optimal binary decision trees." IEEE Trans. Cornput. TC-26, 9 (1977), 905-916.
	PAYR77	PAYNE, R.W. "Reticulation and other methods of reducing the size of printed diagnostic keys." J. Gen. Microbiol. 98 (1977), 595-597.
	PAYR80	PAYNE, R. W., AND PREECE, D. A. "Identification keys and diagnostic tables: a review." J. R. Statist. Soc. A 143, 3 (1980), 253-292 (with discussion).
	PAYR81	PAYNE, R. W. "Selection criteria for the construction of efficient diagnostic keys." J. Statist. Plann. Inf. 5 (1981), 27-36.
	PERL76	PERL, Y., AND BREITBART, Y. "Optimal.sequential arrangement of evaluation trees for Boolean functions." Inf. Sci. 11 (1976), 1-12.
	PICA72	PICARD, C. F. Graphes et questwn. naires. Vol. 2: Questionnaires. Gauthier-ViUars, Paris, 1972.
	POLL65	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]
	POOC74	Udo W. Pooch, Translation of Decision Tables, ACM Computing Surveys (CSUR), v.6 n.2, p.125-151, June 1974 [doi>10.1145/356628.356630]
	PRAT78	PRATHER, R. E., AND CASST~.VENS, H. T. "Realization of Boolean expressions by atomic digraphs." IEEE Trans. Comput. TC-27, 8 (1978), 681-688.
	PRES65	Laurence I. Press, Conversion of decision tables to computer programs, Communications of the ACM, v.8 n.6, p.385-390, June 1965 [doi>10.1145/364955.364989]
	RABI71	Jonas Rabin, Conversion of limited-entry decision tables into optimal decision trees: fundamental concepts, ACM SIGPLAN Notices, v.6 n.8, p.68-74, September 1971 [doi>10.1145/953368.953377]
	REIE72	Edward M. Reingold, On the Optimality of Some Set Algorithms, Journal of the ACM (JACM), v.19 n.4, p.649-659, Oct. 1972 [doi>10.1145/321724.321730]
	REIL66	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]
	REIL67	Lewis T. Reinwald , Richard M. Soland, Conversion of Limited-Entry Decision Tables to Optimal Computer Programs II: minimum storage requirement, Journal of the ACM (JACM), v.14 n.4, p.742-756, Oct. 1967 [doi>10.1145/321420.321433]
	RESC61	RESCIGNO, A., AND MACCACARO, G. A "The information content of biological classificatlons." In Information Theory. Fourth London Symposium, C. Cherry, Ed. Butterworth, London, 1961, pp. 437- 445.
	RIES63	RIESEL, H. "In which order are different conditions to be examined." BIT 3 (1963), 255-256.
	RIVE76a	RIVEST, R. L., AND VUILLEMIN, J. "Oil the number of argument evaluations required to compute Boolean functions." Mere. ERL-M476, Electronics Research Laboratory, Univ. of California at Berkeley, 1976.
	RIVE76b	Rw~.ST, R. L., AND VUILLEMIN, J. "On recognizing graph properties from adjacency matrices." Theor. Comp. Sc~. 3 (1976), 371-384.
	ROUN79	ROUNDS, E.M. "A combined non-parametric approach to feature selection and binary tree design." In Proc. Conf Pattern. Recognition and Image Processing, (Chicago, Ill.). IEEE, New York, 1979, pp. 38-43.
	SAVA76	John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
	SCHU76	Helmut Schumacher , Kenneth C. Sevcik, The synthetic approach to decision table conversion, Communications of the ACM, v.19 n.6, p.343-351, June 1976 [doi>10.1145/360238.360245]
	SETH80	I. K. Sethi , B. Chatterjee, Conversion of decision tables to efficient sequential testing procedures, Communications of the ACM, v.23 n.5, p.279-285, May 1980 [doi>10.1145/358855.358863]
	SHAN48	SHANNON, C.E. "A mathematical theory of communication." Bell Syst. Tech. j. 27 (1948), 379-423.
	SHAP81	SHAPIRO, H. D. Private commumcation. Dep Computer Science, Univ. of New Mexico, Albuquerque, N. Mex., 1981.
	SHWA74	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]
	SHWA75	Keith Shwayder, Combining decision rules in a decision table, Communications of the ACM, v.18 n.8, p.476-480, Aug. 1975 [doi>10.1145/360933.360997]
	SILB71	Bruce Silberg, Detab/65 in third-generation Cobol, ACM SIGPLAN Notices, v.6 n.8, p.4-8, September 1971 [doi>10.1145/953368.953369]
	SLAG64	James R. Slagle, An Efficient Algorithm for Finding Certain Minimum-Cost Procedures for Making Binary Decisions, Journal of the ACM (JACM), v.11 n.3, p.253-264, July 1964 [doi>10.1145/321229.321230]
	SLAG70	SLAGLE, J. R., CHANG, C. L., AND LEE, R. C.T. "A new algorithm for generating prnne implicants." IEEE Trans. Comput. TC-19, 4 (1970), 304-310.
	SLAG71	James R. Slagle , Richard C. T. Lee, Application of game tree searching techniques to sequential pattern recognition, Communications of the ACM, v.14 n.2, p.103-110, Feb. 1971 [doi>10.1145/362515.362562]
	TABL76	TABLOSKI, T. F., AND MAULE, F. J. "Numerical expansion technique for minimal multiplexer logic circuits." IEEE Trans. Comput. TC-25, 7 (1976), 684-702.
	THAY78	A. Thayse , M. Davio , J. -P. Deschamps, Optimization of multivalued decision algorithms, Proceedings of the eighth international symposium on Multiple-valued logic, p.171-178, January 1978, Rosemont, Illinois, United States
	THAY81a	THAYSE, A. "P-functions: A new tool for the analysis and synthesis of binary programs." IEEE Trans. Comput. TC- 30, 2 (1981), 126-134.
	THAY81b	THAYSE, A. Boolean Calculus of Differences, Lecture Notes in Computer Science, vol. 101. Springer-Verlag, New York, 1981.
	VOIT77	VOITH, R. "ULM ~mphcants for mmimization of universal logic modules circuits.'' IEEE Trans. Comput. TC-26, 5 (1977), 417-424.
	VOSS52	Voss, E.G. "The history of keys and phylogenetic trees in systematic biology.'' J. Sct. Denison Unw. 43 (1952), 1-25.
	WEID77	Bruce Weide, A Survey of Analysis Techniques for Discrete Algorithms, ACM Computing Surveys (CSUR), v.9 n.4, p.291-313, Dec. 1977 [doi>10.1145/356707.356711]
	WILL80	WILLCOX, W. R., LAPAGE, S. P., ANi) HOLMES, B. "A review of numerical methods in bacterial identification." Antense van Leeuwenhoek 46, 3 (1980), 233-299.
	WONG76	Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
	WORR75	WOm~.LL, R.B. "Using the Set Equatwn Transformation System in fault tree analysis." In Reliabihty and Fault Tree Analysis, R. E. Barlow et al., Eds. SIAM Press, Philadelphia, Pa., 1975, pp. 165- 186.
	WU75	Wu, C., LANOGRF. B~., D., A~O SWAIN, P. "The decision tree approach to classification." Tech. Rep. TR-EE 75-17, Purdue Univ., Lafayette, Ind., 1975.
	YASU71	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]
	YOU76	You, K. C., ANO Fu, K. S. "An appreach to the design of a linear binary tree classifier." In Prec. Syrnp. Machine Processing of Remotely Sensed Data (Lafayette, Ind.). IEEE, New York, 1976, pp. 3A1-3A10.
	ZIMM59	ZIMMERMAN, S. "An optimal search procedure." Am. Math. Mon. 66 (1959), 69O-693.