Characterizing History Independent Data Structures

We consider history independent data structures as proposed for study by Naor and Teague. In a history independent data structure, nothing can be learned from the memory representation of the data structure except for what is available from the abstract data structure. We show that for the most part, strong history independent data structures have canonical representations. We provide a natural alternative definition of strong history independence that is less restrictive than Naor and Teague and characterize how it restricts allowable representations. We also give a general formula for creating dynamically resizing history independent data structures and give a related impossibility result.     

基于局部堆内存抽象表示的堆操作程序内存泄露检测

堆操作程序通过共享易变数据结构可灵活地申请、合并、删除堆内存.这类程序的内存泄漏检测要求精确的域敏感的指针别名信息,变得尤其复杂和难以处理.针对这个问题,提出了基于“指针扩展类型”域敏感的堆内存抽象方法,对指针变量在形态上的排列关系进行抽象以支持堆的局部推理.首先,定义了各种基本语句的操作语义,然后基于该抽象方法采用前向数据流迭代算法提出了一种新的内存泄露检测算法.在Crystal编译框架下实现了面向C程序的内存泄漏检测原型工具Heapcheck,该工具支持复杂数据结构内指针型数据域上的内存泄露检测.在典型基准C程序上的实验结果分析表明,该方法与现有的技术相比在效率和精度上都具有优势.     

Queaps

A new priority queue structure, the queap, is introduced. The queap executes insertion in O(1) amortized time and extract-min in O(log (k+2)) amortized time if there are k items that have been in the heap longer than the item to be extracted. Thus if the operations on the queap are first-in first-out, as on a queue, each operation will execute in constant time. This idea of trying to make operations on the least recently accessed items fast, which we call the queueish property, is a natural complement to the working set property of certain data structures, such as splay trees and pairing heaps, where operations on the most recently accessed data execute quickly. However, we show that the queueish property is in some sense more difficult than the working set property by demonstrating that it is impossible to create a queueish binary search tree, but that many search data structures can be made almost queueish with a O(log logn) amortized extra cost per operation.     

Three priority queue applications revisited

Results indicate that the two recently introduced self-adjusting heaps are the most competitive choices for the applications considered. Further, the results indicate that only some heap structures support lazymerge/lazydelete operations well, partially confirming that algorithms based on top-down skew heap compare more favorably than those based on binomial queues, that there are strong grounds for believing the conjectured amortized time bounds for pairing heap operations, and that pairing heaps are a competitive alternative to Fibonacci heaps.     

面向顺序存储结构的数据流分析

C程序中数组、malloc动态分配后的连续内存等顺序存储结构被大量使用,但大多数传统的数据流分析方法未能充分描述其结构及其上的操作,特别是在利用指针访问顺序存储结构时,传统的分析方法只关注了指针的指向关系,而未讨论指针可能发生偏移的数值信息,且未考虑发生偏移时可能存在越界的不安全问题,导致了对顺序存储结构分析不精确.针对以上不足,首先对顺序存储结构进行抽象建模,并对顺序存储结构与指针结合使用时的指向关系与偏移量进行有效表示,建立了用于顺序存储结构的抽象内存模型SeqMM;其次,归纳总结C程序中顺序存储结构涉及的指针相关迁移操作、谓词操作及遍历顺序存储结构的循环操作,提出了安全范围判别保证操作安全性;之后,针对函数调用时形参指针引用顺序存储结构与实参的映射过程进行过程间推导规则设计;最后,基于上述分析,提出了一种内存泄漏缺陷检测算法,对5个开源C工程的内存泄漏缺陷进行检测.实验结果表明,所提出的Seq MM能够有效地刻画C程序中的顺序存储结构及其涉及的各种操作,其数据流分析结果能够用于内存泄漏的检测工作,同时在效率和精度之间取得合理的权衡.     

Stability, queue length, and delay of deterministic and stochasticqueueing networks

We present two types of stability problems: 1) conditions for queueing networks that render bounded queue lengths and bounded delay for customers, and 2) conditions for queueing networks in which the queue length distribution of a queue has an exponential tail with rate &thetas;. To answer these two types of stability problems, we introduce two new notions of traffic characterization: minimum envelope rate (MER) and MER with respect to &thetas;. We also develop a set of rules for network operations such as superposition, input-output relation of a single queue, and routing. Specifically, we show that: 1) the MER of a superposition process is less than or equal to the sum of the MER of each process, 2) a queue is stable in the sense of bounded queue length if the MER of the input traffic is smaller than the capacity, 3) the MER of a departure process from a stable queue is less than or equal to that of the input process, and 4) the MER of a routed process from a departure process is less than or equal to the MER of the departure process multiplied by the MER of the routing process. Similar results hold for MER with respect to &thetas; under a further assumption of independence. For single class networks with nonfeedforward routing, we provide a new method to show that similar stability results hold for such networks under the first come, first served policy. Moreover, when restricting to the family of two-state Markov modulated arrival processes, the notion of MER with respect to &thetas; is shown to be equivalent to the recently developed notion of effective bandwidth in communication networks     

Three priority queue applications revisited

Results indicate that the two recently introduced self-adjusting heaps are the most competitive choices for the applications considered. Further, the results indicate that only some heap structures support lazymerge/lazydelete operations well, partially confirming that algorithms based on top-down skew heap compare more favorably than those based on binomial queues, that there are strong grounds for believing the conjectured amortized time bounds for pairing heap operations, and that pairing heaps are a competitive alternative to Fibonacci heaps.This work was carried out during the author's final graduate year (1987) at Rensselaer Polytechnic Institute. Though the author is currently with Thomson Financial Networks, this is an unaffiliated paper.     

Isolating an Odd Number of Elements and Applications in Complexity Theory

Naor and Naor [11] implicitly isolate an odd number of elements of a nonempty set of n -bit vectors. We perform a tighter analysis of their construction and obtain better probability bounds. Using this construction, we improve bounds on several results in complexity theory that originally used a construction due to Valiant and Vazirani [18]. In particular, we obtain better bounds on polynomials which approximate boolean functions; improve bounds on the running time of the ⊕ P machine in Toda's result [16]; and improve bounds on the size of threshold circuits accepting languages accepted by AC ⁰ circuits. Received July 1993, and in revised form January 1995, and in final form February 1997.     

Detecting loop-carried dependences in programs with dynamic data structures

The problem of data dependences detection in codes based on dynamic data structures, is crucial to various compiler optimizations. The approach presented in this paper focuses on detecting data dependences induced by heap-directed pointers on loops that access dynamic data structures. Knowledge about the shape of the data structure accessible from a heap-directed pointer provides critical information for disambiguating heap accesses originating from it. The new approach is based on a previously developed shape analysis that maintains topological information of the connections among the different nodes (memory locations) in the data structure. As a novelty, our approach carries out abstract interpretation of the statements being analyzed, annotating memory locations with read/write information. This information will be later used in a very accurate data dependence test which we describe in this paper. We also discuss its application to several different benchmarks.     

Bisimulation from Open Maps

An abstract definition of bisimulation is presented. It makes possible a uniform definition of bisimulation across a range of different models for parallel computation presented as categories. As examples, transition systems, synchronisation trees, transition systems with independence (an abstraction from Petri nets), and labelled event structures are considered. On transition systems the abstract definition readily specialises to Milner's strong bisimulation. On event structures it explains and leads to a strengthening of the history-preserving bisimulation of Rabinovitch and Traktenbrot and van Glabeek and Goltz. A tie-up with open maps in a (pre)topos, as they appear in the work of Joyal and Moerdijk, brings to light a new model, presheaves on categories of pomsets, into which the usual category of labelled event structures embeds fully and faithfully. As an indication of its promise, this new presheaf model has “refinement” operators. The general approach yields a logic, generalising Hennessy–Milner logic, which is characteristic for the generalised notion of bisimulation.     

Encoding, Decoding and Data Refinement

Data refinement is the systematic replacement of a data structure with another one in program development. Data refinement between program statements can on an abstract level be described as a commutativity property where the abstraction relationship between the data structures involved is represented by an abstract statement (a decoding). We generalise the traditional notion of data refinement by defining an encoding operator that describes the least (most abstract) data refinement with respect to a given abstraction. We investigate the categorical and algebraic properties of encoding and describe a number of special cases, which include traditional notions of data refinement. The dual operator of encoding is decoding, which we investigate and give an intuitive interpretation to. Finally we show a number of applications of encoding and decoding. Received May 1999 / Accepted in revised form November 2000     

A modular approach to defining and characterising notions of simulation

We propose a modular approach to defining notions of simulation, and modal logics which characterise them. We use coalgebras to model state-based systems, relators to define notions of simulation for such systems, and inductive techniques to define the syntax and semantics of modal logics for coalgebras. We show that the expressiveness of an inductively defined logic for coalgebras w.r.t. a notion of simulation follows from an expressivity condition involving one step in the definition of the logic, and the relator inducing that notion of simulation. Moreover, we show that notions of simulation and associated characterising logics for increasingly complex system types can be derived by lifting the operations used to combine system types, to a relational level as well as to a logical level. We use these results to obtain Baltag’s logic for coalgebraic simulation, as well as notions of simulation and associated logics for a large class of non-deterministic and probabilistic systems.     

An Experiment in Abstract Machine Design

In this article we present Typed Feature Structures as an extension of Prolog, and show how to come up with a compilation scheme and an abstract machine using a design methodology based on partial evaluation. First we define the transformations used by our partial evaluator. Then we present the design methodology which we will use later. Next, we clarify the notion of Typed Feature Structures that underlies our work, and formally define the unification of such structures. Based on this definition, we develop a unification procedure with explicit heap representation. By partially evaluating this procedure with respect to some example programs, we show how to come up with the machine instructions and translation schemes. Finally, we briefly address coreferences, cyclic structures and the unification of types. © 1997 by John Wiley & Sons, Ltd.     

Refined complexity analysis for heap operations

A heap (priority queue) is a data structure for representing a set of items, each item having an associated numerical value, which facilitates such operations as insertion, deletion, merge (union), and findmin (find the item having the minimum value). It is well known that when n items are present the inherent complexity of these operations (in terms of comparisons) is logn per operation in the worst case. However, Cheriton and Tarjan have observed that when the frequency of findmin operations is small relative to the frequency of other operations, then certain implementations of heaps perform better than logn per operation. We explore this phenomenon with respect to inherent complexity.     

Workload bounds in fluid models with priorities

In this paper we establish upper and lower bounds on the steady-state per-class workload distributions in a single-server queue with multiple priority classes. Motivated by communication network applications, the model has constant processing rate and general input processes with stationary increments. The bounds involve corresponding quantities in related models with the first-come first-served discipline. We apply the bounds to support a new notion of effective bandwidths for multi-class systems with priorities. We also apply the lower bound to obtain sufficient conditions for the workload distributions to have heavy tails.     

A rational reconstruction of the domain of feature structures

Feature structures are employed in various forms in many areas of linguistics. Informally, one can picture a feature structure as a sort of tree decorated with information about constraints requiring that specific subtrees be identical (isomorphic). Here I show that this informal picture of feature structures can be used to characterize exactly the class of feature structures under their usual subsumption ordering. Furthermore, once a precise definition of tree is fixed, this characterization makes use only of standard domain-theoretic notions regarding the information borne by elements in a domain, thus removing (or better, explaining) all apparentlyad hoc choices in the original definition of feature structures. In addition, I show how this characterization can be parameterized in order to yield similar characterizations of various different notions of feature structure, including acyclic structures, structures with appropriateness conditions and structures with apartness conditions (used to model path inequations). The generalizations to other notions of feature structure also emphasize that the construction given here is in fact independent of the application to feature structures.This research has been supported by the Deutsche Forschungsgemeinschaft as part of Sonderforschungsbereich 314, Projekt N3.     

The relative power of logspace and polynomial time reductions

There exist many different formalisms to model the notion of resource bounded truth-table reduction. Most papers in which truthtable reductions appear refer to the seminal paper of Ladner, Lynch and Selman for a definition. The definition of truth-table reductions given there however, pertains to only one of the possible incarnations of the notion. For larger resource bounds, this definition often coincides with other-often implicitly used-definitions of the notion. In this paper we focus our attention on resource bounds for which the various definitions probably donot pertain to the same notion. In particular, we show that coincidence of different notions implies coincidence of complexity classes likeNC ₁,LOG, andP, which are widely believed to be different.     

Prolog语言抽象机器GOAM的设计与实现

本文提出了一种抽象机ＧＯＡＭ,是Ｐｒｏｌｏｇ语言新的运行和实现方式,因为ＧＯＡＭ内存管理是一种堆式内存分配方法,所以具有潜在的并行性,另外ＧＯＡＭ控制算法是智能回溯方法,ＧＯＡＭ在没有引入冗余信息的情况下提高了系统的效率。