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

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

On the depth of Boolean functions over an arbitrary infinite basis

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} 

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

 SHARE:

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
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
3. A. V. Kochergin, “On the depth of $k$-valued logic functions over arbitrary bases”, J. Math. Sci., 233:1 (2018), 100–102
•  Number of views: This page: 460 Full text: 144 References: 41