Narrow Results

An efficient simulation algorithm using an algebra of transients for gate circuits was proposed by Brzozowski and Ésik. This algorithm seems capable of predicting all the signal changes that can occur in a circuit under worst-case delay conditions. We verify this claim by comparing simulation with binary analysis. For any feedback-free circuit consisting of one- and two-input gates, we prove that all signal changes predicted by simulation occur in binary analysis, provided that wire delays are taken into account. Two types of finite automata play an important role in our proof.

Transient simulation of a gate circuit is an efficient method of counting signal changes occurring during a transition of the circuit. It is known that this simulation covers the results of classical binary analysis, in the sense that all signal changes appearing in binary analysis are also predicted by the simulation. For feedback-free circuits of 1- and 2-input gates, it had been shown that the converse also holds, if wire delays are taken into account. In this paper we generalize this result. First, we prove that, for any feedback-free circuit N of arbitrary gates, there exists an expanded circuit, constructed by adding a number of delays to each wire of N, such that binary analysis of covers transient simulation of N. For this result, the number of delays added to a wire is obtained from the transient simulation. Our second result involves adding only one delay per wire, which leads to the singular circuit of N. This result is restricted to circuits consisting only of gates realizing functions from the set , functions obtained by complementing any number of inputs and/or the output of a function from , and FORKS. The numbers of inputs of the AND, OR and XOR gates are arbitrary, and all functions of two variables are included. We show that binary analysis of such a circuit covers transient simulation of N. We also show that this result cannot be extended to arbitrary gates, if we allow only a constant number of delays per wire.

Transient algebra is a multi-valued algebra for hazard detection in gate circuits. Sequences of alternating 0's and 1's, called transients, represent signal values, and gates are modeled by extensions of boolean functions to transients. Formulas for computing the output transient of a gate from the input transients are known for NOT, AND, OR and XOR gates and their complements, but, in general, even the problem of deciding whether the length of the output transient exceeds a given bound is NP-complete. We propose a method of evaluating extensions of general boolean functions. We study a class of functions for which, instead of evaluating the extensions on a given set of transients, it is possible to get the same values by using transients derived from the given ones, but having length at most 3. We prove that all functions of three variables, as well as certain other functions, have this property, and can be efficiently evaluated.

In this paper, we investigate the complexity of computing the detector, constructor and lexicographic constructor functions for a given language. The following classes of languages will be considered: (1) context-free languages, (2) regular sets, (3) languages accepted by one-way nondeterministic auxiliary pushdown automata, (4) languages accepted by one-way nondeterministic logspace-bounded Turing machines, (5) two-way deterministic pushdown automaton languages, (6) languages accepted by uniform families of constant-depth polynomial-size Boolean circuits, and (7) languages accepted by multihead finite automata. We show that for the classes (1)–(4), efficient detectors, constructors and lexicographic constructors exist, whereas for (5)– (7) polynomial-time computable detectors, constructors and lexicographic constructors exist iff there are no sparse sets in NP−P (or equivalently, E=NE). Our results provide sharp boundaries between classes of languages which have efficient detectors, constructors and classes of languages for which efficient detectors and constructors do not appear to exist.