Shortest and minimal disjunctive normal forms of complete functions

Yu V. Maximov

    Результат исследований: Вклад в журналСтатьярецензирование

    Аннотация

    It was previously established that almost every Boolean function of n variables with k zeros, where k is at most log2n–log2log2n + 1, can be associated with a Boolean function of 2k–1–1 variables with k zeros (complete function) such that the complexity of implementing the original function in the class of disjunctive normal forms is determined only by the complexity of implementing the complete function. An asymptotically tight bound is obtained for the minimum possible number of literals contained in the disjunctive normal forms of the complete function.

    Язык оригиналаАнглийский
    Страницы (с-по)1242-1255
    Число страниц14
    ЖурналComputational Mathematics and Mathematical Physics
    Том55
    Номер выпуска7
    DOI
    СостояниеОпубликовано - 27 июл. 2015

    Fingerprint

    Подробные сведения о темах исследования «Shortest and minimal disjunctive normal forms of complete functions». Вместе они формируют уникальный семантический отпечаток (fingerprint).

    Цитировать