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



Sib. Èlektron. Mat. Izv.:
Year:
Volume:
Issue:
Page:
Find






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


Sib. Èlektron. Mat. Izv., 2017, Volume 14, Pages 1100–1107 (Mi semr850)  

Discrete mathematics and mathematical cybernetics

Asymptotics of growth for non-monotone complexity of multi-valued logic function systems

V. V. Kochergina, A. V. Mikhailovichb

a Lomonosov Moscow State University, GSP-1, Leninskie Gory, 119991, Moscow, Russia
b Higher School of Economics, str. Myasnitskaya, 20, 101000, Moscow, Russia

Abstract: The problem of the complexity of multi-valued logic functions realization by circuits in a special basis is investigated. This kind of basis consists of elements of two types. The first type of elements are monotone functions with zero weight. The second type of elements are non-monotone elements with unit weight. The non-empty set of elements of this type is finite.
In the paper the minimum number of non-monotone elements for an arbitrary multi-valued logic function system $F$ is established. It equals $\lceil\log_{u}(d(F)+1)\rceil - O(1)$. Here $d(F)$ is the maximum number of the value decrease over all increasing chains of tuples of variable values for at least one function from system $F$; $u$ is the maximum (over all non-monotone basis functions and all increasing chains of tuples of variable values) length of subsequence such that the values of the function decrease over these subsequences.

Keywords: combinational machine (logic circuits), circuits complexity, bases with zero weight elements, $k$-valued logic functions, inversion complexity, Markov's theorem, Shannon function.

DOI: https://doi.org/10.17377/semi.2017.14.093

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

Bibliographic databases:

UDC: 519.714
MSC: 94C10
Received June 1, 2017, published November 9, 2017
Language:

Citation: V. V. Kochergin, A. V. Mikhailovich, “Asymptotics of growth for non-monotone complexity of multi-valued logic function systems”, Sib. Èlektron. Mat. Izv., 14 (2017), 1100–1107

Citation in format AMSBIB
\Bibitem{KocMik17}
\by V.~V.~Kochergin, A.~V.~Mikhailovich
\paper Asymptotics of growth for non-monotone complexity of multi-valued logic function systems
\jour Sib. \`Elektron. Mat. Izv.
\yr 2017
\vol 14
\pages 1100--1107
\mathnet{http://mi.mathnet.ru/semr850}
\crossref{https://doi.org/10.17377/semi.2017.14.093}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000454861900026}


Linking options:
  • http://mi.mathnet.ru/eng/semr850
  • http://mi.mathnet.ru/eng/semr/v14/p1100

    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
  • Number of views:
    This page:75
    Full text:17
    References:20

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