STOC

We present an algorithm that recognizes the class of General Series Parallel digraphs and runs in time proportional to the size of its input. To perform this recognition task it is necessary to compute the transitive reduction and transitive closure of ...

An O(EVlog²V) algorithm for finding the maximal flow in networks is described. It is asymptotically better than the other known algorithms if E = O(V^2-ε) for some ε>0. The analysis of the running time exploits the discovery of a phenomenon similar to (...

In this paper we present an algorithm which on input a graph G and a positive integer g finds an embedding of G on a surface on genius g, if such an embedding exists. This algorithm runs in (v) ^O(g) steps where v is the number of vertices of G.

We ...

A common operation in geometric computing is the decomposition of complex structures into more basic structures. Since it is easier to apply most algorithms to triangles or arbitrary convex polygons, there is considerable interest in finding fast ...

We introduce a notion of integrated cost of a dictionary, as average cost of sequences of search, insert and delete operations. We express generating functions of these sequences in terms of continued fractions; from this we derive an explicit integral ...

Let G denote the set of elements of a commutative group whose addition operations is denoted by +, let N be a positive integer, and let A(1) ,..., A(N) denote an array with values in G. We will be concerned with designing data structures for ...

The problem of searching for a given k-vector among a sorted list of n k-vectors is considered. The binary search is known to be optimal when k is 1. Here an almost optimal algorithm is presented for the 2-dimensional case. Interesting upper and lower ...

Given a function f over a finite domain D and an arbitrary starting point x, the sequence x,f(x),f(f(x)),... is ultimately periodic. Such sequences typically are used for constructing random number generators. The cycle problem is to determine the first ...

The complexity of the Discrete Fourier Transform (DFT) is studied with respect to a new model of computation appropriate to VLSI technology. This model focuses on two key parameters, the amount of silicon area and time required to implement a DFT on a ...

Deadlock is one of the most serious system failures that can occur in a computer system or a network. Deadlock states have been observed in existing computer networks emphasizing the need for carefully designed flow control procedures (controllers) to ...

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 ...

We consider representations of data structures in which the relative ordering of the values stored is implicit in the pattern in which the elements are retained, rather than explicit in pointers. Several implicit schemes for storing data are introduced ...

A recent trend in cryptographic systems is to base their encryption/decryption functions on NP-complete problems, and in particular on the knapsack problem. To analyze the security of these systems, we need a complexity theory which is less worst-case ...

We motivate, formalize, and study a computational problem in concrete inductive inference. A “pattern” is defined to be a concatenation of constants and variables, and the language of a pattern is defined to be the set of strings obtained by ...

It is shown that the class of relations (functions) definable by Presburger formulas is exactly the class of relations (functions) computable by finite-reversal multicounter machines.

An upper bound of 2^c(N/logN)4 on the deterministic time complexity of ...

However difficult the fundamental problems of theoretical computer science may seem, there is very little to suggest that they are anything more than knotty combinatorial problems. So, when we look for reasons for our inability to resolve P = NP and ...

In this paper, we show that by dropping the restrictions on interpretations of arbitrary programs and requiring only that very natural deductive systems are sound, we get classes of semantics which give good representations of program behavior and are ...

We show that “looping” of while-programs can be expressed in Regular First-Order Dynamic Logic, disproving a conjecture made in [Harel-Pratt 1978].

In addition we show that the expressive power of quantifier-free Dynamic Logic increases when ...

Strongly typed programming languages contain a natural subrecursive part consisting of programs with no loops and no explicitly recursive (circular) function definitions. For languages with polymorphic type structure, such as Model, the termination of ...

Among the most remarkable algorithms in algebra are Strassen's algorithm for the multiplication of matrices and the Fast Fourier Transform method for the convolution of vectors. For both of these problems the definition suggests an obvious algorithm ...

We consider the problem of computing a set of bilinear forms in the case when the indeterminates commute. We develop lower bound techniques which seem to be more powerful than those already known in the literature for the commutative case. An unexpected ...

Let M = {0, 1, 2, ..., m—1} , N = {0, 1, 2,..., n—1} , and f:M × N → {0, 1} a Boolean-valued function. We will be interested in the following problem and its related questions. Let i ε M, j ε N be integers known only to two persons P₁ and P₂, ...

There is a wide-spread belief among computer scientists that systems of communicating sequential processes are harder to analyze than purely sequential processes. The belief is largely based on the observation that the parallelism in such systems leads ...

The question of relative efficiencies is studied in the context of a simple model of communicating aynchronous processes. The fundamental problem is whether a simple distributed system, with arbitrary size variables, is any more powerful than a system ...

The parallel processing array consists of an n×n array of processors to which a cn² node directed graph can be input by placing c nodes at every point of the array. It is shown that every one of the following properties of the graph can be computed in ...

We examine a pebbling problem which has been used to study the storage requirements of various models of computation. Sethi has shown this problem to be NP-hard and Lingas has shown a generalization to be P-space complete. We prove the original problem ...

In the theory of recursive functions and computational complexity it has been demonstrated repeatedly that the natural problems tend to cluster together in “completeness classes”. These are families of problems that (A) are computationally ...

This paper derives asymptotically tight bounds on the time-space tradeoffs for pebbling three different classes of directed acyclic graphs. Let N be the size of the graph, S the number of available pebbles, and T the time necessary for pebbling the ...

We prove that a class of functions (denoted by NPC^P_t), whose graphs can be accepted in non-deterministic polynomial time, can be evaluated in deterministic polynomial time if and only if γ-reducibility is equivalent to polynomial time many-one ...

We consider two-person games of incomplete information in which certain portions of positions are private to each player and cannot be viewed by the opponent. We present various games of incomplete information which are universal for all reasonable ...