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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Fundam. Prikl. Mat.:
Year:
Volume:
Issue:
Page:
Find






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


Fundam. Prikl. Mat., 2009, Volume 15, Issue 4, Pages 189–208 (Mi fpm1242)  

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

On the constructive characterization of threshold functions

A. P. Sokolov

M. V. Lomonosov Moscow State University

Abstract: In this paper, structure of the set of threshold functions and complexity problems are considered. The notion of a signature of threshold function is defined. It is shown that if threshold function essentially depends on all of its variables then signature of this function is unique. Set of threshold functions is partitioned onto classes with equal signatures. Theorem characterizing this partition is proved. Importance of the class of monotone threshold functions is emphasized. Complexity of transferring one threshold function specified by the linear form into another is examined. It is shown that in the worst case this transferring would take exponential time. Structure of the set of linear forms specifying the same threshold function is also examined. It is proved that for any threshold function this set of linear forms has unique basis in terms of the operation of addition of the linear forms. It is also shown that this basis is countable.

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

English version:
Journal of Mathematical Sciences (New York), 2010, 169:4, 541–555

Bibliographic databases:

UDC: 519.716

Citation: A. P. Sokolov, “On the constructive characterization of threshold functions”, Fundam. Prikl. Mat., 15:4 (2009), 189–208; J. Math. Sci., 169:4 (2010), 541–555

Citation in format AMSBIB
\Bibitem{Sok09}
\by A.~P.~Sokolov
\paper On the constructive characterization of threshold functions
\jour Fundam. Prikl. Mat.
\yr 2009
\vol 15
\issue 4
\pages 189--208
\mathnet{http://mi.mathnet.ru/fpm1242}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2744986}
\transl
\jour J. Math. Sci.
\yr 2010
\vol 169
\issue 4
\pages 541--555
\crossref{https://doi.org/10.1007/s10958-010-0060-5}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-77956060287}


Linking options:
  • http://mi.mathnet.ru/eng/fpm1242
  • http://mi.mathnet.ru/eng/fpm/v15/i4/p189

    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. D. A. Soshin, “Predstavlenie geometricheskikh tipov bulevykh funktsii ot trekh peremennykh algebraicheskimi porogovymi funktsiyami”, PDM, 2016, no. 1(31), 32–45  mathnet  crossref
  • Фундаментальная и прикладная математика
    Number of views:
    This page:198
    Full text:74
    References:28
    First page:2

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