RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Subscription
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Mat. Zametki, 1968, Volume 4, Issue 6, Pages 649–658 (Mi mz6785)  

This article is cited in 2 scientific papers (total in 2 papers)

On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions

A. A. Sapozhenko

Institute of Mathematics, Siberian Branch of USSR Academy of Sciences

Abstract: The maximal number $l(f)$ of conjunctions in a dead-end disjunctive normal form (d.n.f.) of a Boolean function $f $and the number $\tau(f)$ of dead-end d.n.f. are important parameters characterizing the complexity of algorithms for finding minimal d.n.f. It is shown that for almost all Boolean functions $l(f)\sim2^{n-1}$, $\log_2\tau(f)\sim2^{n-1}\log_2n\log_2\log_2n$ ($n\to\infty$).

Full text: PDF file (687 kB)

English version:
Mathematical Notes, 1968, 4:6, 881–886

Bibliographic databases:

UDC: 51.01.16
Received: 20.05.1968

Citation: A. A. Sapozhenko, “On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions”, Mat. Zametki, 4:6 (1968), 649–658; Math. Notes, 4:6 (1968), 881–886

Citation in format AMSBIB
\Bibitem{Sap68}
\by A.~A.~Sapozhenko
\paper On the greatest length of a~dead-end disjunctive normal form for almost all Boolean functions
\jour Mat. Zametki
\yr 1968
\vol 4
\issue 6
\pages 649--658
\mathnet{http://mi.mathnet.ru/mz6785}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=243936}
\zmath{https://zbmath.org/?q=an:0177.02001|0169.01702}
\transl
\jour Math. Notes
\yr 1968
\vol 4
\issue 6
\pages 881--886
\crossref{https://doi.org/10.1007/BF01110822}


Linking options:
  • http://mi.mathnet.ru/eng/mz6785
  • http://mi.mathnet.ru/eng/mz/v4/i6/p649

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    This publication is cited in the following articles:
    1. I. P. Chukhrov, “On irredundant complexes of faces in the unit cube”, Discrete Math. Appl., 21:2 (2011), 243–274  mathnet  crossref  crossref  mathscinet  elib
    2. I. P. Chukhrov, “On the relation between the irredundant and minimal complexes of faces in the unit cube”, Discrete Math. Appl., 22:3 (2012), 273–306  mathnet  crossref  crossref  mathscinet  elib
  • Математические заметки Mathematical Notes
    Number of views:
    This page:358
    Full text:98
    First page:1

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020