article
article
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...
article
article
We consider some of the important unsolved problems in the theory of computation concerning the relationship between deterministic and nondeterministic computations, and between tape and time bounded computations. For each such problem we find an equivalent problem concerning two way deterministic pushdown automaton languages. This is the first time many of the open problems have been reduced to questions...
article
Two characterization theorems for the class of context-free grammatical families are given. The characterizations are expressed in terms of the family of regular sets, the family of linear sets, and the following language-family operators: union, concatenation, the full semi-AFL operator, the full AFL operator, and a new ternary substitution operator.
article
The problem of finding the minimum amount of fanout needed to realize a switching function f is investigated. Fanout-free functions are defined, and necessary and sufficient conditions for a function to be fanout-free are derived. A measure τ(f) called the input fanout index, is introduced which represents the minimum number of input variables that fan out in any realization off. It is shown that...
article
article
Many apparently divergent approaches to specifying formal semantics for programming languages are applications of initial algebra semantics. Here we provide an overview of the concept of initial algebra semantics.
article
A program schema which models straight line code admitting structured variables such as arrays, lists, queues etc. is considered. A set of expressions is associated with a program reflecting the inputoutput transformations. Given a set of basic axioms defining expression equivalence the class of programs with equivalent expression sets is characterized by a minimal complete set of equivalence preserving...
article
We study the class of P-Complete problems and show the following: i) for any constant ε ≫0 there is a P-complete problem for which an ε-approximate solution can be found in linear time ii) there exist P-Complete problems for which linear time approximate solutions that get closer and closer to the optimal (with increasing problem size) can be found iii) there exist P-Complete problems for which the...
article
The equivalence problems for uninterpreted recursive program schemes and deterministic pushdown automata are reducible to each other. The equivalence class of a scheme is characterized by an infinite tree which is generated by the scheme as a language by a context-free grammar and which satisfies the equations of the system. Such trees are called algebraic. Roughly speaking, a tree is algebraic iff...
article
An IP-schema (Ianov schema with pushdown memory) has one register just as for Ianov schemas, but the finite-state control is augmented by a pushdown memory that can only be used for storing the contents of the register or fetching the contents of the top to the register. An IP(k)-schema is an IP-schema which uses only the first k memory locations of the pushdown memory. Let CIP(k)(or CIP) be the class...
article
We consider random access machines with a multiplication operation, having the added capability of computing logical operations on register are considered both as an integer and as a vector of bits and both arithmetic and boolean operations may be used on the same register. We prove that, counting one operation as a unit of time and considering the machines as acceptors, deterministic and nondeterministic...
article
Recent work [AJU, E1, E2] has shown that substantial improvements in both the size and the running time of a bottom-up parser often can be realized by constructing the parser using an ambiquous underlying grammar. Various heuristic techniques are used to resolve action conflicts in the parser which result from the ambiquity of the grammar. In this paper we present a method for construction of such...
article
Advances in LSI technology have led to problems concerning the selection of output functions for optimum complex logic modules. A natural criterion for the evaluation of possible designs is the structure of the set of all subfunctions of the function realized by a module. Thus studying properties of the sub-function sets of Boolean functions is an approach to solving the above problems. In the paper...
article
article
We examine a class of heuristics for maintaining a sequential list in approximately optimal order with respect to the average time required to search for a specified element, assuming that we search for each element with a fixed probability independent of previous searches performed. The "move to front" and "transposition" heuristics are shown to be optimal to within a constant...
article
article
various operations on graphs, matrices, or relations can be executed more quickly when the arguments are "sparse" (i.e., if e ≪ ≪ v2where e is the number of edges and v the number of vertices) than when they are "dense" (i.e., e ≈ v2). Fast algorithms are presented for a large class of operations on sparse relations. These algorithms are used to produce the best known methods for...
article
We first introduce informally our grammatical scheme for modeling the generation or growth of data structures which can be viewed as the neighbor relations (topologically invariant) for planar maps, permitting binary division of "countries" or "cells", motivated by biological considerations and by the desire to generate successive patterns in the Lindenmayer fashion (i.e., by simultaneous...
