TY - JOUR

T1 - Totally optimal decision rules

AU - Amin, Talha M.

AU - Moshkov, Mikhail

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Research reported in this publication was supported by King Abdullah University of Science and Technology (KAUST) . The authors are grateful to the anonymous reviewer for useful comments and suggestions.

PY - 2017/11/22

Y1 - 2017/11/22

N2 - Optimality of decision rules (patterns) can be measured in many ways. One of these is referred to as length. Length signifies the number of terms in a decision rule and is optimally minimized. Another, coverage represents the width of a rule’s applicability and generality. As such, it is desirable to maximize coverage. A totally optimal decision rule is a decision rule that has the minimum possible length and the maximum possible coverage. This paper presents a method for determining the presence of totally optimal decision rules for “complete” decision tables (representations of total functions in which different variables can have domains of differing values). Depending on the cardinalities of the domains, we can either guarantee for each tuple of values of the function that totally optimal rules exist for each row of the table (as in the case of total Boolean functions where the cardinalities are equal to 2) or, for each row, we can find a tuple of values of the function for which totally optimal rules do not exist for this row.

AB - Optimality of decision rules (patterns) can be measured in many ways. One of these is referred to as length. Length signifies the number of terms in a decision rule and is optimally minimized. Another, coverage represents the width of a rule’s applicability and generality. As such, it is desirable to maximize coverage. A totally optimal decision rule is a decision rule that has the minimum possible length and the maximum possible coverage. This paper presents a method for determining the presence of totally optimal decision rules for “complete” decision tables (representations of total functions in which different variables can have domains of differing values). Depending on the cardinalities of the domains, we can either guarantee for each tuple of values of the function that totally optimal rules exist for each row of the table (as in the case of total Boolean functions where the cardinalities are equal to 2) or, for each row, we can find a tuple of values of the function for which totally optimal rules do not exist for this row.

UR - http://hdl.handle.net/10754/626257

UR - http://www.sciencedirect.com/science/article/pii/S0166218X17304791

UR - http://www.scopus.com/inward/record.url?scp=85035065766&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2017.10.024

DO - 10.1016/j.dam.2017.10.024

M3 - Article

AN - SCOPUS:85035065766

VL - 236

SP - 453

EP - 458

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

ER -