Space Complexity Vs. Query Complexity

Combinatorial property testing deals with the following relaxation of decision problems: Given a fixed property and an input x, one wants to decide whether x satisfies the property or is “far” from satisfying it. The main focus of property testing is in identifying large families of properties that can be tested with a certain number of queries to the input. In this paper we study the relation between the space complexity of a language and its query complexity. Our main result is that for any space complexity s(n) ≤ log n there is a language with space complexity O(s(n)) and query complexity 2^Ω(s(n)). Our result has implications with respect to testing languages accepted by certain restricted machines. Alon et al. [FOCS 1999] have shown that any regular language is testable with a constant number of queries. It is well known that any language in space o(log log n) is regular, thus implying that such languages can be so tested. It was previously known that there are languages in space O(log n) that are not testable with a constant number of queries and Newman [FOCS 2000] raised the question of closing the exponential gap between these two results. A special case of our main result resolves this problem as it implies that there is a language in space O(log log n) that is not testable with a constant number of queries. It was also previously known that the class of testable properties cannot be extended to all context-free languages. We further show that one cannot even extend the family of testable languages to the class of languages accepted by single counter machines.      

Time and Space Issues in the Generation of Graph Transition Systems

GROOVE is a tool for the automatic generation of graph transition systems from graph grammars. In this type of tool, both memory and time performance are of prime importance. In this paper we discuss the implementation techniques used for optimising the tool in this regard, and we list possible future improvements.     

Control of Dynamics of Systems with Space and Time Integral Models

Problems of system dynamics control with an integral model in a bounded space and time domain are solved. The cases of control of distributed external dynamic disturbances and boundary conditions on internal and external domain contours are considered.     

Infinite String Rewrite Systems and Complexity

We study the relation between time complexity and derivation work for the word problem of infinitely presented semigroups and groups. We introduce the notion of theworkof a derivation (defined as the sum of the lengths of all the rules used in the derivation, with multiplicity). The following results are proved:     

具有反馈延迟特性系统的最优控制器设计及其算法实现

针对反馈传感器具有延迟特性的一类系统,提出了三自由度Ｗｉｅｎｅｒ－Ｈｏｐｆ最优控制器设计方法,并给出了状态空间实现算法。最后通过仿真实例证明了该方法的有效性。     

OFDM系统中基于能量效率的低复杂度算法的研究与仿真

早先的无线通信传输主要以频谱效率为设计标准,在保证用户服务质量的同时,对有限的资源进行合理的分配从而得到较好的系统性能。关于频谱效率的研究主要是在系统发射功率有限的情况下并考虑用户公平性的同时,最大化系统的容量。而随着各种高速无线通信服务的应用越来越广泛,以及无处不在的无线接入使得能量的消耗越来越多。而对于电池容量有限的移动终端来说是一个较大的瓶颈。与此同时,无线网络的能量消耗的产生了越来越多的温室气体,并加重了运营费用。因此,以能量效率为设计准则的绿色通信越来越得到重视并成为未来无线网络设计的准则。本文提出了一种OFDM系统中基于能量效率的复杂度较低。本文首先提出了OFDM系统中能量效率的优化模型,接着采用经典的注水法,求出了最优的功率分配。通过仿真证明了该算法是最优的。     

Space Functions and Space Complexity of the Word Problem in Semigroups

We introduce the space function s(n) of a finitely presented semigroup ${S =\langle A \mid R \rangle}$ . To define s(n) we consider pairs of words w,w′ over A of length at most n equal in S and use relations from R for the derivations ${w = w_0 \rightsquigarrow \dots \rightsquigarrow w_t = w'; s(n)}$ bounds from above the lengths of the words w _i at intermediate steps, i.e., the space sufficient to implement all such transitions ${w \rightsquigarrow \dots \rightsquigarrow w'}$ . One of the results obtained is the following criterion: A finitely generated semigroup S has decidable word problem of polynomial space complexity if and only if S is a subsemigroup of a finitely presented semigroup H with polynomial space function.     

连续属性离散化算法的时间复杂性分析

对几个常用的连续属性离散化算法的时间复杂性进行分析,并纠正文献[3]第107页与第111页中几处对离散化算法的时间复杂性分析的缺陷。     

时间复杂度的几种计算方法

算法的时间复杂度是反映算法优劣的重要指标,是《数据结构》的重要理论基础,是学习和教学过程中贯穿始终的主要线索。但是由于概念的抽象和计算方法的繁琐,使算法时间复杂度成为最难理解和掌握的问题之一。在总结教学经验的基础上,该文提出几种常用的时间复杂度计算方法,使对该知识点的教学和学习变得系统和简单。     

演化算法的时间复杂性

演化算法在工程领域取得了广泛的应用,但是其基础理论尚未完全建立。文章讨论了演化算法的时间复杂性,提出一个估计(1+1)EA平均计算时间的简单方法,对几个实例的应用显示了该方法分析演化算法计算时间的有效性。     

k分搜索的时间复杂度分析

分治策略的思想是将一个规模较大的问题分解为多个形式相同的子问题来解决。搜索是指在一个排好序的数组中寻找与给定数值x相等的元素,传统的搜索算法是遍历,而二分搜索是一种基于分治策略的搜索算法。二分搜索是将数组每次分为相等的两部分,将待查元素x与数组中间的元素比较,若相等则搜索成功;否则将搜索范围缩小为原来的一半,之后以此类推,直到找到待查元素,与遍历相比,二分搜索复杂度明显降低。以二分搜索为基础,每次可以将数组分为更多部分,即k分搜索,探寻k为何值时k分搜索算法的时间复杂度最低,能够对搜索算法进一步优化。通过分析、归纳与证明,得出k分搜索的时间复杂度为O(klog_kn),由于该函数是递增的,因此二分搜索是效率最高的搜索算法,复杂度为O(log₂n);此外,当k=n时,k分搜索退化为遍历,复杂度退化为O(n)。     

Complexity of Solving Tropical Linear Systems

An algorithm is designed for solving a tropical linear system with complexity polynomial in the size of the system.     

Formalization of Time and Space

Time and space limitations can be specified, and proven, in exactly the same way as functionality. Proofs of time bounds, both implementation-independent and real-time, and of space requirements, both worst-case and average-case, are given in complete detail. Received May 1997 / Accepted in revised form July 1998     

Interaction in Time and Space

Distributed π-calculus and ambient calculus are extended with timers which may trigger timeout recovery processes. Timers provide a useful notion of relative time with respect to the interaction in a distributed system. The rather flat notion of space in timed distributed π-calculus is improved by considering a hierarchical representation of space in timed mobile ambients. Some basic results are proven, making sound both formal approaches. An easily understood example is used for both extensions, showing how it is possible to describe a non-monotonic behaviour and use a decentralized control to coordinate the interacting components in time and space.     

浅析算法设计与算法时间复杂度

算法设计与算法时间复杂度分析是数据结构中研究算法的重要内容。本文主要介绍如何针对实际问题设计效率较高的算法以及对算法的时间复杂度进行分析的方法。     

含有纯滞后系统的控制方法

针对时滞对象的控制问题,着重选取几种控制方法,考虑模型失配,时滞大小及干扰作用等因素,进行仿真,比较控制性能,以期对含有大时滞的实际对象的控制起到方法上的指导作用,结果表明,其中预测PI和内模PID两种控制方法响应速度快,超调量小,对模型失配的鲁棒性强,抗干扰能力好,时滞时间越长,越能体现出其优越性,是在克服纯滞后所产生影响的较好的控制方法。     

Exponential Separation of Quantum and Classical Online Space Complexity

Although quantum algorithms realizing an exponential time speed-up over the best known classical algorithms exist, no quantum algorithm is known performing computation using less space resources than classical algorithms. In this paper, we study, for the first time explicitly, space-bounded quantum algorithms for computational problems where the input is given not as a whole, but bit by bit. We show that there exist such problems that a quantum computer can solve using exponentially less work space than a classical computer. More precisely, we introduce a very natural and simple model of a space-bounded quantum online machine and prove an exponential separation of classical and quantum online space complexity, in the bounded-error setting and for a total language. The language we consider is inspired by a communication problem (the disjointness function) that Buhrman, Cleve and Wigderson used to show an almost quadratic separation of quantum and classical bounded-error communication complexity. We prove that, in the framework of online space complexity, the separation becomes exponential.     

Color Space Quantization for Color-Content-Based Query Systems

Color histograms are widely used in most of color content-based image retrieval systems to represent color content. However, the high dimensionality of a color histogram hinders efficient indexing and matching. To reduce histogram dimension with the least loss in color content, color space quantization is indispensable. This paper highlights and emphasizes the importance and the objectives of color space quantization. The color conservation property is examined by investigating and comparing different clustering techniques in perceptually uniform color spaces and for different images. For studying color spaces, perceptually uniform spaces, such as the Mathematical Transformation to Munsell system (MTM) and the C.I.E. L*a*b*, are investigated. For evaluating quantization approaches, the uniform quantization, the hierarchical clustering, and the Color-Naming-System (CNS) supervised clustering are studied. For analyzing color loss, the error bound, the quantized error in color space conversion, and the average quantized error of 400 color images are explored. A color-content-based image retrieval application is shown to demonstrate the differences when applying these clustering techniques. Our simulation results suggest that good quantization techniques lead to more effective retrieval.