Consiglio Nazionale delle Ricerche

Tipo di prodottoArticolo in rivista
TitoloCoupling Logical Analysis of Data and Shadow Clustering for partially defined Boolean function reconstruction
Anno di pubblicazione2011
FormatoCartaceo
Autore/iM. Muselli, E. Ferrari
Affiliazioni autoriM. Muselli, E. Ferrari: Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni, Consiglio Nazionale delle Ricerche, Genova, Italy
Autori CNR e affiliazioni
  • ENRICO FERRARI
  • MARCO MUSELLI
Lingua/e
  • inglese
AbstractThe 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.
Lingua abstractinglese
Altro abstract-
Lingua altro abstract-
Pagine da37
Pagine a50
Pagine totali14
RivistaIEEE transactions on knowledge and data engineering (Print)
Attiva dal 1989
Editore: Institute of Electrical and Electronics Engineers, - New York, NY
Paese di pubblicazione: Stati Uniti d'America
Lingua: inglese
ISSN: 1041-4347
Titolo chiave: IEEE transactions on knowledge and data engineering (Print)
Titolo proprio: IEEE transactions on knowledge and data engineering. (Print)
Titolo abbreviato: IEEE trans. knowl. data eng. (Print)
Titoli alternativi:
  • Institute of Electrical and Electronics Engineers transactions on knowledge and data engineering (Print)
  • Transactions on knowledge and data engineering (Print)
  • Knowledge and data engineering (Print)
Numero volume della rivista23
Fascicolo della rivista1
DOI10.1109/TKDE.2009.20
Verificato da refereeSì: Internazionale
Stato della pubblicazione-
Indicizzazione (in banche dati controllate)
  • ISI Web of Science (WOS) (Codice:000284422700004)
  • Scopus (Codice:2-s2.0-78649424137)
Parole chiavePositive Boolean function, logic synthesis, Logical Analysis of Data, Shadow Clustering
Link (URL, URI)-
Titolo parallelo-
Data di accettazione-
Note/Altre informazioni-
Strutture CNR
  • IEIIT — Istituto di elettronica e di ingegneria dell'informazione e delle telecomunicazioni
Moduli CNR
    Progetti Europei-
    Allegati
    • Articolo pubblicato

    Dati associati a vecchie tipologie
    I dati associati a vecchie tipologie non sono modificabili, derivano dal cambiamento della tipologia di prodotto e hanno solo valore storico.
    Editore
    • IEEE Computer Society, Los Alamitos [CA] (Stati Uniti d'America)

    Dati storici
    I dati storici non sono modificabili, sono stati ereditati da altri sistemi (es. Gestione Istituti, PUMA, ...) e hanno solo valore storico.
    Area disciplinareComputer Science & Engineering
    Area valutazione CIVRIngegneria industriale e informatica
    Rivista ISIIEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING [09405J0]
    NoteDOI: http://doi.ieeecomputersociety.org/10.1109/TKDE.2009.206
    Descrizione sintetica del prodotto