STOC

Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. An 0(n²) algorithm is presented to find an almost minimum circuit. The straightforward algorithm for ...

Let P be a polyhedron with f_s s-dimensional faces. We show that Ω(log f_s) linear comparisons are needed to determine if a point lies in P. This is used to establish an Ω(n² log n) lower bound to the all-pairs shortest path problem between n points.

This paper describes a machine model intended to be useful in deriving realistic complexity bounds for tasks requiring list processing. As an example of the use of the model, the paper shows that any such machine requires non-linear time in the worst ...

The main purpose of this paper is to give techniques for analysing the probabilistic performance of certain kinds of algorithms, and hence to suggest some fast algorithms with provably desirable probabilistic behaviour. The particular problems we ...

A notion of priority queue efficiency is defined, based on comparison counting. A good lower bound on the average and worst case number of comparisons is derived; several priority queue algorithms are exhibited which nearly attain the bound. It is shown ...

We present a new data structure for maintaining a set of records in a linear list according to their key values. This data structure has the property that we can keep a number of fingers at points of interest in the key space (e.g., the beginning or the ...

Let V be a finite set of integral vectors in Euclidian N-space, and let a be an integral point in the first orthant of N-space. The reachability set R(a,V) is the set of integral points b in the first orthant such that there is a polygonal path γ from a ...

We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. It ...

A solution to the critical section problem, first posed by Dijkstra [1], is a fundamental requirement for concurrent program control. The problem is to ensure that no two processes are in a specified area of their programs (the critical section) at the ...

We show that nonserial dynamic programming is optimal among one class of algorithms for an important class of discrete optimization problems. We consider discrete, multivariate, optimization problems in which the objective function is given as a sum of ...

This paper gives an input independent average linear time algorithm for storage and retrieval on keys. The algorithm makes a random choice of hash function from a suitable class of hash functions. Given any sequence of inputs the expected time (...

We discuss the problem of hashing in a full or nearly full table using open addressing. A scheme for reordering the table as new elements are added is presented. Under the assumption of having a reasonable hash function sequence, it is shown that even ...

The classical pumping lemma [BP&S] and Ogden's lemma [Og] are among the most powerful tools we possess for proving that languages are not context-free. Hence one goal of recent research has been to obtain analogous theorems for subclasses of the context-...

Suppose you are approached by a computer designer who wants to select a machine architecture and instruction set that is desirable from a compiler writers standpoint. What would you recommend, and why?

We give a limited answer to the above question. We ...

An open question is the computational complexity of recognizing when two graphs are isomorphic. In an attempt to answer this question we shall analyze the relative computational complexity of generalizations and restrictions of the graph isomorphism ...

The method of showing a problem NP-complete by polynomial reduction is one of the most elegant and productive in our theory ([ 1 ], [ 3 ]). It is a means of providing compelling evidence that a problem in NP is not in P. In this paper we will ...

An algebra A is finitely presented if there is a finite set G of generator symbols, a finite set O of operator symbols, and a finite set Γ of defining relations xΞy where x and y are well-formed terms over G and O, such that A is isomorphic to the free ...

Nondeterminism is one of the most elusive concepts in computing.

In this paper we direct our efforts towards viewing nondeterminism as an additional resource at the disposal of time or space bounded Turing machine computations and study the classes of ...

An open question of [LLS] is whether polynomial time many-one reducibility ≤_m^P and polynomial time Turing reducibility ≤_T^P differ on NP. An affirmative answer to this question would yield P @@@@ NP as a corollary, but it is possible that P @@@@ NP even ...

We study complexity problems associated with generation and manipulation of integers. We show that many such questions may be formulated as problems about random access machines (RAMs), and recent results about RAMs with special instructions sets can be ...

Previous results in the literature which describe separation theorems for time bounded complexity classes serve also to separate classes defined by tape bounded auxiliary pushdown automata. Results described here refine these basic relationships between ...

For fixed k ≥ 2 we tighten the time hierarchy for k-tape Turing machines. Also for fixed k ≥ 2 we exhibit infinite hierarchies of languages recognizable by k-tape machines with increasing amount of time on the same amount of space.

In this paper we study diagonal processes over time-bounded computations of one-tape Turing machines by diagonalizing only over those machines for which there exist formal proofs that they operate in the given time bound. This replaces the traditional “...

Much of the research on semantic theories has concentrated on qualitative properties such as definability (of such programming concepts as recursive procedures), equivalence (of different language constructs), and verifiability (of the correctness, or ...

Just as the Church-Turing thesis has simplified proofs of computability [8], efficient simulations of one computer model by another have simplified proofs of complexity upper bounds. A good example of this is Fischer, Meyer, and Rosenberg's real-time ...

Denoting a version of Hoare's system for proving partial correctness of recursive programs by H, we present an extension D which may be thought of as H υ {@@@@,@@@@,@@@@,@@@@} υ H^-1, including the rules of H, four special purpose rules and inverse rules ...

Dynamic logic is a generalization of first order logic in which quantifiers of the form “for all χ...” are replaced by phrases of the form “after executing program α...”. This logic subsumes most existing first-order logics of programs that manipulate ...

A new logic for reasoning about programs is proposed here, and its metamathematics is investigated. No new primitive notions are needed for the logic beyond those used in elementary programming and mathematics, yet the combination of these notions is ...

We introduce a fundamental propositional logical system for describing correctness, termination and equivalence of programs. We define a formal syntax and semantics for the propositional modal logic of programs and give several consequences of the ...

Recent work on computation of functions defined by sets of recursive equations by Cadiou [Ca72], Vuillemin [Vu74] and Downey and Sethi [DS76] depends on semantic interpretations of such equations. A purely syntactic, combinatory approach yields similar ...