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

space complexity of estimation of distribution algorithms

EVOLUTIONARY COMPUTATION 2005年第1期13卷 125-143页

作者： Gao, Y Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

In this paper, we investigate the space complexity of the Estimation of Distribution Algorithms (EDAs), a class of sampling-based variants of the genetic algorithm. By analyzing the nature of EDAs, we identify criteria that characterize the space complexity of two typical implementation schemes of EDAs, the factorized distribution algorithm and Bayesian network-based algorithms. Using random additive functions as the prototype, we prove that the space complexity of the factorized distribution algorithm and Bayesian network-based algorithms is exponential in the problem size even if the optimization problem has a very sparse interaction structure.

关键词： estimation of distribution algorithms space complexity additive fitness functions graphical models and bayesian networks treewidth

来源：评论

学校读者我要写书评

暂无评论

space complexity of exact discrete geodesic algorithms on regular triangulations

引用

INFORMATION PROCESSING LETTERS 2017年 124卷 10-14页

作者： Liu, Yong-Jin Fan, Dian Xu, Chunxu He, Ying Tsinghua Univ Dept Comp Sci & Technol Tsinghua Natl Lab Informat Sci & Technol Beijing Peoples R China Nanyang Technol Univ Sch Comp Engn Singapore Singapore

Computing geodesic distances on 2-manifold meshes is a fundamental problem in computational geometry. To date, two notable classes of exact algorithms, namely, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been widely studied. For an arbitrary triangle mesh with n vertices, these algorithms have space complexity of O(n(2)). In this paper, we prove that both algorithms have circle minus(n(1.5)) space complexity on a completely regular triangulation (i.e., all triangles are equilateral). (C) 2017 Elsevier B.V. All rights reserved.

关键词： Discrete geodesics space complexity Regular triangulation Computational complexity

来源：评论

学校读者我要写书评

暂无评论

space complexity of reachability testing in labelled graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2019年第0期105卷 40-53页

作者： Ramaswamy, Vidhya Sarma, Jayalal Sunil, K. S. Indian Inst Technol Madras Dept Comp Sci & Engn Chennai Tamil Nadu India

Fix an algebraic structure (A, *). Given a graph G = (V, E) and the labelling function phi (phi: E -> A) for the edges, two nodes s, t is an element of V, and a subset F subset of A, the A-REACH problem asks if there is a path p (need not be simple) from s to t whose yield (result of the operation in the ordered set of the labels of the edges constituting the path) is in F. On the complexity frontier of this problem, we show the following results. When A is a group whose size is polynomially bounded in the size of the graph (hence equivalently presented as a multiplication table at the input), and the graph is undirected, the A-REACH problem is in L Building on this, using a decomposition in [4], we show that, when A is a fixed quasi-group, and the graph is undirected, the A-REACH problem is in L In a contrast, we show NL-hardness of the problem over bidirected graphs, when A is a matrix group over Q, or an aperiodic monoid. As our main theorem, we prove a dichotomy for graphs labelled with fixed aperiodic monoids by showing that for every fixed aperiodic monoid A, A-REACH problem is either in L or is NL-complete. We show that there exists a monoid M, such that the reachability problem in general DAGs can be reduced to A-REACH problem for planar non-bipartite DAGs labelled with M. In contrast, we show that if the planar DAGs that we obtain above are bipartite, the problem can be further reduced to reachability testing in planar DAGs and hence is in UL. (C) 2019 Elsevier Inc. All rights reserved.

关键词： space complexity Algebraic reachability Dichotomy Word problems

来源：评论

学校读者我要写书评

暂无评论

space complexity of perfect matching in bounded genus bipartite graphs

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2012年第3期78卷 765-779页

作者： Datta, Samir Kulkarni, Raghav Tewari, Raghunath Vinodchandran, N. V. Indian Inst Technol Kharagpur 721302 W Bengal India Chennai Math Inst Madras Tamil Nadu India Univ Chicago Chicago IL 60637 USA Univ Nebraska Lincoln NE USA

We investigate the space complexity of certain perfect matching problems over bipartite graphs embedded on surfaces of constant genus (orientable or non-orientable). We show that the problems of deciding whether such graphs have (1) a perfect matching or not and (2) a unique perfect matching or not, are in the log-space complexity class Stoic Probabilistic Log-space (SPL). Since SPL is contained in the log-space counting classes circle plus L (in fact in Mod(k) L for all k >= 2), C=L, and PL, our upper bound places the above-mentioned matching problems in these counting classes as well. We also show that the search version, computing a perfect matching, for this class of graphs can be performed by a log-space transducer with an SPL oracle. Our results extend the same upper bounds for these problems over bipartite planar graphs known earlier. As our main technical result, we design a log-space computable and polynomially bounded weight function which isolates a minimum weight perfect matching in bipartite graphs embedded on surfaces of constant genus. We use results from algebraic topology for proving the correctness of the weight function. (C) 2011 Elsevier Inc. All rights reserved.

关键词： space complexity Perfect matching Topological graph theory

来源：评论

学校读者我要写书评

暂无评论

space complexity of TCP for Persistent Packet Reordering

引用

IEICE TRANSACTIONS ON COMMUNICATIONS 2010年第6期E93B卷 1601-1604页

作者： Lim, Chansook Hongik Univ Fac Comp Yeongi Gun Chungnam South Korea Hongik Univ Informat Commun Engn Dept Yeongi Gun Chungnam South Korea

This letter investigates the space complexity of the sender buffer in a TCP variant, TCP-PR, to deal with packet reordering. Our finding is that with the SACK option used, TCP-PR requires the sender buffer of (beta + ... 详细信息

关键词： TCP packet reordering sender buffer space complexity

来源：评论

学校读者我要写书评

暂无评论

space complexity of Stack Automata Models

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2021年第6期32卷 801-823页

作者： Ibarra, Oscar H. Jirasek, Jozef, Jr. McQuillan, Ian Prigioniero, Luca Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA Univ Saskatchewan Dept Comp Sci Saskatoon SK S7N 5A9 Canada Univ Milan Dipartimento Informat Via Celoria 18 Milan Italy

This paper examines several measures of space complexity of variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept every word in the language of the automaton (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves like a linear function, or it can not be bounded by any function of the length of the input word (and it is decidable which case occurs). However, this result does not hold for non-erasing stack automata;we provide an example where the space complexity grows proportionally to the square root of the length of the input. Furthermore, we study the complexity bounds of machines which accept a given language, and decidability of space complexity properties.

关键词： Checking stack automata stack automata pushdown automata space complexity machine models

来源：评论

学校读者我要写书评

暂无评论

space complexity of Stack Automata Models 1

引用

24th International Conference on Developments in Language Theory (DLT)

ISBN: (数字)9783030485160

ISBN: (纸本)9783030485153;9783030485160

This paper examines several measures of space complexity on variants of stack automata: non-erasing stack automata and checking stack automata. These measures capture the minimum stack size required to accept any word in a language (weak measure), the maximum stack size used in any accepting computation on any accepted word (accept measure), and the maximum stack size used in any computation (strong measure). We give a detailed characterization of the accept and strong space complexity measures for checking stack automata. Exactly one of three cases can occur: the complexity is either bounded by a constant, behaves (up to small technicalities explained in the paper) like a linear function, or it grows arbitrarily larger than the length of the input word. However, this result does not hold for non-erasing stack automata;we provide an example when the space complexity grows with the square root of the input length. Furthermore, an investigation is done regarding the best complexity of any machine accepting a given language, and on decidability of space complexity properties.

关键词： Checking stack automata Stack automata Pushdown automata space complexity Machine models

来源：评论

学校读者我要写书评

暂无评论

space complexity of Streaming Algorithms on Universal Quantum Computers 16th

Space Complexity of Streaming Algorithms on Universal Quantu...

引用

16th International Conference on Theory and Applications of Models of Computation (TAMC)

作者： Hu, Yanglin Melnyk, Darya Wang, Yuyi Wattenhofer, Roger Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9783030592660;9783030592677

Universal quantum computers are the only general purpose quantum computers known that can be implemented as of today. These computers consist of a classical memory component which controls the quantum memory. In this paper, the space complexity of some data stream problems, such as PartialMOD and Equality, is investigated on universal quantum computers. The quantum algorithms for these problems are believed to outperform their classical counterparts. Universal quantum computers, however, need classical bits for controlling quantum gates in addition to qubits. Our analysis shows that the number of classical bits used in quantum algorithms is equal to or even larger than that of classical bits used in corresponding classical algorithms. These results suggest that there is no advantage of implementing certain data stream problems on universal quantum computers instead of classical computers when space complexity is considered.

关键词： Streaming algorithm Universal quantum computer space complexity Solovay-Kitaev algorithm

来源：评论

学校读者我要写书评

暂无评论

On the space complexity of turn bounded pushdown automata

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 2003年第3期80卷 295-304页

作者： Moriya, E Tada, T Waseda Univ Sch Educ Dept Math Shinjuku Ku Tokyo 1698050 Japan Waseda Univ Media Network Ctr Tokyo 1698050 Japan

A pushdown automaton is said to make a turn at a given instant if it changes at that instant from stack increasing to stack decreasing. Let NPDA-TURN(f(n)) and DPDA-TURN(f(n)) denote the classes of languages accepted by nondeterministic and deterministic pushdown automata respectively that make at most f(n) turns for any input of length n. In this paper the following inclusions that express the space complexity of turn bounded pushdown automata are given: DPDA-TURN(f(n)) subset of or equal to Dspace(logf(n) log n), and NPDA-TURN(f(n)) subset of or equal to Nspace (logf(n) log n). In particular, it follows that finite-turn pushdown automata are logarithmic space bounded: DPDA-TURN(O(1)) subset of or equal to DL and NPDA-TURN(O(1)) subset of or equal to NL, from which two corollaries follow: one is that the class of metalinear context-free languages is complete for NL, and the other is that a more tight inclusion NPDA-TURN(f(n)) subset of or equal to Dspace(log(2)f(n) log n) cannot be derived unless DL = NL, though NPDA-TURN (f(n)) subset of or equal to Dspace(log(2)f(n) log(2) n) holds.

关键词： pushdown automaton turn (head reversal) space complexity

来源：评论

学校读者我要写书评

暂无评论

space complexity of Fault-Tolerant Register Emulations 17

Space Complexity of Fault-Tolerant Register Emulations

引用

36th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Chockler, Gregory Spiegelman, Alexander Royal Holloway Univ London Dept Comp Sci Egham TW20 0EX Surrey England Technion Viterbi Dept Elect Engn Haifa Israel

ISBN: (纸本)9781450349925

Driven by the rising popularity of cloud storage, the costs associated with implementing reliable storage services from a collection of fault-prone servers have recently become an actively studied question. The well-known ABD result shows that an f-tolerant register can be emulated using a collection of 2f + 1 fault-prone servers each storing a single read-modify-write object, which is known to be optimal. In this paper we generalize this bound: we investigate the inherent space complexity of emulating reliable multi-writer registers as a function of the type of the base objects exposed by the underlying servers, the number of writers to the emulated register, the number of available servers, and the failure threshold. We establish a sharp separation between registers, and both max-registers (the base object type assumed by ABD) and CAS in terms of the resources (i.e., the number of base objects of the respective types) required to support the emulation;we show that no such separation exists between max-registers and CAS. Our main technical contribution is lower and upper bounds on the resources required in case the underlying base objects are fault-prone read/write registers. We show that the number of required registers is directly proportional to the number of writers and inversely proportional to the number of servers.

关键词： Faulty shared memory reliable emulations space complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：