Delay test problems are well understood for gate level circuits. For certain logic families, delays depend on the charge stored at internal nodes. For such circuits, gate level models do not surface, A switch level simulator can be used for logic verification and stuck-at fault simulation. Toward making the delay fault simulation possible, this paper contributes three innovations to the switch-level technique: (1) Signals that remain steady over two consecutive vectors are identified using additional strength designations for charge and discharge paths; (2) Delay faults are propagated through MOS gates using articulation analyse's of the graph; and (3) A modified relaxation procedure determines the steady or non-steady status of signals at the same time it evaluates nodes. Experimental results demonstrate the validity of algorithms.

Timing verification and optimization have been formulated as mathematical programming problems. The computational aspects of using such a formulation for verifying clock schedules are considered. The formulation can have multiple solutions, and these extraneous solutions can cause previously published algorithms to produce incorrect or misleading results. The conditions under which multiple solutions exist are characterized, and it is shown that even when the solution is unique, the running times of these previous algorithms can be unbounded. By contrast, a simple polynomial time algorithm for clock schedule verification is exhibited. The algorithm was implemented and used to check the timing of all the circuits in the ISCAS-89 benchmark suite. Observed running times are linear in circuit size and quite practical.>

It is shown how the substitution of a partial order facilitates automatic modeling in switch-level simulators that use the traditional total ordering of strengths for resolving conflicts between opposing signals while increasing the accuracy of that model. Minimization techniques are described that reduce the number of required modeling strengths to acceptable levels. As a result, the use of partially ordered strengths does not significantly degrade simulation performance. It is also shown how to rearrange the computations performed during switch-level simulation to yield a nearly twofold increase in speed for good circuit simulation. A switch-level simulator using this algorithm with partially ordered strengths has been successfully used to verify several full-custom industrial designs.>

A key idea in switch-level simulation is the use of a total ordering of signal strengths to resolve conflicts between opposing signals. For many circuits, however, it is not possible to assign such strengths to circuit elements in a logically consistent fashion without user intervention. It is shown that the use of a partial ordering of strengths avoids these difficulties and allows modeling to be done automatically. The authors also discuss the need to minimize the number of distinct strengths needed to model a circuit, because simulation times are affected by the number of strengths being used. This is especially important for compiled switch-level simulators that generate representations whose size is proportional to the number of strengths. Statistics on the application of these ideas to industrial chips are presented.>

Interconnecting two rows of points across an intervening channel is an important problem in the design of LSI circuits. The most common methodology for producing such interconnections uses two orthogonal layers of parallel conductors and allows wires to "dogleg" arbitrarily. Although effective heuristic procedures are available for routing channels with this methodology, no efficient optimal algorithm has yet been discovered for the general case problem. We show that such an algorithm is unlikely to exist by establishing that this problem is NP-complete.

A general model for data compression which includes most data compression systems in the fiterature as special cases is presented.Macro schemes are based on the principle of finding redundant strings or patterns and replacing them by pointers to a common copy.Different varieties of macro schemes may be defmed by specifying the meaning of a pointer; that is, a pointer may indicate a substring of the compressed string, a substring of the original string, or a substring of some other string such as an external dictionary.Other varieties of macro schemes may be defined by restricting the type of overlapping or recursion that may be used.Trade-offs between different varieties of macro schemes, exact lower bounds on the amount of compression obtainable, and the complexity of encoding and decoding are discussed, as well as how the work of other authors relates to this model.

Given a function f over a finite domain D and an arbitrary starting point x, the sequence $f^0 (x),f^1 (x),f^2 (x), \cdots $ is ultimately periodic. Such sequences are typically the output of random number generators. The cycle problem is to determine the first repeated element $f^n (x)$ in the sequence. Previous algorithms for this problem have required $3n + O(1)$ operations. In this paper we show that $n(1 + \Theta (1/\sqrt M ))$ steps are both necessary and sufficient, if M memory cells are available to store values of the function. We explicitly consider the performance of the algorithm as a function of the amount of memory available and the relative cost of evaluating f and comparing sequence elements for equality.

We present an algorithm for constructing a tree to satisfy a set of lineage constraints on common ancestors. We then apply this algorithm to synthesize a relational algebra expression from a simple tableau, a problem arising in the theory of relational databases.

The assembled length of a span-dependent jump instruction depends on the distance between the instruction and its target. Such instructions are found on many computers and typically have two forms, long and short. We consider the problem of minimizing object program length for such machines by chaining together jumps with the same target. Although the problem is NP-complete in its most general form, several mildly restricted forms of the problem exist that are of practical importance and have efficient solutions.

Given a function f over a finite domain D and an arbitrary starting point x, the sequence x,f(x),f(f(x)),... is ultimately periodic. Such sequences typically are used for constructing random number generators. The cycle problem is to determine the first repeated element fn(x) in the sequence. Previous algorithms for this problem have required 3n operations. In this paper we present an algorithm which only requires n(1+O(1/(@@@@)M)) steps, if M memory cells are available to store values of the function. By increasing M, this running time can be made arbitrarily close to the information-theoretic lower bound on the running time of any algorithm for the cycle problem. Our treatment is novel in that we explicitly consider the performance of the algorithm as a function of the amount of memory available as well as the relative cost of evaluating f and comparing sequence elements for equality.

A general model for data compression is presented which includes most data compression systems in the literature as special cases. All macro schemes are based on the principle of finding redundant strings or patterns and replacing them by pointers to a common copy. Different varieties of macro schemes may be defined by varying the interpretation of pointers, for instance, a pointer may indicate a substring of the compressed string, a substring of the original string, or a substring of some other string such as an external dictionary. Other varieties of macros schemes may be defined by restricting the type of overlapping or recursion that may be used. Trade-offs between different varieties of macro schemes, exact lower bounds on the amount of compression obtainable, and the complexity of encoding and decoding are discussed as well as how the work of other authors (such as Lempel-Ziv) relates to this model.

AESTRA~ r Many parsing techniques are parameterlzed by the amount of context allowed in making parsmg decisions (e g the LR(k), LL(k), and SLR(k) hierarchies).The best-known algorithms for testing membership in these classes depend exponentially on k when the test is performed determinlsttcally, and polynomlally on k when the test IS done nondetermmistically This paper shows that the deterministic complexity of any uniform algorithm for, say, LR(k) testing is a polynommi function of k if and only if P = NP.We then provide a lower bound on the growth rate with respect to k As to the relationships between the various classes, it is shown that the time needed for testing the LL(k) property ~s a lower bound on the time needed for testing membership in any subset of the LR(k) grammars that includes all the LL(k) grammars These results suggest that the complexity of LL(I) testing is a lower bound on the complexity of testing membership m most useful classes of grammars Finally, some relative decision problems are mvesUgated, that is, problems of testing whether a given member of some class is also a member of some other specified class A polynomial time algorithm ts given for determining for an LR(k) grammar whether there exists a k' for which the grammar is LL(k').Slmdar results are shown for the SLR(k) and strong LL(k) hierarchies KEY WORDS AND eHRAS~S: computational complexity, lower bounds, context-free grammars, LR(k) and LL(k) parsing

No abstract available.

There is no recursive function bounding the succinctness gained using ambiguous grammars rather than unambiguous ones in the description of unambiguous context-free languages.

We consider expressions whose arguments are relations and whose operators are chosen from among $\cup , \circ ,{}^*$, and ${}^{ - 1}$. We further assume that operands may be designated “sparse” or “dense”, in a manner to be made formal subsequently. Our aim is to determine whether the evaluation of such an expression is (a) as hard as general transitive closure, (b) as hard as transitive closure for sparse graphs, (c) as hard as finding connected components of an undirected graph.

We present several techniques for proving lower bounds that can be applied to problems about grammars, formal languages, program schemes, simple programming languages, and automata. These techniques include dichotomization, extensions of dichotomization to certain classes of relational problems, recursive analogues of the Post Correspondence Problem, and the reachability problem. These techniques provide many new lower bounds and provide a unified framework for viewing much of the work on the complexity of problems about grammars, languages, schemes, and automata. We show how to prove the undecidability of a problem by efficiently reducing the membership problem for Tms that always halt to it. We also introduce the forbidden subgraph problem.

A bottom-up parsing technique which can make nonleftmost possible reductions in sentential forms is said to be noncanonical Nearly every existing parsing technique can be extended to a noncanonical method which operates on larger classes of grammars and languages than the original technique. Moreover, most of the resulting parsers run in time linearly proportional to the length of their input strings. Several such extensions are defined and analyzed from the points of view of both power and decidability. The results are presented in terms of a general bottom-up parsing model which yields a common decision procedure for testing membership in many of the existing and extended classes.

It is shown that there is a sequence of languages E1, E2,... such that every correct prefix parser (one which detects errors at the earliest possible moment, e.g., LR or LL parsers) for En has size 2cn, yet a deterministic PDA recognizing En exists and has size O(n2). There is another easily described sequence of languages N1,N2,... for which Nn has a nondeterministic PDA of size O(n2) but no deterministic PDA of size less than 2cn. It is shown moreover, that this latter exponential gap can be made arbitrarily large for different sequences of languages.

We consider expressions whose arguments are relations and whose operators are chosen from among ∪, ο, *, and -1. We further assume that operands may be designated "sparse" or "dense", in a manner to be made formal subsequently. Our aim is to determine whether the evaluation of such an expression is (a) as hard as general transitive closure (b) as hard as transitive closure for sparse graphs. (c) as hard as connected components of an undirected graph.

In this paper we derive upper bounds on the complexity of LR(k) testing both when k is considered to be a fixed integer and also when k is considered to be a parameter of the problem. In the latter case, we show that the lower bounds on the running time of such algorithms depend very strongly on the representation chosen for k. Thus LR(k) testing is NP-complete when k is expressed in unary and complete for nondeterministic exponential time when k is expressed in binary.These results carry over to many other parameterized classes of grammars, such as the LL(k), strong LL(k), SLR(k), LC(k), strong LC(k), BRC(l,k), BC(l,k) and extended precedence (l,k) grammars.

In [1] and [2] a complexity theory for formal languages and automata was developed. This theory implies most of the previously known results and yields many new results as well. Here we develop an analogous theory for several classes of more practically motivated problems. Two such classes, both closely related to formal language and automata theory, suggest themselves - grammar problems and program scheme problems. Here, our primary emphasis is on grammar problems of interest in parsing and compiling. Other problems considered include -

We attempt to characterize classes of schemes allowing pushdown stores, building on an earlier work by Constable and Gries [1]. We study the effect (on the computational power) of allowing one, two, or more pushdown stores, both with and without the ability to detect when a pds is empty. A main result is that using one pds is computationally equivalent to allowing recursive functions. We also study the effect of adding the ability to do integer arithmetic, and multidimensional arrays.