Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
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


Matematicheskie Zametki, 1968, Volume 4, Issue 6, Pages 649–658 (Mi mzm6785)  

This article is cited in 4 scientific papers (total in 4 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
Full-text PDF (687 kB) Citations (4)
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$).
Received: 20.05.1968
English version:
Mathematical Notes, 1968, Volume 4, Issue 6, Pages 881–886
DOI: https://doi.org/10.1007/BF01110822
Bibliographic databases:
UDC: 51.01.16
Language: Russian
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/mzm6785}
\mathscinet{http://mathscinet.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:
  • https://www.mathnet.ru/eng/mzm6785
  • https://www.mathnet.ru/eng/mzm/v4/i6/p649
  • This publication is cited in the following 4 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024