article
article
article
article
This paper reports of part of a contunuing investigation of parallel computation, in particular, efforts toward understanding the nature of different types of parallel control. The first section defines an asynchornous system to be a simple type of state machine. This was arrived at in an attempt to generalize from the types of control in parallel program schemata and networks of asynchronous modules...
article
This paper is concerned with the problem of detecting when two asynchronous control systems are equivalent. The systems investigated in the paper are first represented by means of a formal model called an asynchronous control structure (ACS). This model specifies the constraints imposed on the generation of control signals by a system by means of a simple graphical model called a marked graph. Behavioral...
article
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,...
article
This paper examines the problem of finding a single universal test set that will test any of a variety of different implementations of a given switching function. It is shown that, for and/or networks, universal test sets may be found which detect not only all single faults but all multiple faults as well. The minimality and size of these sets are examined and their derivation for incomplete and multiple-output...
article
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...
article
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...
article
In this paper we provide a formulation of the synchronized execution of a system of tasks using generalized P and V operations. We explore the properties of such processes and present as a main result a decision procedure for settling the consistency question.
article
Our principle technical results are the development of a family of first order logics (called FILs), the translation of classes of program schemes into these logics and the development of routine decision procedures for these representations. We feel the results are interesting because the class of schemes include a previously studied important class (Paterson's monadic non-intersecting loops class),...
article
It is shown that a strong relationship exists between sets of graphs defined by graph (walking) automata with markers available and sets defined by graph grammars. Polynomial recognition algorithms are presented for certain classes of sets and it is argued that the existence of polynomial algorithms for other classes is doubtful. Other properties of the classes of sets defined by graph automata and...
article
article
A set of tasks {T1, T2, ..., Tr] are to be scheduled on a two-processor computing system. The execution time of each of the tasks is given. Moreover, a partial ordering ≪ over the set of tasks is specified. If Ti ≪ Tj, it is required that the execution of Tj will not begin until the completion of the execution of Ti. Let ω denote the total elapsed time for the execution of all the tasks in the set...
article
Fault detecting test sets to detect multiple stuck-at-faults in certain networks realizing Reed-Muller canonic expressions are given. It is shown that to detect t faults, t ≥ 1, in a network realizing an arbitrary n-variable logic function only 4 + Σ i=1 [log22t] (in) tests need be applied ([x] is the integer part of x) and that these tests are independent of the function being realized. Techniques...
article
It is shown that the problem of evaluating an Nth degree polynomial is reducible to the problem of dividing the polynomial. A method for dividing an Nth degree polynomial by an N/2 degree polynomial in O(N log 2N) steps is given. Using this it is shown that the evaluation of an Nth degree polynomial at N points can be done in O(N log 3N). The related problem of computing of computing the resides of...
article
article
article
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.
article
We consider several important problems for which no polynomially time bounded algorithm is known. These problems are shown to be related in that a polynomial algorithm for one implies a polynomial algorithm for the others.
