A family of NP-complete data aggregation problems

Summary We consider a family of general aggregation problems and prove each of its members to be NP-complete in the strong sense. These problems require that we partition a set of objects into aggregates. The goal is to minimize the expected cost of satisfying an anticipated collection of requests for subsets of the objects, where the cost of satisfying a request includes both the number and the sizes of the aggregates which must be retrieved. The aggregation problems are viewed as very basic versions of important database optimization problems, including: the partitioning of data items into record types, the clustering of records into physical blocks of storage, and the partitioning of a database into granules to support locking. The NP-completeness results demonstrate that such optimization problems are intractable, even when simplified to the extreme. The fact that the problems are NP-complete in the strong sense also rules out pseudopolynomial time solutions, unless P = NP.     

Efficient removal of boundary-divergence errors in time-splitting methods

A normal mode analysis is presented and numerical tests are performed to assess the effectiveness of a new time-splitting algorithm proposed recently in Karniadakiset al. (1990) for solving the incompressible Navier-Stokes equations. This new algorithm employs high-order explicit pressure boundary conditions and mixed explicit/implicit stiffly stable time-integration schemes, which can lead to arbitrarily high-order accuracy in time. In the current article we investigate both the time accuracy of the new scheme as well as the corresponding reduction in boundary-divergence errors for two model flow problems involving solid boundaries. The main finding is that time discretization errors, induced by the nondivergent splitting mode, scale with the order of the accuracy of the integration rule employed if a proper rotational form of the pressure boundary condition is used; otherwise a first-order accuracy in time similar to the classical splitting methods is achieved. In the former case the corresponding errors in divergence can be completely eliminated, while in the latter case they scale asO(vt)_1/2.     

The construction of cubature formulae for a family of integrals: A bifurcation problem

Cubature formulae of degree 11 with minimal numbers of knots for the integral $$\int\limits_{ - 1}^1 { \int\limits_{ - 1}^1 {(1 - x^2 )^\alpha } } (1 - y^2 )^\alpha f(x,y) dxdy \alpha > - 1$$ which are invariant under rotation over an angle π/2 are determined by a system of 18 nonlinear equations in 18 unknowns. We start with a known solution for this system for α=0. By varying α smoothly, the knots and weights of the cubature formula vary smoothly except in the singular solutions such as turning points and bifurcation points where new solutions branches arise. We use for this purpose the program AUTO. We obtain surprisingly many branches of cubature formulae.     

On finding optimal and near-optimal lineal spanning trees

The search for good lineal, or depth-first, spanning trees is an important aspect in the implementation of a wide assortment of graph algorithms. We consider the complexity of findingoptimal lineal spanning trees under various notions of optimality. In particular, we show that several natural problems, such as constructing a shortest or a tallest lineal tree, are NP-hard. We also address the issue of polynomial-time, near-optimization strategies for these difficult problems, showing that efficient absolute approximation algorithms cannot exist unlessP = NP.     

一个PASCAL结构编辑器的设计与实现

本文对一个新的PASCAL结构编辑编辑器PSE（PASCAL Structured Editor）的系统结构和功能进行了概括的描述。在设计和实现PSE时,作者提出了一种新的程序内部表示法,即所谓“文本-树”表示。与以往的程序内部表示相较,这种表示方法具有占用内存量小,光标控制及编辑操作简便以及无须进行内部语法树与行式文件间的转换等特点。实践证明,基于此种表示的语法制导编辑器是易于实现的,其工作效率是较高的。     

A self-adjusting algorithm for byzantine agreement

Summary Byzantine Agreement is important both in the theory and practice of distributed computing. However, protocols to reach Byzantine Agreement are usually expensive both in the time required as well as in the number of messages exchanged. In this paper, we present a self-adjusting approach to the problem. The Mostly Byzantine Agreement is proposed as a more restrictive agreement problem that requires that in the consecutive attempts to reach agreement, the number of disagreements (i.e., failures to reach Byzantine Agreement) is finite. Fort faulty processes, we give an algorithm that has at mostt disagreements for 4t or more processes. Another algorithm is given forn3t+1 processes with the number of disagreements belowt ²/2. Both algorithms useO(n ³) message bits for binary value agreement. Yi Zhao is currently working on his Ph.D. degree in Computer Science at University of Houston. His research interests include fault tolerance, distributed computing, parallel computation and neural networks. He obtained his M.S. from University of Houston in 1988 and B.S. from Beijing University of Aeronautics and Astronautics in 1984, both in computer science. Farokh B. Bastani received the B. Tech. degree in electrical engineering from the Indian Institute of Technology, Bombay, India, and the M.S. and Ph.D. degrees in electrical engineering and computer science from the University of California, Berkeley. He joined the University of Houston in 1980, where he is currently an Associate Professor of Computer Science. His research interests include software design and validation techniques, distributed systems, and fault-tolerant systems. He is a member of the ACM and the IEEE and is on the editorial board of theIEEE Transactions on Software Engineering.     

CLP(ℜ) and some electrical engineering problems

The Constraint Logic Programming Scheme defines a class of languages designed for programming with constraints using a logic programming approach. These languages are soundly based on a unified framework of formal semantics. In particular, as an instance of this scheme with real arithmetic constraints, the CLP() language facilitates and encourages a concise and declarative style of programming for problems involving a mix of numeric and non-numeric computation.In this paper we illustrate the practical applicability of CLP() with examples of programs to solve electrical engineering problems. This field is particularly rich in problems that are complex and largely numeric, enabling us to demonstrate a number of the unique features of CLP(). A detailed look at some of the more important programming techniques highlights the ability of CLP() to support well-known, powerful techniques from constraint programming. Our thesis is that CLP() is an embodiment of these techniques in a language that is more general, elegant and versatile than the earlier languages, and yet is practical.An earlier version of this paper appeared in the proceedings of the 4th International Conference on Logic Programming, Melbourne, May 1987. Much of this work was carried out while the authors were at Monash University, Melbourne, Australia.     

QUICK: a tool for graphical user-interface construction by non-programmers

The last decade has placed the superiority of graphical user interfaces over traditional text-based approaches beyond dispute. In almost all contexts, users have found graphical interfaces easier to learn, faster to use, and less error-prone. However, it has been shown that the creation of powerful graphical interfaces takes up to 80% of the time required to develop an application. In our work, we seek to extend the benefits of graphical interaction to the next layer of computer user—the interface designer. Our work in this area is distinguished from other efforts by two important differences. First, while other efforts focus primarily on the design of standard user interfaces, our approach emphasizes the creation of unique and innovative interfaces by supporting, among other things, arbitrary user-designed graphical representations, direct specification of animation, and digitized sound. Second, our goal is to cater to the nonprogrammer. Thus, we address a challenging trade-off: maximizing power and flexibility in an extremely simple environment. We explore the utility of the prototype object-oriented paradigm, a high-level userinterface language, and a direct-manipulation programming environment in this context.     

Parallel heap: An optimal parallel priority queue

We describe a new parallel data structure, namely parallel heap, for exclusive-read exclusive-write parallel random access machines. To our knowledge, it is the first such data structure to efficiently implement a truly parallel priority queue based on a heap structure. Employing p processors, the parallel heap allows deletions of (p) highest priority items and insertions of (p) new items, each in O(log n) time, where n is the size of the parallel heap. Furthermore, it can efficiently utilize processors in the range 1 through n.This work was supported by U.S. Army's PM-TRADE contract N61339-88-g-0002, Florida High Technology and Industry grant 11-28-716, and Georgia State University's internal research support during spring and summer quarters, 1991.     

Supporting inconsistent rules in database systems

When a set of rules generates (conflicting) values for a virtual attribute of some tuple, the system must resolve the inconsistency and decide on a unique value that is assigned to that attribute. In most current systems, the conflict is resolved based on criteria that choose one of the rules in the conflicting set and use the value that it generated. There are several applications, however, where inconsistencies of the above form arise, whose semantics demand a different form of resolution. We propose a general framework for the study of the conflict resolution problem, and suggest a variety of resolution criteria, which collectively subsume all previously known solutions. With several new criteria being introduced, the semantics of several applications are captured more accurately than in the past. We discuss how conflict resolution criteria can be specified at the schema or the rule-module level. Finally, we suggest some implementation techniques based on rule indexing, which allow conflicts to be resolved efficiently at compile time, so that at run time only a single rule is processed.An earlier version of this work appeared under the title Conflict Resolution of Rules Assigning Values to Virtual Attributes inProceedings of the 1989 ACM-Sigmod Conference, Portland, OR, June 1989, pp. 205–214.Partially supported by the National Science Foundation under Grant IRI-9157368 (PYI Award) and by grants from DEC, HP, and AT&T.Partially supported by the National Science Foundation under Grant IRI-9057573 (PYI Award), IBM, DEC, and the University of Maryland Institute for Advanced Computer Studies (UMIACS).