article
The paper presents an algebraic theory of graph-grammars using homomorphisms and pushout-constructions to specify embeddings and direct derivations constructively. We consider the case of arbitrary directed graphs permitting loops and parallel edges. The gluing of two arbitrary labeled graphs (push-out) is defined allowing a strictly symmetric definition of direct derivations and the embedding of...
article
The Investigation of Chow parameters is extended to pseudothreshold functions. Pseudothreshold logic is a generalization of threshold logic. Chow parameters are a set of n + 1 integers derived from a Boolean function of n variables. The main results are: 1. Two different pseudothreshold functions with the same Chow parameters have the same optimum structure. Thus, the optimum structures of pseudothreshold...
article
article
There are several situations that we are trying more or less to model. One arises from the standard IQ test in which a person is given a finite sequence of integers and asked to produce the next integer in the sequence. Another is provided by the following grossly simplified view of one aspect of physics: Consider a physicist who is trying to find a law to explain a growing body of experimental data...
article
article
article
Although the field of "canonical parsing" (i.e. parsing in which we always reduce the leftmost phrase of a sentential form) has been extensively studied, the field of non-canonical parsing has been relatively untouched, In this paper, we first motivate the whole study by presenting a language which is intrinsically non-canonical and then we develop a general model of bottom-up parsing which...
article
Neighborhood search has been used with some success in providing approximate solutions to discrete optimization problems. The technique produces solutions which may be locally but not globally optimal. For a particular class of problems this paper describes a method for analyzing the relative effectiveness associated with different neighborhoods in terms of the probability that a local optimum is...
article
At the heart of a number of arithmetic complexity problems are some basic questions in tensor analysis. Questions regarding the complexity of multiplication operations which are n-linear are most easily studied in a tensor analytic framework. Certain results of tensor analysis are used in this paper to provide insight into the solution of some of these problems. Methods are given to determine a partial...
article
This paper investigates the possibilities of the resolution method of J.A. Robinson [12] as a decision procedure for classes of first-order formulas. It is shown here that resolution, a machine-oriented inference procedure, can be modified to be a method which decides whether certain kinds of quantificational formulas are satisfiable or unsatisfiable. A new complete resolution technique is presented...
article
article
Complexity of sentence recognition is studied for one-way stack languages, indexed languages, and tree transducer languages. The problem is shown to be polynomial-complete in each case. A class of naturallanguage grammars is formalized and the sentence-recognition problem is shown to be polynomial-hard although the languages are context-sensitive. The proofs give new language-theoretic characterizations...
article
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...
article
article
article
A linear recursive program consists of a set of procedures where each procedure can make at most one recursive call. The conventional stack implementation of recursion requires time and space both proportional to n, the depth of recursion. It is shown that in order to implement linear recursion so as to execute in time n one does not need space proportional to n : ne for arbitrarily small e will do...
article
article
Decision procedures for validity in intuitionistic propositional calculus and modal propositional calculus are given which require a running time proportional to a polynomial in the length of the formula on a nondeterministic Turing machine. Using a theorem of Cook's and well-known transformations from intuitionistic to classical and modal to intuitionistic logics, the validity problem for intuitionistic...
article
article
A synthesis method for multiple-input change asynchronous sequential machines is proposed. The method is based on the self-synchronization principle. The internal states are realized with edge-sensitive flip-flops which are triggered selectively. The new concept of selective triggering or controlled excitation results in considerable saving in logic and more flexible design. The state assignment is...
