The paper discusses SiLVIA simulation library. The main purpose of SiLVIA is to supply procedures for simulating the dynamics of colliding rigid bodies and the interactive manipulation of these bodies in virtual environments. Detecting collisions between virtual objects and calculating their reaction to these collisions play an important role in VR applications such as ergonomy, studies or virtual assembly simulations.

Detecting collisions and calculating physically correct collision responses play an important role when simulating the dynamics of colliding rigid bodies. VR-applications such as virtual assembly planning and ergonomy studies can especially profit from advances in these directions, because they enable an interactive and intuitive manipulation of objects in virtual environments. This paper presents new algorithms for the calculation of contact forces in multi-body systems with unilateral contacts.

Coupled-Context-Free Grammars are a natural generalization of context-free grammars obtained by combining nonterminals to corresponding parentheses which can only be substituted simultaneously. Refering to their generative capacity we obtain an infinite hierarchy of languages that comprises the context-free ones as the first and all those generated by Tree Adjoining Grammars (TAGs) as the second element. The latter is important because today, TAGs are commonly used to model the syntax of natural languages. Here, we present a completely new approach to analyse this language hierarchy. It solves the word problem for the class of languages generated by TAGs in time O(n 6 ), n length of the input, by reducing it to the analysis of sequences of parentheses.

Conventional tools for test generation and fault simulation appear to the test engineer as black boxes which neither communicate their results in a convenient way, nor allow for any interactive guidance by the test engineer. In contrast, the HIT system presented in this paper supports interactive test engineering, thus combining the power of state level test generation algorithms with the high level knowledge of the test engineer. Since the HIT system has been integrated into a hierarchical design system (CADIC), the results of test tools can be visualized at the hierarchical circuit specifications given by the designer. Based on this visualization, the critical, untestable areas of the circuit can be easily located. Additionally, the test engineer is supplied with flexible test tools, which allow to actively guide the test development process. Thus, module specific test strategies can be applied or high level knowledge about the functionality of the overall circuit can be 'communicated' to speed-up test generation and redundancy identification. An application example shows that with simple strategies for interactive test engineering the results of test generation can be improved dramatically.

We present an algebraic approach to hierarchical design of integrated circuits. This approach is based on a of nets which includes topological as well as behavioural aspects of integrated circuits. We have developed a hierarchical design system called CADIC which is build around this calculus in much the same way as e.g. Algol is build around numerics. An example for the design of a family of fast adders will demonstrate the power of this calculus. Finally we will give a summary outline on the structure of procedures which automatically transform the design into lower design levels.

The optimal planar layout of planar graphs with respect to the $L_1 $- or $L_2 $-metric leads to NP-hard problems, if one assumes the nodes of the graph to be fixed in the plane (see [FiPa], [Be]). In this paper we consider the (optimal) layout of graphs with fixed boundary (i.e., graphs, where only the nodes of a given cycle of the graph have fixed positions in the plane). The investigated layouts are straight line embeddings in a continuous part of the plane; the cost of a layout is calculated with help of very general cost functions including the pth power of the usual Euclidean distance metric for $p = 2,3, \cdots $ (for short, $l_p $-metric). For a large class of graphs, which, for example, occur in chip layout problems as the abstract structure of switching circuits, we show the existence and uniqueness of the optimal layout. The main part of the paper is concerned with planar graphs. We get an interesting characterization of nonplanar layouts of planar graphs, which shows that the optimal layout of a planar graph is planar or at least “quasiplanar.” This property makes it possible to decompose the general layout problem into two independent problems: (i) Find a layout of a circuit that is not necessarily planar, but that has an “lallowed crossing behaviour.” (ii) Fix the crossing points and then optimize the layout. Our theorems show that no new contacts (crossing points) will be generated. In the Appendix we outline some (efficient, polynomial time) methods for the construction of optimal layouts and give as an example the optimal layouts of a recursively defined n-bit adder and multiplier.

Let G = (V, T, P, S) a c.f. grammar and F(V ⌣ T) the free group generated by V ⌣ T, ((G) = F(V ⌣ T/P is the quotient of F (V ⌣ T) factorized by the relationsystem generated by P. We prove that ((G) only depends on L(G) if G has no superflous variables. This means (fx107-1(G) is an invariant of grammar transformations which preserve the language. Each finitely representable group can be represented by a one sided liner grammar G as ((G). In a straightforward manner one can compute finite basises for the Alexander-ideals of the groups ((G. This ideals are finitely generated in an quotient of a Polynomring by a finitely generated ideal. Therefore this leads to effective computable necessary conditions for the equivalence of c.f. grammars.