IEEE Transactions on Knowledge and Data Engineering · 2009 · 65 citations · 18 references
ComputingComputer EngineeringComputer ScienceAlgorithmsData StructuresOptimizationBoolean AlgebraBoolean OperationsCircuit ComplexityComputational ComplexityDigital Logic DesignLogic SynthesisBoolean Function ComplexityBoolean Function MinimizationBoolean Function RepresentationBoolean FunctionsBoolean MinimizationComplexity Of Boolean FunctionsDepth-first SearchLogic Minimization
The problem of reconstructing the and-or expression of a partially defined positive Boolean function (pdpBf) is solved by adopting a novel algorithm, denoted by LSC, which combines the advantages of two efficient techniques, Logical Analysis of Data (LAD) and Shadow Clustering (SC). The kernel of the approach followed by LAD consists in a breadth-first enumeration of all the prime implicants whose degree is not greater than a fixed maximum d. In contrast, SC adopts an effective heuristic procedure for retrieving the most promising logical products to be included in the resulting and-or expression. Since the computational cost required by LAD prevents its application even for relatively small dimensions of the input domain, LSC employs a depth-first approach, with asymptotically linear memory occupation, to analyze the prime implicants having degree not greater than d. In addition, the theoretical analysis proves that LSC presents almost the same asymptotic time complexity as LAD. Extensive simulations on artificial benchmarks validate the good behavior of the computational cost exhibited by LSC, in agreement with the theoretical analysis. Furthermore, the pdpBf retrieved by LSC always shows a better performance, in terms of complexity and accuracy, with respect to those obtained by LAD.
18
An implementation of logical analysis of data
Endre Boros, P. L. Hammer, Toshihide Ibaraki et al. · IEEE Transactions on Knowledge and Data Engineering · 2000 · 409 citations · Full text
Computing, Data Science, Data Mining +16
Feature selection via discretization
Rudy Setiono · IEEE Transactions on Knowledge and Data Engineering · 1997 · 325 citations