We investigate the nondeterministic state complexity of basic operations for prefix-free regular languages. The nondeterministic state complexity of an operation is the number of states that are necessary and sufficient in the worst-case for a minimal nondeterministic finite-state automaton that accepts the language obtained from the operation. We establish the precise state complexity of catenation, union, intersection, Kleene star, reversal and complementation for prefix-free regular languages.

We present lower and upper bounds on adaptive heuristics for maintaining binary search trees using a constant number of link or pointer changes for each operation (constant linkage cost (CLC)). We show that no adaptive heuristic with an amortized linkage cost of o(log n) can be competitive. In particular, we show that any heuristic that performs f(n)=o(log n) promotions (rotations) amortized over each access has a competitive ratio of at least $\Omega(\log n/f(n))$ against an oblivious adversary, and any heuristic that performs f(n)=o(log n) pointer changes amortized over each access has a competitive ratio of at least $\Omega(\frac{\log n}{f(n)\log(\log n/f(n))})$ against an adaptive online adversary. In our investigation of upper bounds we present four adaptive heuristics: a randomized, worst-case-CLC heuristic randomized two-promotion (R2P) whose expected search time is within a constant factor of the search time using an optimal tree; that is, it is statically competitive against an oblivious adversary; a randomized, expected-CLC heuristic (locally optimized randomized partial splay (LORPS)) that has O(log n) expected-amortized update time and is statically competitive against an oblivious adversary; a deterministic, amortized-CLC heuristic (locally optimized partial splay (LOPS)) that has O(log n) amortized update time and is statically competitive against an adaptive adversary; a practical, randomized heuristic (randomized partial splay (RPS)) that is not CLC but has performance bounds comparable with those of the splay heuristic of Sleator and Tarjan; it is statically competitive against an adaptive adversary. The randomized heuristics use only constant extra space, whereas the deterministic heuristic uses O(n) extra space.

It is shown that the external path length of a binary tree is closely related to the ratios of means of certain integers and establish the upper bound External Path Length ≤ N(log 2 N + Δ - log 2 Δ - 0.6623), where N denotes the number of external nodes in the tree and Δ is the difference in length between a longest and shortest path. Then it is proved that this bound is tight up to an o(N) term if Δ ≤ √N. If Δ > √N , we contstruct binary trees whose external path length is at least as large as N(log 2 N + Φ(N, Δ)Δ - log 2 Δ -4) , where Φ(N, Δ) = 1/(1 + 2(Δ/N)) .

CSAB states in its guidelines that one of its six undergraduate core curriculum subject areas is computer theory. It appears that the ACM Core Curriculum Committee will also suggest a core course in this area. However, courses in computer theory, under the titles “Formal Languages” or “Theory of Computation”, have traditionally been taught on the senior or graduate level. There has been little discussion concerning the development of a computer theory course for use at the sophomore or junior level. Also, computer theory is also becoming a larger part of other computer science courses such as discrete structures and compiler design theory. A clearer understanding is needed of how different aspects of computer theory should be developed throughout the undergraduate computer science curriculum.

Given a set of n rectangles with sides parallel to the coordinate axes, we show how to determine whether their union, viewed as a set of disjoint polygons, has a hole. The algorithm presented needs no more than $O( n\log n )$ time and $O( n )$ space, which is shown to be optimal. However, in practice it is also necessary to know the locations of holes, if there are any. We present an algorithm to determine the locations of all h holes in $O( n\log n + h )$ time and $O( n )$ space, which is again optimal. The algorithm computes a point within each hole, representing the location of the hole. The efficiency of these and several other algorithms follows from some simple combinatorial arguments about sets of rectangles in the plane.

First, we propose a general framework that captures many of the variations on visibility found in the literature. Second, we investigate two specific variations: rectangular and square visibility.

We consider the separation of rebalancing from updates in several database structures, such as B-trees for external and AVL-trees for internal structures. We show how this separation can be implemented such that rebalancing is performed by local background processes. Our solution implies that even simple locking schemes (without additional links and copies of certain nodes) for concurrency control are efficient in the sense that at any time only a small constant number of nodes must be locked.

Given a point set in plane and a fixed planar region (window) a window query consists of enumerating the points in a translate of the region. A recently presented result shows that a static data structure of optimal size enables window queries for convex regions in optimal time. We show that if the windows are (maybe non-convex) polygons another data structure of optimal size supports not only window queries in optimal time but also allows updating of the point set in optimal time.

Given a simple orthogonal polygon, that is a simple polygon whose edges are parallel to the axes, we wish to determine an inscribed convex orthogonal polygon of maximal area. This is the orthogonal version of the potato peeling problem. We present an Ο(n2) time algorithm to solve it, which is a substantial improvement over the Ο(n7 time algorithm for the general problem.

We investigate three cost measures for the recently introduced brother search trees. In particular we characterize node visit optimal, comparison-cost optimal and space-cost optimal 1-2 brother trees and present linear-time algorithms to construct optimal 1-2 brother trees for each cost measure. Furthermore we also consider, briefly, these cost measures for brother leaf search trees.

In this correspondence we reconsider three geometrical problems for which we develop divide-and-conquer algorithms. The first problem is to find all pairwise intersections among a set of horizontal and vertical line segments. The second is to report all points enclosures occurring in a mixed set of points and rectangles, and the third is to find all pairwise intersections in a set of isooriented rectangles. We derive divide-and-conquer algorithms for the first two problems which are then combined to solve the third. In each case a space-and time-optimal algorithm is obtained, that is O(n) space and O(n log n + k) time, where n is the number of given objects and k is the number of reported pairs. These results show that divide-and-conquer can be used in place of line sweep, without additional asymptotic cost, for some geometrical problems. This raises the natural question: For which class of problems are the line sweep and divide-and-conquer paradigms interchangeable?

We introduce a new class of binary search trees, the height-ratio-balanced binary search trees, as the height based analogy of weight (−ratio) balanced binary search trees. They form a proper subclass of the class of binary search trees, but not a logarithmic one, indeed an n node height-ratio balanced tree of order α,0≤α≤1/3, has a worse case height of μmgr]eμ+0(1), where μ=(−2ln(α/(1-a))ln(n)}1/2. This result indicates that these naturally defined trees should not be used to implement the DICTIONARY operations, in practical situations.

For every triple (k, /, m) of nonnegaUve integers, every context-free grammar G can be transformed rote a normal form where (1) each nontermmating production is of the type A ~ wkBwtCw,~ with I wk [ = k, I wll --/, and I w,~ [ = m, and 00 each terminating producUon A ~ w has the property that I wl appears m the length set of L(G).Apphcations and generalizations of this result are discussed.

Various notions are introduced for the closure of a set of rectilinearly oriented rectangles on the plane. Optimal algorithms are presented for computing the closures. These algorithms imply optimal solutions to several problems related to database concurrency control.

A technique ts presented for constructing dense hierarchies of grammatical subfamthes of context-free languages The question of "where" such dense hierarchies may lie is also investigated Infinite hierarchies of successors are studied.The major open problems concern questions deahng with fimte grammar forms Categories and SubJect Descriptors.F 4 3 ]

We present a solution to the problem of reporting and counting all pairs of intersecting or overlapping d-ranges in a given set of n d-ranges. A d-range is a rectilinearly oriented rectangular d-dimensional box or brick. The three-dimensional case is presented in some detail and an 0(n log22n + k) time and 0(n log22n) space algorithm is developed for the reporting problem, where k is the number of reported intersecting pairs. This gives an 0(n log22n) time and 0(n log2n) space algorithm for the counting problem. Apart from its usefulness wherever a "bounding boxes" technique is used, the development of the algorithm is of interest in its own right because of the data structures that are introduced and because of the technique used to reduce the time needed for preprocessing. Finally, the algorithm is generalized to give an 0(2d−1n log2d−n+ k) time and an 0(2d−1n log2d−n) space algorithm for the d-range intersection reporting problem for d ≥ 2, which again reduces to an 0(2d−1n log2d−1n) time and 0(2d−1n log2d−2n) space algorithm for the counting problem. Finally, we sketch how the reporting problem can be carried out with the same space requirements as the counting problem. The bounds presented are the best known to date.

In this paper we study the problem of supporting concurrent operations in B-trees and their variants. A survey of previous work is given and two basic types of solutions to this problem are identified. A new solution with a greater degree of concurrency is proposed. As solutions are surveyed or presented we identify useful techniques which have wider applicability. In particular, we introduce the technique of side-branching in our new solution.

Encouraged by positive experiences with so-called uniform-interpretations of L-forms, we investigate in this paper a suitable analogous definition of uniform interpretations of grammar forms. Concerning CF grammar forms it is shown that a rich variety of language families can be obtained. CF grammar forms with a single variable are extensively examined both with regard to generative capacity (including a characterization of subregular, sublinear and subfinite index families) and with regard to the notion of goodness and badness. Concerning non-CF grammar forms it is shown that each of the families of EOL-, ETOL-, matrix-, scattered context-, context sensitive, type 0-languages (and many others) can be obtained by using interpretations of one form specific to this family.

B-trees of order m are a “balanced” class of m -ary trees, which have applications in the areas of file organization. In fact, they have been the only choice when balanced multiway trees are required. Although they have very simple insertion and deletion algorithms, their storage utilization, that is, the number of keys per page or node, is at worst 50 percent. In the present paper we investigate a new class of balanced m -ary trees, the dense multiway trees, and compare their storage utilization with that of B-trees of order m . Surprisingly, we are able to demonstrate that weakly dense multiway trees have an Ο (log 2 N ) insertion algorithm. We also show that inserting m h - 1 keys in ascending order into an initially empty dense multiway tree yields the complete m -ary tree of height h , and that at intermediate steps in the insertion sequence the intermediate trees can also be considered to be as dense as possible. Furthermore, an analysis of the limiting dynamic behavior of the dense m -ary trees under insertion shows that the average storage utilization tends to 1; that is, the trees become as dense as possible. This motivates the use of the term “dense.”

In recent years B-trees have become a common data structure for representing large data dictionaries. In this paper we investigate the often ignored relationship between routing schemes and the permissible operations in leaf-search B-trees. We show that among the many commonly used routing schemes in the literature, some are cleaner than others, making them more attractive for leaf-search B-trees supporting concurrency.

1-2 brother trees are binary search trees which have similarities to both height balanced search trees and 2-3 trees. Firstly, 0(log2n) insertion and deletion algorithms are demonstrated and their similarities with those for brother trees are noted. Secondly, it is proved that the space utilisation of (random) 1-2 brother trees is much better than that for (random) 2-3 trees. Thirdly, the close relationship between 1-2 brother trees and height balanced trees is demonstrated, and as this also holds for their right-sided counterparts it leads to 0(log2n) insertion and deletion algorithms for right-sided height balanced trees. Finally, this demonstrates that the insertion and deletion algorithms for right-sided height balanced trees were already available, but hidden, in the corresponding algorithms for right brother trees.

In this paper we investigate the problem of reporting all intersecting pairs in a set of n rectilinearly oriented rectangles in the plane. This problem arises in applications such as design rule checking of very large-scale integrated (VLSI) circuits and architectural databases. We describe an algorithm that solves this problem in worst case time proportional to n lg n + k, where k is the number of interesecting pairs found. This algorithm is optimal to within a constant factor. As an intermediate step of this algorithm, we solve a problem related to the range searching problem that arises in database applications. Although the algorithms that we describe are primarily theoretical devices (being very difficult to code), they suggest other algorithms that are quite practical.

We review the motivation underlying the study of data encodings and the formal framework of the study. We then present a series of results whose main message is that (complete) trees are materially less congenial storage representations for tree-like data structures than they have been shown to be for array-like data structures. In response to these results, we propose a new data structure, called a dree, which we show to share the advantages of trees, but not to suffer their disadvantages, when used as a storage structure.

This paper continues the study of EOL forms. The notion of a good EOL form is introduced as an important generalization of the notion of complete and very complete EOL forms. Transformations preserving the property good are obtained and the existence of a variety of good and bad (i.e. not good) forms is demonstrated. It is further shown that good and complete (i.e. vomplete) EOL forms do exist; that propagating EOL forms are bad except under very special circumstances; and that synchronized EOL forms are always bad.

Two variations on a basic model, n–parallel finite state generators, are given. One variation causes the model to degenerate, so that only regular sets are generated and the second variation produces new families of languages.

The implementation of locally balanced binary search tree construction is described. Empirical investigation reveals that locally balanced trees are either superior or inferior to other more recent methods available in the literature, depending upon the chosen measurement criteria.

A brief introduction to four areas of theoretical research in computer science and bibliographies for these areas are presented. A common factor in each of these areas is one of parallelism and the study of its effects.

Two new families of languages, the F(k) and U(k) languages, are introduced each of which is, in some sense, a generalisation of top-down deterministic languages. This leads us to new characterisations of s-languages and LL(1) languages. We include a characterisation of the unambiguous context-free languages, generalisations of the equivalence relation on s-grammars to s-separable sets, a summary of the non-closure results for LL(k), F(k) and U(k) languages, and it is shown that non-degenerate hierarchies exist for the families of F(k) and U(k) languages.

In the first part of this paper left-factored grammars and languages were introduced and their relevance to syntax-directed top-down analysers discussed. A number of results concerning these languages were proved and a number of problems were posed. In this second part further results are proved, further problems are posed and conclusions are reached.

Generalised versions of the Greibach Normal Form Theorem are presented and proved, together with the introduction of two new classes of grammars.

An alternative proof of the normal form theorem for context-free languages is given. A series of simple constructions lead to the result. The proof makes use of a practical method of removing left cycles due to Foster.

Left factored grammars and languages are introduced and their relevance to syntax-directed top-down analysers is discussed. A number of results concerning these languages are proved, including the decidability of left factored grammars. Finally a number of open problems are posed.