Diskretnaya Matematika
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



Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Diskr. Mat., 2015, Volume 27, Issue 1, Pages 111–122 (Mi dm1319)  

This article is cited in 1 scientific paper (total in 1 paper)

Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms

Svetlana N. Selezneva

Lomonosov Moscow State University

Abstract: A polarized polynomial form (PPF) (modulo $k$) is a modulo $k$ sum of products of variables $x_1, …, x_n$ or their Post negations, where the number of negations of each variable is determined by the polarization vector of the PPF. The length of a PPF is the number of its pairwise distinct summands. The length of a function $f(x_1, …, x_n)$ of $k$-valued logic in the class of PPFs is the minimum length among all PPFs realizing the function. The paper presents a sequence of symmetric functions $f_n(x_1, …, x_n)$ of three-valued logic such that the length of each function $f_n$ in the class of PPFs is not less than $\lfloor 3^{n+1}/4 \rfloor$, where $\lfloor a \rfloor$ denotes the greatest integer less or equal to the number $a$. The complexity of a system of PPFs sharing the same polarization vector is the number of pairwise distinct summands entering into all of these PPFs. The complexity $L_k^PPF(F)$ of a system $F = \{f_1, …, f_m\}$ of functions of $k$-valued logic depending on variables $x_1, …, x_n$ in the class of PPFs is the minimum complexity among all systems of PPFs $\{p_1, …, p_m\}$ such that all PPFs $p_1, …, p_m$ share the same polarization vector and the PPF $p_j$ realizes the function $f_j$, $j = 1, …, m$. Let $L_k^PPF(m, n) = \max\limits_{F}L_k^PPF(F)$, where $F$ runs through all systems consisting of $m$ functions of $k$-valued logic depending on variables $x_1, …, x_n$. For prime values of $k$ it is easy to derive the estimate $L_k^PPF(m, n) \le k^n$. In this paper it is shown that $L_2^PPF(m, n) = 2^n$ and $L_3^PPF(m, n) = 3^n$ for all $m \ge 2$, $n = 1, 2, …$ Moreover, it is demonstrated that the estimates remain valid when consideration is restricted to systems of symmetric functions only. \def\acknowledgementname{Funding

Keywords: Boolean function, function of three-valued logic, function of $k$-valued logic, polarized polynomial form (PPF), complexity, upper estimate, lower estimate.

Funding Agency Grant Number
Russian Foundation for Basic Research 13-01-00684-а
13-01-00958-а
This work was supported by the Russian Foundation for Basic Research, projects no. 13-01-00684-a and 13-01-00958-a.


DOI: https://doi.org/10.4213/dm1319

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

English version:
Discrete Mathematics and Applications, 2016, 26:2, 115–124

Bibliographic databases:

UDC: 519.716.325
Received: 09.10.2014

Citation: Svetlana N. Selezneva, “Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms”, Diskr. Mat., 27:1 (2015), 111–122; Discrete Math. Appl., 26:2 (2016), 115–124

Citation in format AMSBIB
\Bibitem{Sel15}
\by Svetlana N. Selezneva
\paper Complexity of systems of functions of Boolean algebra and systems of functions of three-valued logic in classes of polarized polynomial forms
\jour Diskr. Mat.
\yr 2015
\vol 27
\issue 1
\pages 111--122
\mathnet{http://mi.mathnet.ru/dm1319}
\crossref{https://doi.org/10.4213/dm1319}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3468145}
\elib{https://elibrary.ru/item.asp?id=23780140}
\transl
\jour Discrete Math. Appl.
\yr 2016
\vol 26
\issue 2
\pages 115--124
\crossref{https://doi.org/10.1515/dma-2016-0009}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000375870900004}
\scopus{https://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84968884486}


Linking options:
  • http://mi.mathnet.ru/eng/dm1319
  • https://doi.org/10.4213/dm1319
  • http://mi.mathnet.ru/eng/dm/v27/i1/p111

    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. A. I. Mamontov, S. M. Ryabinov, “Ob odnom metode ekonomii pamyati pri klassifikatsii tekstov”, Programmnye sistemy: teoriya i prilozheniya, 8:4 (2017), 133–147  mathnet  crossref
  • Дискретная математика
    Number of views:
    This page:322
    Full text:95
    References:42
    First page:25

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