Search

The principal result described in this paper is the equivalence of the following statements: (1) Every set accepted by a nondeterministic one-way two-head finite automaton can be accepted by a deterministic two-way k-head finite automaton, for some k. (2) The context-free language LPΣ (described in the paper) is recognized by a (log n)-tape bounded deterministic Turing machine. (3) Every set accepted by a L(n)-tape bounded nondeterministic Turing machine is recognized by a L(n)-tape bounded deterministic Turing machine, provided L(n) ≥ log n. This work extends results reported earlier by Hartmanis [2], Savitch [9,10], and Lewis, Stearns, and Hartmanis [6].

Suppose we are given a polynomial P(x"1,...,x"r) in r>=1 variables, let m bound the degree of P in all variables x"i, [email protected][email protected]?r, and we wish to raise P to the nth power, n>1. In a recent paper which compared the iterative versus the binary method it was shown that their respective computing times were O(m^2^rn^r^+^1) versus O(mn)^2^r) when using single precision arithmetic. In this paper a new algorithm is given whose computing time is shown to be O((mn)^r^+^1). Also if we allow for polynomials with multiprecision integer coefficients, the new algorithm presented here will be faster by a factor of m^r^-^1n^r over the binary method and faster by a factor of m^r^-^1 over the iterative method. Extensive empirical studies of all three methods show that this new algorithm will be superior for polynomials of even relatively small degree, thus guaranteeing a practical as well as a useful result.

We pursue in this paper some of the ideas discussed a year ago at the First Annual Symposium on Switching Theory and Logical Design. For a general discussion of threshold logic, and for definitions and motivations of the terms used below, the reader is referred to "Single Stage Threshold Logic" also published in this volume [13]. Also, a general survey of recent papers in the subject has been published elsewhere [14]. The main subject treated below is compound synthesis. The importance of such a study was shown last year: The family of functions of n arguments realizable in a single stage becomes a vanishing fraction of all switching functions of n arguments as n grows (for n = 7 the ratio is about 1028 1/2). We provide an algorithm for determining "2-realizability" -- reallzability with two threshold elements. The general approach produces a good solution in any case, but one guaranteed optimal only for 2-realizable functions. We use here a geometric terminology; this new language is also used in the second section, where "higher" necessary conditions for realizability are discussed. A conjecture that certain of these conditions might be sufficient is disproved; three related conditions are treated in a common language. The final section considers optimal integral single-stage realizations, and disproves a conjecture made last year: That such a realization gives equal arguments equal weights.

This paper presents systematic synthesis procedures for Lupanov decoding networks. Decoding networks find applications in computer memories for the selection of a particular item of data addressed by a binary code, in counter circuits, in character-by-character code conversion circuits, in the synthesis of switching functions and also in the theoretical derivations of complexity bounds for arbitrary switching networks. In particular, a complete decoding network of n input variables provides a distinct output for each of the 2n possible combinations of the variables. These networks have been studied extensively, both in terms of relay contact realizations1,2 and in terms of gate-type element realizations3. Moore4 has shown that for disjunctive contact networks, hence for networks of branch-type elements, the familiar transfer trees using CM = 2(2n-1) contacts are the only possible minimal n variable decoding networks. In applications where disjunctivity of the outputs is not required, Lupanov5 has shown that the required number of contacts can be reduced considerably (by a factor of 2 as n grows arbitrarily large). Short6 has examined specific design procedures using Lupanov's approach. The main idea is based on the design of a r-variable partial decoder, where r = 2k, k = 2,3,... whose 2r/r outputs consist of mutually disjoint groups of r vertices, collectively exhausting all the vertices of the r-cube such that any vertex is ? distinguished from the rest of the vertices in the group by the value of a single variable. The problem that has been posed7 and solved in this paper is the following: can we take r ≠ 2k for the partial decoder and find Lupanov trees whose costs are smaller than those obtained using r = 2k? We shall prove that this is possible and present systematic procedures for the design of Lupanov trees. The Lupanov trees obtained by our method have the best minimal costs known so far for all values of n. As an example, we have designed a 5-variable decoder which uses only 58 contacts compared to 60 contacts used by Lupanov.

This paper continues investigations pertaining to recursive bounds on computing resources (such as time or memory) and the amount by which these bounds must be increased if new computations are to occur within the new bound. The paper proves that no recursive operator can increase every recursive bound enough to reach new computations. In other words, given any general recursive operator F[ ], there is an arbitarily large recursive t( ) such that between bound t( ) and bound F[t( )]( ) there is a gap in which no new computation runs. This demonstrates that the gap phenomenon first discovered by Borodin for composition is a deeply intrinsic property of computational complexity measures. Moreover, the Operator Gap Theorem proved here is shown to be the strongest possible gap theorem for general recursive operators. The proof involves a priority argument but is sufficiently self-contained that it can easily be read by a wide audience. The paper also discusses interesting connections between the Operator Gap Theorem and McCreight & Meyer's important result that every complexity class can be named by a function from a measured set.

This paper describes an eigenvector decomposition of an m × n rectangular matrix, P0. Matrix P0 is approximated as a series of matrices each one of which can be expressed as the outer product of two vectors. These vectors are of dimensions m × 1 and n × 1; thus, each term in the approximation to P0 requires m + n storage locations. If P0 is approximated by a series of l matrices, then l(m + n) storage locations are required to store the approximation. Data compression will be achieved by this approximation for those values of l for which l(m + n) < mn.

An important open question in the field of computational complexity in the development of nontrivial lower bounds on the number of logical operations required to compute switching functions. Although counting arguments can be used to show that most Boolean functions of n inputs and 0(n) or fewer outputs have complexity growing exponentially in n, no one has yet exhibited a particular such function whose unlimited fan-out combinational complexity is known to grow faster than linearly in n when a functionally complete set of primitive operations is allowed. In this paper, we consider the class of monotone increasing Boolean functions. These correspond to the functions which can be computed using only two-input OR and AND operations, an incomplete set of primitives. We develop techniques for proving functions of n inputs and 0(n) outputs have nonlinear combinational complexity if only OR and AND operations are allowed. We do this by demonstrating that binary sorting requires 0(n log n) operations, and by exhibiting a set of n Boolean sums over n variables which requires 0(n3/2) operations.

Let U1,U2,...,Udbe totally ordered sets and let V be a set of n d-dimensional vectors in U1× U2× ... × Ud. A partial ordering is defined on V in a natural way. We consider the problem of finding all maximal elements of V with respect to the partial ordering. The computational complexity of the problem is defined to be the maximum number of required comparisons of two components and is denoted by Cd(n). It is trivial that C1(n) = n-1 and Cd(n) ≤ 0 (n2) for d ≥ 2. previous results are Cd(n) ≤ 0 (n log2n) for d = 2,3. in this paper, we show 1. Cd(n) ≤ 0 (n(log2n)d-2) for d ≥ 4. 2. Cd(n) ≥ ⌈log2n! ⌉ for d ≥ 2.

The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to (m+n) n.

We informally define a modular (cellular, iterative) computer to be a device consisting of a large (or, in theory, infinite) number of identical circuit modules connected together in some uniform manner, that is, in such a fashion that every module is connected into the device in the same manner as every other. In this paper we propose a mathematically precise definition of, "connected together in a uniform manner". In brief, we show that the underlying linear graph whose vertices correspond to the modules and whose edges correspond to the cables connecting the modules, is a group-graphs that is, the vertices correspond to the elements of a group G and there is given a finite subset G0 of G such that {g, g1} is an edge of the graph If, and only if, there exists g0 e G0 such that g1 = gg0. We further investigate the effects of restricting G to be an Abelian group and indicate why we feel such a restriction is unwarranted at least in developing the theory of modular computers.

Solving prime implicant tables is greatly facilitated by reduction techniques such as row dominance, column dominance, and essential row selection. This paper presents a new reduction technique which is operable on any otherwise irreducible table having a column covered by exactly two rows.

There is a class of flow charts called "reducible" for which many global code optimization algorithms have been recently written. As a practical matter, one may expect the flow chart of a program appearing "in nature" to be reducible with a probability over 90% [3], and those that are not can be made reducible by "node splitting" [10]. Unfortunately, the algorithms written for reducible graphs do not really take advantage of reducibility, since they require O(n2) bit vecter steps in worst case, the same as for the obvious general algorithms of these types. In this paper we give an O(n log n) bit vecter step algorithm to determine "available expressions," [7]. This information is essential for global elimination of common subexpressions. However, the ideas discussed here carry over to other global code optimization problems such as "reaching definitions" [1], "live variables" [9] and "very busy variables" [6].

Several algorithms are presented, more or less directly related to the "minimization" theory of Boolean formulas. They give solutions to the following specific problems: computation of the sum of all the "prime implicants", starting with any "normal" formula; verification of the equivalence F a/ for "normal" formulas F; determination of some or all of the minimal F-including sets. The last problem is a two-fold generalization of the determination of the "irredundant normal formulas". More precisely if F, F1, F2,..., Fn are Boolean formulas such that F is included in ("implies") SigmaFi, a minimal F-including set is a collection of Fi such that their sum includes F, but no subcollection has the same property. Although these algorithms are of obvious practical importance, they are viewed here more as a theoretical contribution. Examples are included; the theory of Boolean formulas on which this paper is based is presented elsewhere.

In the above paper [1], Varshamov considers discrete channels with q inputs and q outputs, q being an arbitrary integer.

It is the object of this paper to study the topological properties of finite graphs that can be imbedded in the n-dimensional integral lattice (denoted Nn). The basic notion of deletability of a node is first introduced. A node is deletable with respect to a graph if certain computable conditions are satisfied on its neighborhood. An equivalence relation on graphs called reducibility and denoted by "∼" is then defined in terms of deletability and it is shown that (a) most important topological properties of the graph (homotopy, homology and cohomology groups) are ∼-invariants, (b) for graphs imbedded in N3 different knot types belong to different ∼-equivalence classes, (c) it is decidable whether two graphs are reducible to each other in N2 but this problem is undecidable in Nn for n ≥ 4. Finally, it is shown that two different methods of approximating an n-dimensional closed manifold with boundary by a graph of the type studied here lead to graphs whose corresponding homology groups are isomorphic.

The functions considered are p-valued functions of n p-valued arguments; they may conveniently be represented by functions over the field Jp of integers modulo some prime p. It is noted that if every function can be uniquely written as a mod-p linear combination f = Sigmai=lpn fibi, fi in Jp, (1) then (1) may be thought of equivalently as a canonical form or as a vector-space representation, with the bi forming a basis. This latter interpretation suggests the use of matrix multiplication to transform functions from one canonical form to another. The present paper is devoted to two main topics: 1. A consideration of various canonical forms and their analogies to the Taylor and Maclaurin expansions and the Lagrange interpolation formula of real-variable function theory. 2. A derivation of the matrices relating these forms and of expedient matrix-inversion techniques. The inversion of a pn times pn matrix is reduced, in general, to the inversion of n p times p matrices and in some cases simply to transposition or rotation of the matrix. These simplifications greatly facilitate the evaluation of 'power' series expansions for all inputs and the generation of power series from function tables.

This paper presents several representations of the recursively enumerable (r.e.) sets. The first states that every r.e. set is the homomorphic image of the intersection of two linear context-free languages. Another states that every r.e. set is accepted by an on-line Turing acceptor with two pushdown stores such that in every computation, each pushdown store can make at most one reversal (that is, one change from "pushing" to "popping"). It is shown that this automatatheoretic representation cannot be strengthened by restricting the acceptors to be either deterministic multitape, nondeterministic one-tape, or nondeterministic multicounter acceptors. An investigation of the properties of reversal-bounded computations suggests that reversal bounds are not a "natural" measure of computational complexity for multitape Turing acceptors. The above results are used to obtain an independence theorem for full semi-AFLs and an undecidability result for effective families of languages.

Left corner parsing refers to a class of parsing procedures in which the productions are recognized in a particular order which is different than both bottom up and top down. Each production is recognized after its left descendant but before its other descendants. Procedures in this class have occurred frequently in the compiler literature. In this paper a class of grammars, called LC (k) grammars, is defined and shown to be exactly those grammars for which a certain canonical pushdown machine that does left corner parsing is deterministic. A subset of LC(k) grammars, called strong LC(k) grammars, is defined and shown to be those grammars that can be deterministically left corner parsed by a simplified canonical machine. It is shown that when a particular grammatical rewriting procedure is applied to a grammar, the resulting grammar is (strong) LL(k) if and only if the original grammar is (strong) LC(k). This implies that the class of LC(k) languages is identical to the class of LL(k) languages. The syntax directed translations on LC(k) grammars that can be performed by the canonical pushdown machine are also discussed.

This paper presents some results concerning the star height of regular events. First we consider the behavior of star height under various operations on regular events and it is proved that star height is preserved under the derivative operation. The relation of star height of a regular event to the cycle rank of the reduced state graph of the corresponding finite automaton is studied. This investigation leads to sufficient conditions for the star height to be equal to the rank of the state graph. For example, this is true for events defined by permutation automata with a single output state. Families of regular events of arbitrary star height are exhibited. Finally, some open questions posed by Eggan regarding star height and rank are answered.

This paper derives a set of parameters which characterize functions realizable with single threshold devices. A Boolean function of n variables is a function on the vertices of an n-dimensional cube to 0 and 1. Considering the vertices as n-dimensional vectors, the ordinary vector sum (or the center of gravity) of the true vertices and the number of true vertices determine the realizability. It is proven that, if the characterizing vectors and the numbers of the true vertices of two functions are respectively equal, then either both functions are realizable or both are not realizable and, if one of the functions is realizable, then both functions are identical. Because of the uniqueness, these characterizing parameters can be used to label known threshold functions. The use of this label in conjunction with a procedure of reducing functions to a standard form provides a convenient means of ascertaining whether an arbitrary function is one of the known threshold functions. Some simple properties of the characterizing parameters are described: the characterizing parameters give directly the algebraic signs of, and the ordinal relations among, the weights to realize a threshold function; the characterizing vector is minimal with respect to a partial ordering. Results on a class of threshold functions are given.

A model of an automaton, called a balloon automaton is proposed, It consists of a finite control, which may be deterministic or nondeterministic, an input tape which may be one way or two way, and an abstract, infinite memory, called the balloon, which can enter any of a countable number of states. There is assumed to be a recursive function which manipulates the state of the balloon, and another which passes a finite amount of information from the balloon to the finite control. A subset of the balloon automata is considered a closed class if it obeys two very simple closure properties. Certain closed classes recognize exactly the languages recognized by such familiar automata as the pushdown automaton or stack automaton. Unfortunately, no closed class recognizes the sets accepted by linear bounded automata or the time and tape complexity classes of Turing machines. It is shown that many of the usual closure properties of languages accepted by the pushdown automaton, stack automaton, etc., hold for an arbitrary closed class of balloon automata. For example, the languages accepted by a closed class of one-way, nondeterministic balloon automata are closed under concatenation. Of special interest is the fact that a closed class of two-way deterministic balloon automata is closed under inverse g.s.m. mappings. This fact is not obvious, and was not known for all of the types of automata which form closed classes of balloon automata. It should be emphasized that the purpose of this paper is not to propose another “model of a computer.” Rather, we are proposing a method of proving the standard theorems about existing and future models. Hopefully, when a model is proposed in the future, one will simply show it equivalent to a closed class of balloon automata, and have many of the closure properties automatically proven.

This paper is concerned with the effects of randomization on finite memory decision rules [1]. It is shown that for any twohypothesis testing problem, there exists a b < ?, such that for all B, the optimal randomized rule using a memory with B bits has a probability of error no smaller than that of the optimal deterministic rule using B+b bits. Thus as B?? the fraction of bits lost by using deterministic rules tends to zero, and in this sense deterministic rules are asymptotically optimal.

The purpose of this paper is to give an alternative proof to the decidability of the emptiness problem for tree automata, as shown in Rabin4. The proof reduces the emptiness problem for automata on infinite trees to that for automata on finite trees, by showing that any automata definable set of infinite trees must contain a finitely-generable tree.

Rabin has investigated the difficulty of proving that a set of linear forms is simultaneously positive by the evaluation of analytic functions. In this paper we study this same question under the restriction that each analytic function itself be linear. A complete result is given in the case that the original set of linear forms are simultaneously positive on a subspace having at least one extreme point. Applications are then given. In particular, it is shown that the proof that a real number x"1 is maximal out on the set {x"1,...,x"m} requires evaluation of m-1 linear forms even if x"1 is known in advance to be exceeded by at most one x"i for 2@?i@?m.

This paper develops techniques for establishing a lower bound on the number of arithmetic operations necessary for sets of simple expressions. The techniques are applied to matrix multiplication. A modification of Strassen's algorithm is developed for multiplying n × p matrices by p × q matrices. The techniques are used to prove that this algorithm minimizes the number of multiplications for a few special cases. In so doing we establish that matrix multiplication with elements from a commutative ring requires fewer multiplications than with elements from a non-commutative ring.

This paper deals with cycle rank of finite transition graphs and its relation to the (restricted) star height of regular events. Rank-non-increasing transformations on transition graphs are studied. It is proved that for every transition graph G there exists an equivalent reduced non-deterministic state graph G', having no more nodes than G and no higher rank. This result yields a stronger version of Eggan's theorem on star height. Some new notions concerning non-deterministic state graphs are then introduced and utilized for developing a proof technique for establishing the star height of regular events. Results on the star height of events recognized by reset-free state graphs are also obtained.

Let F be any effective mapping from total functions on the integers to total functions. Composition and iterated composition are examples of such mappings. The "operator speed-up" theorem in this paper establishes the existence of a computable function f such that for any program computing f(x) in p1(x) steps for all x, there is another program computing f(x) in p2(x) steps and F(p2) ≪ P1 almost everywhere. Thus, there is no best program for f. The notions of "program" and "number of steps" are treated axiomatically, so that the theorem is independent of any particular model of a computing machine. An example of speed-up for Turing machines is considered.

Several algorithms are presented, more or less directly related to the "minimization" theory of Boolean formulas. They give solutions to the following specific problems: computation of the sum of all the "prime implicants", starting with any "normal" formula; verification of the equivalence F a/ for "normal" formulas F; determination of some or all of the minimal F-including sets. The last problem is a two-fold generalization of the determination of the "irredundant normal formulas". More precisely if F, F1, F2,..., Fn are Boolean formulas such that F is included in ("implies") SigmaFi, a minimal F-including set is a collection of Fi such that their sum includes F, but no subcollection has the same property. Although these algorithms are of obvious practical importance, they are viewed here more as a theoretical contribution. Examples are included; the theory of Boolean formulas on which this paper is based is presented elsewhere.

In this paper we study some classes of irregular languages which can be denoted by regularlike expressions. It is shown that a set of regular expressions can be used to characterize every language which is generated by a non-expansive context-free grammar, i.e. which is a standard matching-choice set as defined by Yntema. Characterizations are given for the linear, metalinear and ultralinear languages. Some known results are presented in a simpler and more intuitive fashion by using the notion of a finite automaton with a folded tape. It is next shown that the model used can be naturally extended to a subfamily of contextsensitive languages.

In this paper we shall investigate the automorphism group G(A/H) of the reduced automaton A/H where A = (S, I, M) is a finite strongly connected automaton and H is a subgroup of the automorphism group G(A) of the automaton A. This problem and other related topics have been dealt with recently by G. P. Weeg, A. C. Fleck, and B. Barnes.1,2,3,4,5 However, the particular problem to give an isomorphic representation of G(A/H) for arbitrary A and H still remained open. Our present purpose is to fill this gap.