Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS


Vestnik Moskov. Univ. Ser. 1. Mat. Mekh.:
Year:
Volume:
Issue:
Page:
Find




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

Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika, 2022, Number 3, Pages 25–32 (Mi vmumm4472)  
Mathematics

On the implementation of monotone Boolean functions by memoryless programs

A. V. Chashkin

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics
Full-text PDF (352 kB)
References:
PDF
HTML
Abstract: The average-case complexity of computing monotone Boolean functions by straight line programs without memory with a conditional stop in the basis of all Boolean functions of at most two variables is considered. For the set of all monotone Boolean functions of $n$ variables, Shannon-type upper and lower bounds for the average-case complexity are established for $n\to\infty$.
Key words: monotone Boolean functions, formulas, average-case complexity.
Received: 08.12.2021
English version:
Moscow University Mathematics Bulletin, 2022, Volume 77, Issue 3, Pages 136–143
DOI: https://doi.org/10.3103/S0027132222030056
Bibliographic databases:
Document Type: Article
UDC: 507
Language: Russian
Citation: A. V. Chashkin, “On the implementation of monotone Boolean functions by memoryless programs”, Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2022, no. 3, 25–32; Moscow University Mathematics Bulletin, 77:3 (2022), 136–143
Citation in format AMSBIB
\Bibitem{Cha22}
\by A.~V.~Chashkin
\paper On the implementation of monotone Boolean functions by memoryless programs
\jour Vestnik Moskov. Univ. Ser.~1. Mat. Mekh.
\yr 2022
\issue 3
\pages 25--32
\mathnet{http://mi.mathnet.ru/vmumm4472}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=4480999}
\zmath{https://zbmath.org/?q=an:7596807}
\transl
\jour Moscow University Mathematics Bulletin
\yr 2022
\vol 77
\issue 3
\pages 136--143
\crossref{https://doi.org/10.3103/S0027132222030056}
Linking options:
  • https://www.mathnet.ru/eng/vmumm4472
  • https://www.mathnet.ru/eng/vmumm/y2022/i3/p25
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Statistics & downloads:
    Abstract page:61
    Full-text PDF :18
    References:16
    First page:2
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024