Petri nets and their languages are a useful model of systems exhibiting concurrent behavior. The sequential language associated with a given Petri net S consists of all possible firing sequences of S, where each element of a firing sequence is a single transition. The concurrent language associated with S consists of all possible concurrent firing sequences of S, where each element of a concurrent firing sequence is a set of transitions. The sequential language and the concurrent language associated with S are denoted by (L)(S) and (/spl pi/)(S), respectively. In this paper, we consider an important special ease of Petri nets, called labeled marked graphs. The main result derived in this paper states that if /spl Gammasub 1/ and /spl Gammasub 2/ are two structurally deterministic labeled marked graphs, then (L)(/spl Gammasub 1/)=L(/spl Gammasub 2/)/spl rlhar2spl pi/(/spl Gammasub 1/)=/spl pi/(/spl Gammasub 2/).>

The authors propose a general synthesis method for efficiently implementing any family of Boolean functions over a set of variables, as a self-timed logic module. Interval temporal logic is used to express the constraints that are formulated for the self-timed logic module. A method is provided for proving the correct behavior of the designed circuit, by showing that it obeys all the functional constraints. The resulting circuit is compared with alternative proposed self-timed methodologies. This approach is shown to require less gates than other methods. The proposed method is appropriate for automatic synthesis of self-timed systems. A formal proof of correctness is provided.>

A self-timed finite state machine (FSM) is described. It is based on a formally proven, efficient implementation of self-timed combinational logic and a self-timed master-slave register. Temporal behavioral constraints are formalized, and the system is shown to abide by them. The synthesis method is algorithmic and serves as an automatic compiler of self-timed FSMs. The specification of the FSM is given by a state table, similar to that of synchronous machines. The circuit operates according to a sequence of events that replaces the role of the central clock in the synchronous FSM. The inputs and outputs of the circuit are double-rail (or ternary) and the circuit produces a completion signal. The method is compared with other approaches.>

In this paper we formalize a ternary model which is being used to study the behavior of binary sequential gate networks. We first describe a binary model which is capable of a detailed description of network behavior, but involves a number of steps that grows exponentially in the number of gates. The complexity of the ternary model is linear in the number of gates;however, only partial information is obtained in generaL A mathematical theory is developed making precise these two models and the comparison between them. A number of examples illustrate these results. This work generalizes previously reported research.

In this correspondence the advantages of exhaustive testing of combinational networks are investigated. The method consists of applying all possible input combinations and checking only some attributes of the output vector. It is shown that by abandoning the requirement of minimal testing time (practically insignificant for medium sized networks) a substantial reduction of testing data to be stored is obtained, and the generation process is simplified. It is shown that

This paper is an interesting probabilistic study of the decomposability of sequential machines. State-splitting is not admitted, however. In view of the well known relationship between decompositions (of the state behavior) of sequential machines and partitions having the substitution property (SP partitions [1]), the author's interest turns to SP partitions.

This note discusses multivalued cellular cascades, i.e., one-dimensional arrays of multivalued two-input, one-output combinational cells. It is shown that a large class of multivalued combinational switching functions can be realized by such a cascade.

Abstract—Autonomous sequential networks are represented by transformation graphs, i.e., finite directed graphs, each vertex of which has outdegree one. A network that can be realized by a set of simpler, parallel networks corresponds to a transformation graph representable as a Cartesian product of simpler graphs. An algorithm for obtaining the various decompositions of a given transformation graph into irreducible factors is presented. The particular decomposition into a minimum number of factors is directly reached by the method. Decompositions into a greater number of factors are also obtained so that a balance may be struck between number and complexity of factors.

This paper discusses ternary cellular cascades, i.e., one-dimensional arrays of ternary two-input one-output cells. It is shown that every ternary combinational switching function can be realized by such a cascade.

Incompletely specified (Mealy type) sequential machines and their generalizations to infinite machines are discussed. Convenient algebraic techniques for the study of such machines are introduced. These techniques are based on binary relations and on an extension of the usual concept of homomorphism to multivalued mappings. The first part of the paper gives a short, unified introduction to the algebraic theory of partial automata. The second part unifies and extends the algebraic approach to generalized cascade decompositions which combine conventional decomposition techniques with state-splitting procedures. The relationship between such generalized decompositions and state reductions of automata is investigated.

A two-rail cascade is a one-dimensional binary logic cellular array wherein each noninitial cell has two inputs from the preceding cell and one external input. The initial cell has three external inputs, and the last cell one or two external outputs. The interest in two-rail cascades is due to the fact that one-output two-rail cascades are known to be functionally complete. This paper is concerned with two-output two-rail cascades and derives new synthesis procedures for four and five input variables. These procedures utilize certain properties of the symmetric group of degree 4, as well as known functional decomposition techniques.

A logical design theory for ternary voltage switching circuits is developed. The theory is based on familiar binary switching circuit elements and simplification methods. The theory thus leads to simple electronic realization. The basic system of ternary switching elements consists of function realizable by means of either diode gates or a single triode (transistor).

A logical design theory for ternary voltage switching circuits is developed. The theory is based on familiar binary switching circuit elements and simplification methods. The theory thus leads to simple electronic realization. The basic system of ternary switching elements consists of function realizable by means of either diode gates or a single triode (transistor). Various simplification methods for combinational circuits are described, namely a map method and two algebraic methods. The first algebraic method is an adaptation of the Quine method for determining the prime implicants of a given binary function, and the second is a modification of the Scheinman binary method.

This paper is concerned with the study of static hazards in combinational switching circuits by means of a suitable ternary switching algebra. Techniques for hazard detection and elimination are developed which are analogous to the Huffman-McCluskey procedures. However, gate and series-parallel contact networks are treated by algebraic methods exclusively, whereas a topological approach is applied to non-series-parallel contact networks only. Moreover, the paper derives necessary and sufficient conditions for a ternary function to adequately describe the steady-state and static hazard behavior of a combinational network. The sufficiency of these conditions is proved constructively leading to a method for the synthesis of combinational networks containing static hazards as specified. The section on non-series-parallel contact networks also includes a brief discussion of the applicability of lattice matrix theory to hazard detection. Finally, hazard prevention in contact networks by suitable contact sequencing techniques is discussed and a ternary map method for the synthesis of such networks is explained.

This paper discusses methods of designing binary nonlinear feedback shift registers with cycles of specified length. First, the cycle structures of the simplest feedback functions, e.g., the circulating shift function, are considered. It is then shown how such structures may be modified, either by joining two suitable cycles into one or by the reverse process of splitting a cycle into two. By properly applying these two methods, namely cycle joining and cycle splitting, a wide range of binary shift registers having relatively simple feedback logic is easily designed.

This paper studies composite sequential machines obtained from smaller component machines by their connection in cascade, that is, the outputs from one component are the inputs to the next. Given the specification of a deterministic, completely specified, synchronous, sequential machine (Mealy model), a criterion is derived for such a specification to be decomposable into specifications of smaller machines, the cascading of which will lead to a realization of the original machine required. A simple technique, based on homomorphisms between directed graphs, is arrived at for the actual breaking up of a decomposable specification. A number of additional problems related to sequential machine decompositions are pointed out as concluding remarks.

The paper develops a strictly mathematical, unified theory of combinational switching networks, with the aid of linear graph theory and lattice algebra. The theory is based on the concept of a lattice-weighted, directed linear graph, termed switching net. The advantages of using lattice algebra, rather than Boolean algebra are emphasized. A calculus of lattice matrices is outlined in Section II, and then applied to the study of switching nets (Section III). A suitable formulation of Ashenhurst's uniqueness theorem, and a modified version of its proof are given in Section IV. In Section V switching net theory is extended to multi-terminal and reiterative nets, generalizing results due to M.L. Tsetlin and A.Sh. Blokh.