{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T17:15:49Z","timestamp":1649006149877},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2002,6]]},"abstract":"<jats:p> Decision tables provide a natural framework for knowledge acquisition and representation in the area of knowledge based information systems. Decision trees provide a standard method for inductive inference in the area of machine learning. In this paper we show how decision tables can be considered as ordered decision trees: decision trees satisfying an ordering restriction on the nodes. Every decision tree can be represented by an equivalent ordered decision tree, but we show that doing so may exponentially blow up sizes, even if the choice of the order is left free. <\/jats:p><jats:p> Our main result states that finding an ordered decision tree of minimal size that represents the same function as a given ordered decision tree is an NP-hard problem; in earlier work we obtained a similar result for unordered decision trees. <\/jats:p>","DOI":"10.1142\/s0129054102001205","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:05:54Z","timestamp":1027767954000},"page":"445-458","source":"Crossref","is-referenced-by-count":1,"title":["SIZES OF ORDERED DECISION TREES"],"prefix":"10.1142","volume":"13","author":[{"given":"HANS","family":"ZANTEMA","sequence":"first","affiliation":[{"name":"Department of Computer Science, Eindhoven University  of Technology, P.O. box 513, 5600 MB Eindhoven, 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]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054102001205","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:34:40Z","timestamp":1565192080000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054102001205"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,6]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2002,6]]}},"alternative-id":["10.1142\/S0129054102001205"],"URL":"https:\/\/doi.org\/10.1142\/s0129054102001205","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2002,6]]}}}