International Journal of Foundations of Computer Science

In this paper, we introduce a new variant of implicit heaps, called relaxed inorder heaps. The structure is semi-implicit due to the use of 1 extra bit per node to maintain heap order and the allowance of some systematically controlled extra space. We show that relaxed inorder heaps are asymptotically more efficient than other known variants of implicit heaps. In particular, relaxed inorder heaps are especially efficient for heap merging and splitting operations, which are known to be problematic operations for implicit heaps.

Using amortized analysis, we derive several improved time bounds. Heap creation can be done in O(n) comparisons and node movements. Finding the minimum node and node insertion can each be done in O(1) comparisons and node movements. Key updating and node deletion can each be done in O(log n) comparisons and node movements. As for merging, we show that O(1) comparisons and 2k+O(1) node movements are sufficient for merging two heaps of sizes n and k. For splitting, we show that O(log n) comparisons and 1.5k+O(log n) node movements are sufficient for splitting an n-node implicit heap into two heaps of sizes k and n−k. The amount of extra space in a relaxed inorder heap is O(log n) if splitting does not occur, and O(n) otherwise.

The significance of our results is that small sophistication in the structure of implicit heaps can produce large improvements in efficiency. We have implemented the algorithms for operations on relaxed inorder heaps. The simulation results strongly indicate that relaxed inorder heaps are practical, since the constant factors recorded for the heap operations are all very small.

What is the semantics of Negation-as-Failure in logic programming? We try to answer this question by proof-theoretic methods. A rule based sequent calculus is used in which a sequent is provable if, and only if, it is true in all three-valued models of the completion of a logic program. The main theorem is that proofs in the sequent calculus can be transformed into SLDNF-computations if, and only if, a program has the cut-property. A fragment of the sequent calculus leads to a sound and complete semantics for SLDNF-resolution with substitutions. It turns out that this version of SLDNF-resolution is sound and complete with respect to three-valued possible world models of the completion for arbitrary logic programs and arbitrary goals. Since we are dealing with possibly nonterminating computations and constructive proofs, three-valued possible world models seem to be an appropriate semantics.

Quite often a camera that is shooting a video sequence swings or rocks (for example the camera is hand held). For compression of digitized video it can be important to compensate for the motion of the camera by realigning the frames, shifting them one respect to the other, absorbing the movement of the camera. We show that for the general version of optimal frame alignment, the Vector Alignment problem is NP-complete. Moreover we prove that the Run Length Coding Alignment problem, a restricted subcase of the Vector Alignment problem that has direct application in video compression, can be solved in linear time by a dynamic programming algorithm.

Although numerous researchers have pointed out that object-oriented software is easier to extend than software that is not written in an object-oriented style, object-oriented software is still rigid to adapt and maintain. This paper builds on an extension of object-oriented programming which is called adaptive programming. Adaptive programming allows the programmer to write more extensible software called adaptive software without committing to a specific input language. After writing an adaptive program, the programmer selects a specific input language and partially evaluates the program into an executable program. This paper formally studies class dictionaries and informally describes how adaptive programs are partially evaluated by freezing class dictionaries.

A class dictionary is mapped into classes of an object-oriented programming language, for example, C++, CLOS etc. A class dictionary defines both a set of objects and a set of sentences (a language). We derive a set of restrictions on class dictionaries which permit a simple printing algorithm and its inverse, a parsing algorithm, to be bijection functions between objects and sentences of the same class.

We review propagation patterns for describing adaptive object-oriented software at a higher level of abstraction than the one used by today’s object-oriented programming languages. A propagation pattern is an adaptive program which defines a family of programs. From the family, we can select a member by choosing a class dictionary.

The theory presented in this paper has been successfully implemented and used in the Demeter Tools/C++. The system consists of a set of tools that facilitate software evolution.

We investigate the problem of when it is possible to efficiently construct an instance of a given language in P or NP, based on partial information provided about the desired instance. We model this problem by specifying a prefix and a length for the string to be produced. Our results suggest that it may be harder to find efficient constructors for languages in NP if more information is provided about the desired element (assuming that P is not equal to NP). Specifically, for large enough prefix functions, polynomial-time prefix-based constructors cannot exist for all languages in NP unless P=NP. For smaller prefix functions, the existence of such constructors cannot be determined using techniques that relativize, under the assumption that P≠NP. We also show through relativizations and other results, what appears to be a pattern of increasing difficulty for efficient construction as the prefix function increases within this range. For languages in P, however, the difficulty of construction first increases and then appears to decrease as the size of the prefix is increased. We also relate prefix-based construction to that based on more general parameter functions for the strings. In addition, we examine the related ranking problem in the same context, and prove some results about the existence of prefix-based rankers for languages in P and NP.