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

International Symposium on Parallel Processing

作者： C.R. Asthagiri J.L. Potter CIS Department Cleveland State University Cleveland OH USA Department of Math. & Computer Science Kent University Kent OH USA

Presents near constant time associative parallel lexing (APL) algorithms. The best time complexity thus far claimed is O(logn) (n denotes the number of input characters for the parallel prefix lexing (PPL) algorithm. The linear state recording step in the PPL algorithm, which needs to be done only once for each grammar has been ignored in claiming the log n time complexity for the PPL algorithm. Furthermore, the PPL algorithm does not consider recording line numbers for the tokens and distinguishing identifier tokens as keywords or user-identifiers. The APL algorithms perform all of these functions. Thus, without considering the efforts spent on these functions, the APL algorithm takes constant time since every step depends on the length of the tokens, not on the length of the input. Generalizing and including these extra functions, the APL algorithm takes near constant time.< >

关键词： Concurrent computing computer aided instruction Algorithm design and analysis Associative memory Computational Intelligence Society Lakes Performance analysis Vector processors computer science Process control

来源：评论

学校读者我要写书评

暂无评论

Modeling human visual object recognition

Modeling human visual object recognition

引用

International Joint Conference on Neural Networks (IJCNN)

作者： S. Edelman H.H. Bulthoff Department of Applied Mathematics and Computer Science Weizmann Institute of Science Rehovot Israel Dept. of Appl. Math. & Comput. Sci. Weizmann Inst. of Sci. Rehovot Israel

The topics discussed here are network models of object recognition; a computational theory of recognition; psychophysical support for a view-interpolation model: and an open issue, features of recognition. The authors survey a successful replication of central characteristics of performance in 3-D object recognition by a computational model based on interpolation among a number of stored views of each object. Network models of 3-D object recognition based on interpolation among specific stored views behave in several respects similarly to human observers in a number of recognition tasks. Even closer replication of human performance in recognition should be expected, once the issue of the features used to represent object views is resolved.< >

关键词： Humans Object recognition Image recognition computer networks Biology computing math.matics computer science math.matical model Interpolation Image resolution

来源：评论

学校读者我要写书评

暂无评论

Optimal early stopping in distributed consensus 6th

Optimal early stopping in distributed consensus

引用

6th International Workshop on Distributed Algorithms, WDAG 1992

作者： Berman, Piotr Garay, Juan A. Perry, Kenneth J. Department of Computer Science The Pennsylvania State University University ParkPA16802 United States Dept. of Applied Math and Computer Science The Weizmann Institute of Science Rehovot76100 Israel IBM T.J. Watson Research Center P.O. Box 704 Yorktown HeightsNY10598 United States

ISBN: (纸本)9783540561880

The Distributed Consensus problem involves n processors each of which holds an initial binary value. At most t processors may be faulty and ignore any protocol (even behaving maliciously), yet it is required that the non-faulty processors eventually agree on a value that was initially held by one of them. This paper presents consensus protocols that tolerate arbitrary faults, are early-stopping (i.e., run for a number of rounds proportional to the number of faults f that actually occur during their execution), and are optimal in various measures. Our first contribution is an early-stopping consensus protocol that is simultaneously optimal in round complexity (i.e., min(t+1, f+2) rounds) and number of processors (i.e., n > 3t). This settles a long-standing open question [DRS, 1982]. These bounds were not known to be attainable even with the use of authentication. Since consensus is not attainable with n ≤ 3t we provide a definitive answer to the problem of early-stopping consensus. Previous protocols for this problem that achieved round optimality required n = Ω(t2) [C, DRS], n > 6t [MW] and n > 4t [BGP]. Instrumental in achieving this result is the new safe message reconstruction technique, which we expect to be of broader applicability. The previous protocol is round- and processor-optimal, but not efficient. Our second contribution is a pair of optimal early-stopping consensus protocols that use messages of constant size. No previously existing early-stopping protocol, whether exactly or only asymptotically optimal in some measures, has used messages of constant size. The only other existing early-stopping protocol with constant-sized messages requires n = Ω(t2) [C]. Finally, we indicate how to extend one of the previous protocols to be optimal in total bit (and message) complexity and number of processors. This is the first protocol that is both optimal in these measures and early-stopping. © 1992, Springer Verlag. All rights reserved.

关键词： Artificial intelligence

来源：评论

学校读者我要写书评

暂无评论

Witnesses for Boolean matrix multiplication and for shortest paths 33

Witnesses for Boolean matrix multiplication and for shortest...

引用

33rd Annual Symposium on Foundations of computer science, FOCS 1992

作者： Alon, Noga Galil, Zvi Margalit, Oded Naor, Moni Dept. of Math. Tel Aviv Univ. Israel Department of Computer Science Tel Aviv University Tel Aviv69978 Israel Columbia University New YorkNY10027 United States IBM Almaden Research Center San JoseCA95120 United States

ISBN: (纸本)0818629002

The subcubic (O(nw) for w(3) algorithms to multiply Boolean matrices do not provide the witnesses;namely, they compute C=A.B but if Cij=1 they do not find an index k (a witness) such that Aik=Bkj=1. The authors design a deterministic algorithm for computing the matrix of witnesses that runs in O(nw) time, where here O(nw) denotes O(nw(log n)/sup O(1)/). The subcubic methods to compute the shortest distances between all pairs of vertices also do not provide for witnesses;namely they compute the shortest distances but do not generate information for computing quickly the paths themselves. A witness for a shortest path from vi to vj is an index k such that vk is the first vertex on such a path. They describe subcubic methods to compute such witnesses for several versions of the all pairs shortest paths problem. As a result, they derive shortest paths algorithms that provide characterization of the shortest paths in addition to the shortest distances in the same time (up to a polylogarithmic factor) needed for computing the distances;namely O(n/sup (3+w)/2/) time in the directed case and O(nw) time in the undirected case. They also design an algorithm that computes witnesses for the transitive closure in the same time needed to compute witnesses for Boolean matrix multiplication. © 1992 IEEE.

关键词： Matrix algebra

来源：评论

学校读者我要写书评

暂无评论

Amplification and percolation (probabilistic Boolean functions)

Amplification and percolation (probabilistic Boolean functio...

引用

Annual IEEE Symposium on Foundations of computer science

作者： M. Dubiner U. Zwick Department of Applied Math Tel-Aviv University Tel-Aviv Israel Department of Computer Science Tel-Aviv University Tel-Aviv Israel

The authors extend R.B. Boppana's results (1989) in two ways. They first show that his two lower bounds hold for general read-once formulae, not necessarily monotone, that may even include exclusive-or gates. They are then able to join his two lower bounds together and show that any read-once, not necessarily monotone, formula that amplifies (p-/sup 1///sub n/,p+/sup 1///sub n/) to (2/sup -n/,1-2/sup -n/) has size of at least Omega (n/sup alpha +2/). This result does not follow from Boppana's arguments and it shows that the amount of amplification achieved by L.G. Valiant (1984) is the maximal achievable using read-once formulae.< >

关键词： Boolean functions computer science Relays computer network reliability Polynomials Circuit simulation

来源：评论

学校读者我要写书评

暂无评论

Data-parallel compilation and query power extension of large knowledge bases

Data-parallel compilation and query power extension of large...

引用

International Conference on Tools for Artificial Intelligence (ICTAI)

作者： A.K. Bansal J.L. Potter L.V. Prasad Dept. of Math. & Comput. Sci. Kent State Univ. OH USA Department of Mathematics and Computer Science Kent University Kent OH USA

An associative data-parallel compilation model of logic programs capable of answering queries with unspecified relations concerning the given objects is described. The model benefits from the synergy resulting from associative search, data-parallelism during goal reduction, and the use of low-level code to invoke the subgoals and savings in data-transfers resulting from the presence of global registers. The use of associative tables extends the power of logic programming to answer a large class of queries and derive unspecified relation-names for the given objects. In contrast to the interpretation based on a pure data parallel model, this model does not suffer from data sequentiality caused by the presence of multiple-occurrence variables in the goals. The model also handles variable aliasing in the clauses efficiently using the associative data-parallel search and data-parallel assignment property.< >

关键词： Pattern matching Supercomputers Artificial intelligence Logic programming math.matics computer science math.matical model Parallel processing Registers Knowledge representation

来源：评论

学校读者我要写书评

暂无评论

Model based concordance compression

Model based concordance compression

引用

Data Compression Conference (DCC)

作者： A. Bookstein S.T. Klein T. Raita Center for Information and Language Studies University of Chicago Chicago IL USA Departments of Math. & CS and Economics & BA Bar-llan University Ramat-Gan Israel Department of Computer Science University of Turku Turku Finland

The authors discuss concordance compression using the framework now customary in compression theory. They begin by creating a math.matical model of concordance generation, and then use optimal compression engines, such as Huffman or arithmetic coding, to do the actual compression. It should be noted that in the context of a static information retrieval system, compression and decompression are not symmetrical tasks. Compression is done only once, while building the system, whereas decompression is needed during the processing of every query and directly affects the response time. One may thus use extensive and costly preprocessing for compression, provided reasonably fast decompression methods are possible. Moreover, compression is applied to the full files (text, concordance, etc.), but decompression is needed only for (possibly many) short pieces, which may be accessed at random by means of pointers to their exact locations. Therefore the use of adaptive methods based on tables that systematically change from the beginning to the end of the file is ruled out. However, their concern is less the speed of encoding or decoding than relating concordance compression conceptually to the modern approach of data compression, and testing the effectiveness of their models.< >

关键词： Dictionaries Information retrieval Databases Data structures Gallium nitride computer science math.matical model Engines Arithmetic Delay

来源：评论

学校读者我要写书评

暂无评论

The algorithmic aspects of the regularity lemma 33

The algorithmic aspects of the regularity lemma

引用

33rd Annual Symposium on Foundations of computer science, FOCS 1992

作者： Alon, N. Duke, R.A. Lefmann, H. Rödl, V. Yuster, R. Dept. of Math. Raymond and Beverly Sackler Faculty of Exact Sciences Tel Aviv Univ. Tel Aviv Israel Bellcore MorristownNJ07960 United States School of Mathematics Georgia Institute of Technology AtlantaGA30332 United States Fakultat fur Mathematik SFB 343 Universitat Bielefeld Bielefeld 1W-4800 Germany Department of Mathematics and Computer Science Emory University AtlantaGA30322 United States

ISBN: (纸本)0818629002

The regularity lemma of Szemeredi (1978) is a result that asserts that every graph can be partitioned in a certain regular way. This result has numerous applications, but its known proof is not algorithmic. The authors first demonstrate the computational difficulty of finding a regular partition;they show that deciding if a given partition of an input graph satisfies the properties guaranteed by the lemma is co-NP-complete. However, they also prove that despite this difficulty the lemma can be made constructive;they show how to obtain, for any input graph, a partition with the properties guaranteed by the lemma, efficiently. The desired partition, for an n-vertex graph, can be found in time O(M(n)), where M(n)=O(n/sup 2.376/) is the time needed to multiply two n by n matrices with 0,1-entries over the integers. The algorithm can be parallelized and implemented in NC1. © 1992 IEEE.

关键词： computers

来源：评论

学校读者我要写书评

暂无评论

Analysis of the tap changer related voltage collapse phenomena for the large electric power system

Analysis of the tap changer related voltage collapse phenome...

引用

IEEE Conference on Decision and Control

作者： V. Venkatasubramanian H. Schattler J. Zaborszky School of Electrical Engineering and Computer Science Washington State University Pullman WA USA Department of Systems Science and Mathematics Washington University Saint Louis MO USA Dept. of Syst. Sci. & Math. Washington Univ. St. Louis MO USA

It is shown that nonsmooth events, such as tap changing can be integrated into the framework of a general theory recently presented by the authors (1991,1992) on the dynamics of large power systems modeled by smooth equations. The boundary to the region of feasible operations starting at a stable operating point, the feasibility boundary, is shown to be composed of five types of segments including two types connected with tap changers. These segments are defined as zero sets of explicitly known functions and thus are relatively computable (at roughly the load flow level). These results offer a powerful new approach to system security when tap changers are present. No reference needs to be made to P-V curves of the large power system, an obstacle in more conventional approaches.< >

关键词： Voltage Power system dynamics Power system modeling Power system security Power system analysis computing Equations Load flow

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON A NEW THEORY OF TURBULENCE

引用

applied math.matics and Mechanics(English Edition) 1991年第1期12卷 101-105页

作者：蔡树棠林多敏 Department of Modern Mechanics University of Science and Technology of China Hefei Shanghai Institute of Applied Math. and Mechanics Shanghai Shanghai University of Technology Shanghai

In this paper, the creation and annihilation of turbulent eddies are described as elementary particles in the quantum field theory. An elementary particle mav be considered as a solid entity as it exists in quantum theory, but a turbulent eddy is often changed in size and shape with time due to its energy dissipation in a turbulent field. Therefore, in order to apply the method of the quantum field theory to the turbulent field by analogy, the entity of the same eddy should be defined firstly According to the linearized theory, the turbulent eddies with the similarity character in time duration may be considered as the entity of the same eddy, and the creation and annihilation of turbulent eddies without the similar characters are related to the interaction term in equation (2.6). Then, the creation operator and annihilation operator similar-to those in the quantum field theory are used to describe the state of turbulent eddy field. Finally, a 'Schrddinger' equation of turbulent eddies is formulated based upon the nonlinear terms in the original N- S equation. Thus, a new turbulent eddy interaction theory similar to the quantum field theory is obtained.

关键词： turbulent eddies creation and annihilation of turbulent eddies turbulent eddy interaction

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：