A study on monotone self-dual Boolean functions

Mustafa Altun; Marc D. Riedel

doi:10.1007/s10255-017-0633-x

A study on monotone self-dual Boolean functions

Mustafa Altun^*
, Marc D. Riedel

^*Bu çalışma için yazışmadan sorumlu yazar

Elektronik ve Hab.Müh.Bölümü

University of Minnesota Twin Cities

Araştırma çıktısı: Dergi yayını › Makale › Hakem

Özet

This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n³).

Orijinal dil	İngilizce
Sayfa (başlangıç-bitiş)	43-52
Sayfa sayısı	10
Dergi	Acta Mathematicae Applicatae Sinica
Hacim	33
Basın numarası	1
DOI'lar	https://doi.org/10.1007/s10255-017-0633-x
Yayın durumu	Yayınlandı - 1 Şub 2017

Bibliyografik not

Publisher Copyright:
© 2017, Institute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences and Springer-Verlag Berlin Heidelberg.

Belgeye Erişim

10.1007/s10255-017-0633-x

Diğer Dosyalar ve Linkler

Link to publication in Scopus

Alıntı Yap

@article{0df6c5e5938a4cbcb6e3f24f3bbf89f9,

title = "A study on monotone self-dual Boolean functions",

abstract = "This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n3).",

keywords = "duality problem, monotone Boolean functions, self-dual Boolean functions",

author = "Mustafa Altun and Riedel, \{Marc D.\}",

note = "Publisher Copyright: {\textcopyright} 2017, Institute of Applied Mathematics, Academy of Mathematics and System Sciences, Chinese Academy of Sciences and Springer-Verlag Berlin Heidelberg.",

year = "2017",

month = feb,

day = "1",

doi = "10.1007/s10255-017-0633-x",

language = "English",

volume = "33",

pages = "43--52",

journal = "Acta Mathematicae Applicatae Sinica",

issn = "0168-9673",

publisher = "Springer Verlag",

number = "1",

}

TY - JOUR

T1 - A study on monotone self-dual Boolean functions

AU - Altun, Mustafa

AU - Riedel, Marc D.

PY - 2017/2/1

Y1 - 2017/2/1

N2 - This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n3).

AB - This paper shows that monotone self-dual Boolean functions in irredundant disjuntive normal form (IDNF) do not have more variables than disjuncts. Monotone self-dual Boolean functions in IDNF with the same number of variables and disjuncts are examined. An algorithm is proposed to test whether a monotone Boolean function in IDNF with n variables and n disjuncts is self-dual. The runtime of the algorithm is O(n3).

KW - duality problem

KW - monotone Boolean functions

KW - self-dual Boolean functions

UR - https://www.scopus.com/pages/publications/85015637527

U2 - 10.1007/s10255-017-0633-x

DO - 10.1007/s10255-017-0633-x

M3 - Article

AN - SCOPUS:85015637527

SN - 0168-9673

VL - 33

SP - 43

EP - 52

JO - Acta Mathematicae Applicatae Sinica

JF - Acta Mathematicae Applicatae Sinica

IS - 1

ER -

A study on monotone self-dual Boolean functions

Özet

Bibliyografik not

Belgeye Erişim

Diğer Dosyalar ve Linkler

Parmak izi

Alıntı Yap