{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T21:26:07Z","timestamp":1762032367204},"reference-count":12,"publisher":"World Scientific Pub Co Pte Lt","issue":"02","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2000,6]]},"abstract":"<jats:p> Two decision trees are called decision equivalent if they represent the same function, i.e., they yield the same result for every possible input. <\/jats:p><jats:p> We prove that given a decision tree and a number, to decide if there is a decision equivalent decision tree of size at most that number is NP-complete. As a consequence, finding a decision tree of minimal size that is decision equivalent to a given decision tree is an NP-hard problem. <\/jats:p><jats:p> This result differs from the well-known result of NP-hardness of finding a decision tree of minimal size that is consistent with a given training set. Instead our result is a basic result for decision trees, apart from the setting of inductive inference. <\/jats:p><jats:p> On the other hand, this result differs from similar results for BDDs and OBDDs: since in decision trees no sharing is allowed, the notion of decision tree size is essentially different from BDD size. <\/jats:p>","DOI":"10.1142\/s0129054100000193","type":"journal-article","created":{"date-parts":[[2002,8,24]],"date-time":"2002-08-24T21:40:19Z","timestamp":1030225219000},"page":"343-354","source":"Crossref","is-referenced-by-count":31,"title":["FINDING SMALL EQUIVALENT DECISION TREES IS HARD"],"prefix":"10.1142","volume":"11","author":[{"given":"HANS","family":"ZANTEMA","sequence":"first","affiliation":[{"name":"Department of Computer Science, Utrecht University Padualaan 14, P.O. box 80.089, 3508 TB Utrecht, The Netherlands"}]},{"given":"HANS L.","family":"BODLAENDER","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Utrecht University Padualaan 14, P.O. box 80.089, 3508 TB Utrecht, The Netherlands"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.537122"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0269888997000015"},{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1986.1676819"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(87)90130-7"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1145\/96559.96576"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1109\/12.53586"},{"key":"p_9","first-page":"114","volume":"126","author":"HANCOCK T.","year":"1996","journal-title":"Information and Computation"},{"key":"p_10","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1145\/356893.356898"},{"key":"p_14","first-page":"81","volume":"1","author":"NLAN J. R","year":"1986","journal-title":"Machine Learning"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1145\/129617.129621"},{"key":"p_16","first-page":"2","volume":"37","author":"VANTHIENEN J","year":"1994","journal-title":"Communications of the ACM"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054100000193","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:34:01Z","timestamp":1565192041000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054100000193"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,6]]},"references-count":12,"journal-issue":{"issue":"02","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2000,6]]}},"alternative-id":["10.1142\/S0129054100000193"],"URL":"https:\/\/doi.org\/10.1142\/s0129054100000193","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,6]]}}}