STOC

We define a measure of the generality of the control structure of a program schema. This imposes a partial ordering on program schemas, and leads to a concept of the “difficulty” of a programming problem. In this sense there exists a “hardest” flowchart ...

In this paper, we provide a simple recursive programming language with a semantics and a formal proof system, along the lines of [5], [17] and [23]. We show that the semantics used is the “best” possible if one admits the validity of Algol's copy rule, ...

A deterministic pushdown automaton (dpda) is described as finite-turn if there is a bound on the number of times the direction of the stack movement can change in the set of all derivations from the starting configuration. The purpose of this paper is ...

A striking example of practical tradeoffs between storage space and execution time is provided by the IBM 1401 Fortran compiler.

On another level, there is an interesting relation between the time and storage required to recognize context free ...

The results of Cook and Karp ([K], [C]) aroused considerable interest for at least two reasons. First, the answer to a long-standing open question which had seemed peculiar to automata theory—whether deterministic and nondeterministic polynomial-time-...

It is widely believed that showing a problem to be NP-complete is tantamount to proving its computational intractability. In this paper we show that a number of NP-complete problems remain NP-complete even when their domains are substantially ...

This paper presents a complexity theory of formal languages. The main technique used is that of embedding “={0,1}*”, “=0*”, and “=φ” into other linguistic predicates. In Section 2, the undecidability of “={0,1}*” for cfl's is exploited to provide ...

Several measures of complexity of a regular expression are defined. (Star height and number of alphabetical symbols are two of them.) Upper and lower estimates for the complexities of expressions for certain standard sets (e.g. the set of all paths on a ...

We are interested in combinational circuits synthesized from and-gates and or-gates. We first show that n³ distinct and-gate inputs are needed to form the product of two Boolean matrices, and hence O(n³) two-input and-gates are needed to compute the ...

An open problem, posed by A. Rosenberg [R], motivates the consideration of representations of graphs and the effect of these representations on the efficiency of algorithms which determine properties of unlabelled graphs. In this paper we investigate ...

Probabilistic Turing machines are Turing machines with the ability to flip coins in order to make random decisions. We allow probabilistic Turing machines small but nonzero error probability in computing number-theoretic functions. An example is given ...

We define polynomial time computable operator. Our definition generalizes Cook's definition to arbitrary function inputs. Polynomial classes are defined in terms of these operators; the properties of these classes are investigated. Honest polynomial ...

Comparison of the polynomial-time-bounded reducibilities introduced by Cook [1] and Karp [4] leads naturally to the definition of several intermediate truth-table reducibilities. We give definitions and comparisons for these reducibilities; we note, in ...

Random access machines (RAMs) are usually defined to have registers that hold integers. While this captures in part the structure of a commercial computer, it overlooks an implementation-dependent feature of most binary oriented machines, namely their ...

One of the most important open questions in the field of computational complexity is the question of whether there is a polynomial time decision procedure for the classical propositional calculus.

The purpose of the present paper is to study a question ...

Let N be the set of nonnegative integers and let <N*,+> be the weak direct product of <N,+> with itself. Mostowski[9] shows that the theory of <N*,+> is decidable, but his decision procedure isn't elementary recursive. We present here a more efficient ...

The complexity of decision procedures for the Weak Monadic Second-Order Theories of the Natural Numbers are considered. If only successor is allowed as a primitive, then every alternation of second-order quantifiers causes an exponential increase in the ...

The isomorphism problem for graphs G₁ and G₂ is to determine if there exists a one-to-one mapping of the vertices of G₁ onto the vertices of G₂ such that two vertices of G₁ are adjacent if and only if their images in G₂ are adjacent. In addition to ...

An algorithm proposed by Dinic for finding maximum flows in networks and by Hopcroft and Karp for finding maximum bipartite matchings is applied to graph connectivity problems. It is shown that the algorithm requires 0(V^1/2E) time to find a maximum set ...

In his chapter on sorting, Knuth [1]@@@@ describes the open problem of stable sorting with no more than 0(log²N) bits of extra space and less than 0(N²) computation time.

In this paper we define the concept of a contiguent and show that a contiguent ...

In this paper, we present an algorithm which computes the optimal pattern for merging n equal size sorted sequences stored on a disk, in time O(log n) and constant space. The best previously known algorithm for solving this problem (Knuth [4], ...

A formal model of the process concept is presented. This model can represent sets of processes that use the synchronization primitive PV or one of the many generalizations of PV. The study of synchronization problems is then reduced to the study of ...

The parallel derivative of a set of strings is introduced. Given a serial, repetition-free parallel program schema, its closure is constructed by taking parallel derivatives of its set of computations. The construction resembles the construction of a ...

The purpose of this paper is to present the basis of an automata-theoretic model which treats the concept of “schedule” for programs which admit a (predefined) degree of parallelism.

After a brief review of notational conventions (Section 2), the class ...

The effect of some restrictions on W-grammars (the formalization of the syntax of ALGOL 68) are explored. Two incomparable families examined at length are W_RB (languages generated by normal regular-based W-grammars) and W_S (languages generated by simple ...

For some time, it has been recognized that left-to-right deterministic top-down parsing has a number of features to recommend it. The logic of such a parser is easily expressed as a one-state pushdown machine, and very flexible translations can readily ...

Let NIA(d) be the family of languages accepted within linear time by nondeterministic d-dimensional iterative arrays. (On-line deterministic multidimensional iterative arrays have been studied by Cole [2].) It has been observed [8] that every language ...

The purpose of this paper is to establish the following result.

Theorem 3.1. Let L be a language. The following are equivalent:

(i) L is accepted by a nondeterministic multipushdown acceptor which operates in such a way that in every accepting ...

Efficient storage utilization by schemes which allocate storage for extendible arrays is studied. A minimax lower bound on efficiency of storage use by such schemes is derived; and a scheme which achieves this bound is exhibited. When arrays are ...

With geometrical techniques we hope to bring new insight into the reachability problem for vector-addition systems, which is pertaining in many areas in computer science theory but unsolved ever since it was proposed by Karp and Miller. We show that the ...