The state complexity of a regular language is the number of states in a minimal deterministic finite automaton accepting the language. The syntactic complexity of a regular language is the cardinality of its syntactic semigroup. The syntactic complexity of a subclass of regular languages is the worst-case syntactic complexity taken as a function of the state complexity n of languages in that class. We prove that n n−1, n n−1 + n − 1, and n n−2 + (n − 2)2 n−2 + 1 are tight upper bounds on the syntactic complexities of right ideals and prefix-closed languages, left ideals and suffix-closed languages, and two-sided ideals and factor-closed languages, respectively. Moreover, we show that the transition semigroups meeting the upper bounds for all three types of ideals are unique, and the numbers of generators (4, 5, and 6, respectively) cannot be reduced.

Current memory testing methods rely on fault models that are inadequate to accurately represent potential defects that occur in modern, often specialized, memories. To remedy this, the authors present a formal framework for modeling and testing special-purpose memories. Their approach uses three models: the transistor circuit, the event-sequence model, and finite-state machines. The methodology is explained using the example of a content-addressable memory (CAM). The fault model they describe comprises input stuck-at, transistor, and bridging faults. The authors show that functional tests can reliably detect all input stuck-at faults, most transistor faults (including all stuck-open faults), and about 50% of bridging faults. The remaining faults are detectable by parametric tests. A test of length 7n+2l+9 that detects all the reliably testable faults in an n-word by l-bit CAM is presented. A CAM test by Giles & Hunter is evaluated with respect to the input stuck-at faults. It is shown that this test fails to detect certain faults; it can be modified to achieve full coverage at the cost of increased length.

An approach to modeling and testing memories is presented and illustrated using an n-word by l-bit (n/spl times/l) static content-addressable memory (GAM) array for cell input stuck-at faults. An input stuck at fault model for a CAM is defined, and a test of length 7n+2l+5 with 100% fault coverage with respect to this fault model is constructed. This test also detects all the usual cell stuck-at and transition faults. Finally, some design-for-testability (DFT) modifications facilitating a further reduction of this test's length are proposed.

This article introduces a mathematical framework called cluster-cover. We show that this framework captures the combinatorial structure of a class of VLSI design optimization problems, including two-level logic minimization, constrained encoding, multilayer topological planar routing, application timing assignment for delay-fault testing, and minimization of monitoring logic for BIST enchancement. These apparently unrelated problems can all be cast into two metaproblems in our framework: finding a maximum cluster and finding a minimum cover. We describe paradigms for developing algorithms for these problems. First, a simple heuristic called greedy peeling is presented and characterized. We derive sufficient conditions that guarantee optimum solutions by greedy peeling. We generalize the performance analysis of a multilayer topological planar routing heuristic to greedy peeling for the general cluster-cover problems. We propose a performance bound of greedy set covering that can be computed efficiently for a given problem instance; this bound is much tighter than the previously known bounds. Second, prime covering—orignally developed for logic minimization—is generalized to finding exact solutions for cluster-cover problems. Previously, only the connection between logic minimizaton and constrained encoding was known.

No abstract available.

In classical switching theory, asynchronous sequential circuits are operated in the fundamental mode. In this mode, a circuit is started in a stable state, and then the inputs are changed to cause a transition to another stable state. The inputs are not allowed to change again until the entire circuit has stabilized. In contrast to this, delay-insensitive circuits-the correctness of which is insensitive to delays in their components and wires-use the input-output mode. In this case, it is assumed that inputs may change again, in response to an output change, even before the entire circuit has stabilized. It is shown that such commonly used behaviors as those of the set-reset latch and Muller's C-ELEMENT do not have delay-insensitive realizations, if gates are used as the basic components. It is proved that no nontrivial sequential behavior with one binary input possesses a delay-insensitive realization using gates only. The proof makes use of the equivalence between ternary simulation and the general-multiple-winner model of circuit behavior.>

Abstract Manufacturers often use digital waveforms to specify critical device timing. In this paper, we study two problems related to the use of such specifications. First, we are interested in verifying that the timing information is consistent to begin with. Second, given waveform specifications of two devices that are to be linked, we wish to know whether one satisfies the other's timing requirements. We construct a model of the timing information conveyed by the waveform convention and show how both problems can be solved efficiently with optimization techniques. To illustrate our arguments, we compare the write‐cycle timing of a typical CPU with that of a RAM device.

A unified framework is developed for the study of asynchronous circuits of both gate and MOS type. A basic network model consisting of a directed graph and a set of vertex excitation functions is introduced. A race analysis model, using three values (0, 1, and x), is developed for studying state transitions in the network. It is shown that the results obtained using this model are equivalent to those using ternary simulation. It is also proved that the set of state variables can be reduced to a minimum size set of feedback variables, and the analysis still yields both the correct state transitions and output hazard information. Finally, it is shown how the general results above are applicable to both gate and MOS circuits.

Ternary simulation techniques provide efficient methods for the analysis of the behavior of VLSI circuits. However, the results of ternary simulation have not been completely characterized. In this paper we prove a somewhat modified version of the Brzozowski-Yoeli conjecture (stated in 1976) that the results of the ternary simulation of a gate network N correspond to the results of the binary race analysis of Ñ in the ``multiple-winner'' model, where Ñ is the network N in which a delay has been inserted in each wire.

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.

This paper considers translation problems in residue number systems. The conversion from a fixed-base representation to a residue representation can be done using residue adders only; we show that relatively simple combinational logic can be used to replace one level of residue addition. In the reverse translation problem, we examine the conditions under which base extension can be used to compute the fixed-base digits from a residue code number, and we study the efficiency of the algorithm.

Minimum feedback realizations of synchronous sequential machines using set-reset flip-flops are discussed. The known results are pointed out in order to clarify any possible misunderstanding of a statement made in a recent review.

The authors define a general repetitive machine (GRM) as a finite automaton in which the initial state can be reached from every final state. If there exists a tape which takes all final states to the initial state, the automaton is called a repetitive machine (RM). The RM's constitute a proper subclass of the GRM's. The first result is that a GRM is either strongly connected or it has a nonaccepting dead state, and the remaining states form a strongly connected subset.

Decompositions of regular events into star events, i.e. events of the form W = V *, are studied. Mathematically, the structure of a star event is that of a monoid. First it is shown that every regular event contains a finite number of maximal star events, which are shown to be regular and can be effectively computed. Necessary and sufficient conditions for a regular event to be the union of its maximal star events are found. Next, star events are factored out from arbitrary events, yielding the form W - V * T . For each W there exists a unique largest V * and a unique smallest T ; an algorithm for finding suitable regular expressions for V and T is developed. Finally, an open problem of Paz and Peleg is answered: Every regular event is decomposable as a finite product of star events and prime events.

This paper is concerned with the sign detection problem in residue number systems. The proposed solution is applicable only to nonredundant systems. It is shown that under rather general conditions an explicit, closed formula for the sign function can be obtained. In a special case, when one of the moduli is 2, the sign function becomes an EXCLUSIVE-OR function. A sign detection algorithm is proposed and methods of implementing the algorithm are presented.

An asynchronous unit delay is an n input n output asynchronous sequential circuit in which the present value of the output n-tuple is equal to the value of the input n-tuple prior to the last input change. This paper considers the problem of determining when a fundamental mode flow table is realizable as a feedback-free connection of asynchronous unit delays. It is shown that such a realization exists if and only if the flow table is asynchronous definite, where the asynchronous definite property is a modification of the definite property of synchronous sequential machines. A straightforward method of realizing asynchronous definite flow tables without critical races by feedback-free circuits of asynchronous unit delays and combinational gates is developed. The use of asynchronous unit delays for definite tables avoids complicated secondary assignment problems, results in circuits with very simple structure, and brings closer the theories of synchronous and asynchronous sequential machines.

A regular event W is a star event if there exists another event V such that W = V * . In that case, V is called a root of W . It is shown that every star event has a unique minimum root, which is contained in every other root. An algorithm for finding the minimum root of a regular event is presented, and the root is shown to be regular. The results have applications to languages, codes, canonical forms for regular expressions, simplification of expressions, decomposition of sequential machines, and semigroup theory.

This paper presents a method for determining, from the flow table of a sequential machine, whether the machine is linearly realizable using the minimum number of unit delay elements. The method is an extension of a previously presented method for autonomous machines. A linearity algorithm is presented for each of two cases: 1) where the output is given and is to be linear, and 2) where the output is either not given or may be nonlinear. The method is simple, straightforward, and, in general, provides a ready solution to the linearity problem.

This paper considers the class of linear sequential circuits from the regular expression point of view. The circuits studied do not have special starting units which are necessary in the conventional construction of circuits from regular expressions. Since conventional regular expressions are only indirectly related to the circuit structure, a new regular language is developed. Using this language, the regular expression accepted by a linear circuit can be obtained more directly from the circuit. The regular expressions are then interpreted to provide a word description of the circuit behavior.

In the design of sequential relay circuits one often has to consider the circuit as a part of a larger system, and one must take into account the nature of the inputs to the circuit. Frequently, the inputs are two-terminal contact networks with one terminal grounded; such inputs will be called simple. This paper examines the formal design techniques as applied to circuits with simple inputs. It is shown that all relays should be considered as secondary, from the point of view of both races and minimization. Several other shortcomings of the present theory are pointed out. Properties of circuits with simple inputs are examined. It is shown that there are flow tables not realizable without races with simple inputs, and that the presently known secondary assignment methods are not applicable to circuits with simple inputs.

Kleene's regular expressions, which can be used for describing sequential circuits, were defined using three operators (union, concatenation and iterate) on sets of sequences.Word descriptions of problems can be more easily put in the regular expression language if the language is enriched by the inclusion of other logical operations.However, il~ the problem of converting the regular expression description to a state diagram, the existing methods either cannot handle expressions with additional operators, or are made quite complicated by the presence of such operators.In this paper the notion of a derivative of a regular expression is introduced atld the properties of derivatives are discussed.This leads, in a very natural way, to the construction of a state diagram from a regular expression containing any number of logical operators.

In this paper the relation between a sequential circuit and its regular expression is investigated. The circuits are without special starting units. One method of analysis of a circuit leads to a set of equations whose solutions are regular expressions related to the state diagram of the circuit. In another approach, a set of regular equations, identical in form to the next state equations, is obtained directly from the circuit. By reversing the regular equations and using derivatives, the regular equations are transformed to a form related to the reverse state diagram. The discussion clarifies the relationship among circuits, regular expressions and state diagrams. Moreover, further insight is obtained into the solution of equations with regular expressions as unknowns.

This paper presents a method of determining, from the flow table of an autonomous sequential machine, whether the machine can be realized by a linear circuit which uses the minimum possible number of secondary variables. The method is based on a class of binary partitions of states, which are used to find a minimal assignment of the secondary variables such that the next state and output functions are linear. The partitions are examined in detail and the properties necessary to produce a valid assignment are developed.

This paper considers the application of signal flow graph techniques to the problem of characterizing sequential circuits by regular expressions. It is shown that the methods of signal flow graph theory, with the proper interpretation, apply to state diagrams of sequential circuits. The use of these methods leads to a simple algorithm for obtaining a regular expression describing the behavior of a sequential circuit directly from its state diagram.

Methods have been described [1], [2] for constructing sequential machines directly from regular expressions. In the construction, every machine is assumed to have an input terminal, an output terminal and a special starting input terminal. The methods described [1], [2] involve a recursive procedure. For example, if machines MEand MFrealize the regular expressions E and F respectively, then the machine realizing the concatenation, R = EF, is obtained [1], [2] by connecting the output of MEto the starting terminal of MF. In this paper it is shown that a submachine generated by the algorithm in the middle of the synthesis procedure cannot be replaced in general, by an equivalent machine. It is felt that the proofs of the original algorithms [1], [2] are rather brief and do not point out the difficulties which might arise if proper precautions are not taken. To remedy this situation, this paper examines the construction in detail. The notion of recurrent realization of a regular expression is introduced, and a theorem is proved that the construction is valid if the proper precautions are taken.

This paper is an exposition of the theory of regular expressions and its applications to sequential circuits. The results of several authors are presented in a unified manner, pointing out the similarities and differences in the various treatments of the subject. Whenever possible, the terminology and notation of sequential circuit theory are used. The topics presented include: the relation of regular expressions to sequential circuits; algorithms for constructing sequential circuits and state diagrams corresponding to a given regular expression; methods for obtaining a regular expression from a state diagram of a sequential circuit, improper state diagrams, algebraic properties of regular expressions, and applications to codes.