检索结果-内蒙古大学图书馆

Asymptotically best method for synthesis of boolean recursive circuits

DISCRETE MATHEMATICS AND APPLICATIONS 2020年第2期30卷 137-146页

作者： Zhukov, Vladimir V. Lozhkin, Sergey A. Lomonosov Moscow State Univ Moscow Russia

Models of multi-output and scalar recursive boolean circuits of bounded depth in an arbitrary basis are considered. Methods for lower and upper estimates for the Shannon function for the complexity of circuits of these classes are provided. Based on these methods, an asymptotic formula for the Shannon function is put forward. Moreover, in the above classes of recursive circuits, upper estimates for the complexity of implementation of some functions and systems of functions used in applications are obtained.

关键词： recursive circuits of gates complexity of boolean functions Shannon function asymptotic estimates

来源：评论

学校读者我要写书评

暂无评论

Asymptotically Best Synthesis Methods for Reflexive-Recursive Circuits

引用

Computational Mathematics and Modeling 2020年第3期31卷 369-383页

作者： Zhukov, V.V. Faculty of Computational Mathematics and Cybernetics Lomonosov Moscow State University Moscow Russian Federation

We introduce the notion of reflexive-recursive circuits and consider classes of many-output and scalar reflexive-recursive circuits of bounded depth in an arbitrary basis. Methods are proposed for deriving lower and upper bounds on the Shannon function for the complexity of circuits from these classes and asymptotic expressions are established. We also derive upper bounds for the realization complexity in these classes of circuits for some functions and systems of functions occurring in applications. © 2020, Springer Science+Business Media, LLC, part of Springer Nature.

关键词： asymptotic bounds complexity of boolean functions recursive circuits of functional elements Shannon function

来源：评论

学校读者我要写书评

暂无评论

The asymptotically best method for synthesizing limited-depth boolean recursive schemes

引用

Moscow University Computational Mathematics and Cybernetics 2017年第3期41卷 134-141页

作者： Zhukov, V.V. Faculty of Computational Mathematics and Cyberntics Moscow State University Moscow 119991 Russian Federation

A model of limited-depth recursive schemes for the functions of boolean algebra (boolean functions), constructed from multi-output functional elements, is considered. A lower estimate of the Shannon function for the complexity of schemes of this class is derived. Upper estimates for the complexity of some specific functions and systems of functions in this class of schemes are obtained. A method is proposed for synthesizing schemes of this class for arbitrary functions that allow us (using the derived lower estimate) to determine the asymptotics of the Shannon function for their complexity. © 2017, Allerton Press, Inc.

关键词： asymptotic estimates complexity of boolean functions recursive schemes of functional elements Shannon’s function

来源：评论

学校读者我要写书评

暂无评论

Harmonic analysis, real approximation, and the communication complexity of boolean functions

引用

ALGORITHMICA 1999年第4期23卷 341-353页

作者： Grolmusz, V Eotvos Lorand Univ Dept Comp Sci H-1088 Budapest Hungary

The two-party communication complexity of boolean function f is known to be at least log rank(M-f). i.e., the logarithm of the rank of the communication matrix of f [19]. Lovasz and Saks [17] asked whether the communication complexity of I can be bounded from above by (log rank(M-f))(c), for some constant c. The question was answered affirmatively for a special class of functions f in [17], and Nisan and Wigderson proved nice results related to this problem [20], but, for arbitrary f, it remained a difficult open problem. We prove here an analogous polylogarithmic upper bound in the stronger multiparty communication model of Chandra et al. [6], which, instead of the rank of the communication matrix, depends on the L-I norm of function f, for arbitrary boolean function f.

关键词： complexity of boolean functions communication complexity Fourier coefficients

来源：评论

学校读者我要写书评

暂无评论

Harmonic analysis, real approximation, and the communication complexity of boolean functions 2nd

Harmonic analysis, real approximation, and the communication...

引用

2nd Annual International Computing and Combinatorics Conference (COCOON 1996)

作者： Grolmusz, V Eotvos Lorand Univ Dept Comp Sci H-1088 Budapest Hungary

ISBN: (纸本)9783540613329

关键词： complexity of boolean functions communication complexity Fourier coefficients

来源：评论

学校读者我要写书评

暂无评论

Identification of partial disjunction, parity, and threshold functions

引用

THEORETICAL COMPUTER SCIENCE 2000年第1-2期230卷 131-147页

作者： Uehara, R Tsuchida, K Wegener, I Komazawa Univ Fac Nat Sci Setagaya Ku Tokyo 1548525 Japan Toyo Univ Fac Engn Kawagoe Saitama 350 Japan Univ Dortmund FB Informat D-44221 Dortmund Germany

Let F be a class of functions obtained by replacing some inputs of a boolean function of a fixed type with some constants. The problem considered in this paper, which is called attribute efficient learning, is to identify "efficiently" a boolean function g out of F by asking for the value of g at chosen inputs, where "efficiency" is measured in terms of the number of essential variables. We study the query complexity of attribute-efficient learning for three function classes that are, respectively, obtained from disjunction, parity, and threshold functions. In many cases, we obtain almost optimal upper and lower bound on the number of queries. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： complexity of boolean functions attribute-efficient learning randomization

来源：评论

学校读者我要写书评

暂无评论

Computing boolean functions by polynomials and threshold circuits

引用

COMPUTATIONAL complexity 1998年第4期7卷 346-370页

作者： Krause, M Pudlák, P Univ Mannheim D-68131 Mannheim Germany Acad Sci Czech Republic Inst Math CR-11567 Prague 1 Czech Republic

We investigate the computational power of threshold-AND circuits versus threshold-XOR circuits. In contrast to the observation that, small weight threshold-AND circuits can be simulated by small weight threshold-XOR circuit, we present a function with small size unbounded weight threshold-AND circuits for which all threshold-XOR circuits have exponentially many nodes. This answers the basic question of separating subsets of the hypercube by hypersurfaces induced by sparse real polynomials. We prove our main result by a new lower bound argument for threshold circuits. Finally we show that unbounded weight threshold Rates cannot simulate alternation: There are AC(0,3)-functions which need exponential size threshold-AND circuits.

关键词： complexity of boolean functions threshold circuits circuit lower bounds representations by multivariate polynomials

来源：评论

学校读者我要写书评

暂无评论

The Logical complexity of Geometric Properties in the Plane

引用

Journal of the ACM (JACM) 1970年第2期17卷 339-347页

作者： Hodes, Louis Department of Health Education and Welfare Division of Computer Research and Technology National Institutes of Health Public Health Service United States

The logical complexity of some geometrical properties such as convexity and congruence in the plane is considered. These properties are characterized by the length of formulas necessary to express them. The main results show that certain formulations of congruence, convexity, area, and connectedness have only “nonlinear” realizations. These results are easy consequences of a recent theorem of Specker. This work is related to the concept of order of a geometric property introduced by Minsky and Papert. There are some striking differences, however, which are due to the fact that order is a measure of local complexity, while the measure of complexity used here is global. There are some limitations on measuring complexity in this manner, as one sees through the use of a switching circuit and a computer program in order to recognize patterns. © 1970, ACM. All rights reserved.

关键词： artificial intelligence complexity of boolean functions complexity of circuits complexity of congruence complexity of convexity geometrical complexity logical complexity logical design measures of complexity pattern recognition

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：