RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
General information
Latest issue
Archive
Impact factor
Subscription

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Diskretn. Anal. Issled. Oper.:
Year:
Volume:
Issue:
Page:
Find






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


Diskretn. Anal. Issled. Oper., Ser. 1, 2007, Volume 14, Number 1, Pages 45–69 (Mi da41)  

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

On the depth of Boolean functions over an arbitrary infinite basis

O. M. Kasim-zade

M. V. Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: Realization of Boolean functions by circuits is considered over an arbitrary infinite complete basis. The depth of a circuit is defined as the greatest number of functional elements constituting a directed path from an input of the circuit to its output. The Shannon function of the depth is defined for a positive integer $n$ as the minimal depth $D_B(n)$ of the circuits sufficient to realize every Boolean function on $n$ variables over a basis $B$. It is shown that, for each infinite basis $B$, either there exists a constant $\beta\geqslant 1$ such that $D_B(n)=\beta$ for all sufficiently large $n$ or there exist an integer constant $\gamma\geqslant 2$ and a constant $\delta$ such that $\log_\gamma n\geqslant D_B(n)\geqslant\log_\gamma n+\delta$ for all $n$.

Full text: PDF file (319 kB)
References: PDF file   HTML file

English version:
Journal of Applied and Industrial Mathematics, 2008, 2:2, 196–210

Bibliographic databases:


Citation: O. M. Kasim-zade, “On the depth of Boolean functions over an arbitrary infinite basis”, Diskretn. Anal. Issled. Oper., Ser. 1, 14:1 (2007), 45–69; J. Appl. Industr. Math., 2:2 (2008), 196–210

Citation in format AMSBIB
\Bibitem{Kas07}
\by O.~M.~Kasim-zade
\paper On the depth of Boolean functions over an arbitrary infinite basis
\jour Diskretn. Anal. Issled. Oper., Ser.~1
\yr 2007
\vol 14
\issue 1
\pages 45--69
\mathnet{http://mi.mathnet.ru/da41}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2328234}
\zmath{https://zbmath.org/?q=an:1249.94080}
\transl
\jour J. Appl. Industr. Math.
\yr 2008
\vol 2
\issue 2
\pages 196--210
\crossref{https://doi.org/10.1134/S1990478908020051}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-44849083428}


Linking options:
  • http://mi.mathnet.ru/eng/da41
  • http://mi.mathnet.ru/eng/da/v14/s1/i1/p45

    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. Kochergin A.V., “O glubine funktsii $k$-znachnoi logiki v beskonechnykh bazisakh”, Vestnik Moskovskogo universiteta. Seriya 1: Matematika. Mekhanika, 2011, no. 1, 22–26  mathscinet  zmath  elib
    2. O. M. Kasim-zade, “Depth of Boolean functions realized by circuits over an arbitrary infinite basis”, Moscow University Mathematics Bulletin, 68:1 (2013), 69–70  mathnet  crossref  mathscinet
    3. A. V. Kochergin, “On the depth of $k$-valued logic functions over arbitrary bases”, J. Math. Sci., 233:1 (2018), 100–102  mathnet  crossref
  • Дискретный анализ и исследование операций
    Number of views:
    This page:460
    Full text:144
    References:41

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