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, 1972, Volume 11, Issue 1, Pages 109–120 (Mi mzm9769)  
This article is cited in 10 scientific papers (total in 11 papers)

The complexity of the realization of symmetrical functions by formulae

V. M. Khrapchenko

Institute of Applied Mathematics, Academy of Sciences of the USSR
Full-text PDF (1526 kB) Citations (11)
Abstract: It is proved that every symmetric function in $k$-valued logic of $n$ arguments can be realized by a formula in any basis, the complexity of the formula not exceeding $n^C$, where $C$ is a constant depending on the basis. It is shown that in the case $k=2$, $C\leqslant 4,93$ for all bases.
Received: 24.12.1970
English version:
Mathematical Notes, 1972, Volume 11, Issue 1, Pages 70–76
DOI: https://doi.org/10.1007/BF01366920
Bibliographic databases:
Document Type: Article
UDC: 51.01
Language: Russian
Citation: V. M. Khrapchenko, “The complexity of the realization of symmetrical functions by formulae”, Mat. Zametki, 11:1 (1972), 109–120; Math. Notes, 11:1 (1972), 70–76
Citation in format AMSBIB
\Bibitem{Khr72}
\by V.~M.~Khrapchenko
\paper The complexity of the realization of symmetrical functions by formulae
\jour Mat. Zametki
\yr 1972
\vol 11
\issue 1
\pages 109--120
\mathnet{http://mi.mathnet.ru/mzm9769}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=311149}
\zmath{https://zbmath.org/?q=an:0301.02016}
\transl
\jour Math. Notes
\yr 1972
\vol 11
\issue 1
\pages 70--76
\crossref{https://doi.org/10.1007/BF01366920}
Linking options:
  • https://www.mathnet.ru/eng/mzm9769
  • https://www.mathnet.ru/eng/mzm/v11/i1/p109
    • This publication is cited in the following 11 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Математические заметки Mathematical Notes
    Statistics & downloads:
    Abstract page:172
    Full-text PDF :87
    First page:1
     
      Contact us:
    		  Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024