Search results for author `Hotz'

• Thomas Chadzelek and Günter Hotz. Analytic machines. Technical Report 12/97, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, December 1997. (Gzipped PostScript, 10 pages, 69852 bytes)

  In this paper we present some results about analytic machines regarding the power of computations over Q or R, solutions of differential equations and the stability problem of dynamical systems. We first explain the machine model, which is a kind of sf Blum-Shub-Smale machine enhanced by infinite convergent computations. Next, we compare the computational power of such machines over the fields Q and R showing that finite computations with real numbers can be simulated by infinite converging computations on rational numbers, but the precision of the approximation is not known during the process. Our attention is then shifted to ordinary differential equations (ODEs), dynamical systems described by ODEs and the undecidability of a class of stability problems for dynamical systems.

• Günter Hotz and Bin Zhu. Verifying parameterized recursive circuits using semantics-preserving transformations of nets. Technical Report 11/97, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1997. (Gzipped PostScript, 34 pages, 156226 bytes)

• Günter Hotz and Bin Zhu. Applying Calculus of Nets to Hardware Verification Using Higher Order Logic. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1996.

• Günter Hotz and Bin Zhu. Formal Hardware Verification Based on Semantics-Preserved Transformations of Nets. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1996.

• Günter Hotz and Bin Zhu. Verifiable Synthesis by Using Semantics-Preserved Transformations of Nets. Technical report, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1996.

• G. Hotz and H. Wu. On the arrangement complexity of uniform trees. Technical Report SFB124-95-05, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1995. (Gzipped PostScript, 16 pages, 61466 bytes)

• T. Burch, J. Hartmann, G. Hotz, M. Krallmann, U. Nikolaus, S.M. Reddy, and U. Sparmann. Hit - a hierarchical environment for interactive test engineering. Technical Report SFB124-93-20, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), 1993. (Gzipped PostScript, 14 pages, 91772 bytes)

  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 gate 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 him to actively guide the test development process. Thus, he can easily apply module specific test strategies or `communicate' his high level knowledge about the functionality of the overall circuit 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.

• G. Hotz. Suchbäume und und Suchgraphen bei Markoffquellen. Technical Report SFB124-93-11, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1993.

• G. Hotz and J. Sellen. On algebraic computation tree and Betti numbers. Technical Report SFB124-93-10, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1993.

• U. Becker and G. Hotz. Foldingfree covering and graph embeddings. Technical Report SFB124-90-01, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1990. 17 Seiten. Erscheint in dem Sonderband der Abhandlungen des Mathematischen Seminares der Universität Hamburg anlä\3lich des 300-ten Geburtstages der Mathematischen Gesellschaft zu Hamburg.

• B. Becker, G. Hotz, R. Kolla, P. Molitor, and H.G. Osthof. CADIC - A system for hierarchical design of integrated circuits. Technical Report SFB124-86-07, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1986.

• B. Becker, G. Hotz, R. Kolla, and P. Molitor. Ein Cad-System zum Entwurf Integrierter Schaltungen. Technical Report SFB124-84-16, Sonderforschungsbereich 124 (VLSI-Entwurfsmethoden und Parallelität), Universität des Saarlandes, Postfach 15 11 50, 66041 Saarbrücken, Germany, 1984.

• Günter Hotz. A remark on nondecidabilities of initial value problems of ODEs. Technical report, Universität des Saarlandes, FB Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, 2003. Technical Report. (PostScript, 7 pages, 118030 bytes)

• Günter Hotz and Tobias Gärtner. Approximation von Folgen durch berechenbare Folgen - Eine neue Variante der Chaitin-Kolmogorov-Komplexität. Technical Report FB14-2002-01, Fakultät für Mathematik und Informatik, 66041 Saarbrücken, Germany, March 2002. Technical Report. (PostScript, 92885 bytes)

• Günter Hotz. Darstellung von Schaltfunktionen unter Ausnutzung von Symmetrien boolescher Algebren. Technical Report FB14-1999-02, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, March 1999. Technical Report. (Gzipped PostScript, 89 pages, 647460 bytes)

• Günter Hotz. A graph based parsing algorithm for context-free languages. Technical Report FB14-99-01, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, July 1999. Technical Report. (Gzipped PostScript, 6 pages, 46148 bytes)

  We present a simple algorithm deciding the word problem of c. f. languages in O(n^3). It decides this problem in time O(n^2) for unambiguous grammars and in time O(n) in the case of LR(k) grammars.

• Alexander Gamkrelidze, Günter Hotz, and Bin Zhu. Designing correct recursive circuits using semantics-preserving transformations of nets. Technical Report FB14-1998-02, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, December 1998. Technical Report. (Gzipped PostScript, 1 pages, 24557 bytes)

• Günter Hotz. Algorithmische Informationstheorie (Teil 1). Technical Report FB14-97-01, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, January 1997. Vorlesung an der Universität des Saarlandes, Wintersemester 1996/97. (Gzipped PostScript, 116 pages, 272435 bytes)

• Thomas Chadzelek, Günter Hotz, and Elmar Schömer. Heuristic motion planning with many degrees of freedom. Technical Report FB14-95-08, Universität des Saarlandes, FB 14 Informatik, Postfach 15 11 50, 66041 Saarbrücken, Germany, August 1995. (Gzipped PostScript, 48 pages, 306965 bytes)

  We present a general heuristic approach to the geometric motion planning problem with the aim to quickly solve intuitively simple problems. It is based on a divide-and-conquer path search strategy which makes inquiries about feasible paths; to answer these, we develop an efficient collision detection scheme that handles translations and rotations of polyhedra to compute all times of collision. The whole algorithm can be easily implemented and universally applied and has been successfully tested in a program for assembly planning.

• G. Hotz J. Eckstein and E. Schömer. Heuristische Bewegungsplanungsstrategien im IR^3. Technical Report FB14-95-05, Universität des Saarlandes, Saarbrücken, 1995. (Gzipped PostScript, 132 pages, 1368395 bytes)

  Two general heuristic approaches to the geometric motion planning problem are considered. Both heuristics make use of efficient collision detection algorithms and combine motion planning with collision detection to speed up planning or to extend planning facilities. The first approach tries to speed up motion planning by ignoring all obstacles in the scene which do not contribute to the planned collision-free path. In order to obtain such a minimal scene the heuristic computes a collision-free path in a scene and checks the planned paths for collisions with ignored obstacles using standard collision detection algorithms. The heuristic thereby conserves qualitative features of the algorithms used like completeness, computation of most-secure, euclidian-shortest or time-optimal paths. It can be used with any kind of motion planning algorithms like classical ones, algorithms for dynamical environments or multiple moving objects. The advantages of the heuristic are shown for a complete algorithm handling 3-dimensional objects with two translational degrees of freedom using the configuration space approach of Lozano-Perez and Wesley. The second heuristic extends the facilities of algorithms for static environments by classifying the obstacles in the scene in fixed and movable obstacles forming a motion planning problem with many degrees of freedom. The complex problem is decomposed in a series of simple problems which can be solved efficiently by known algorithms and the solutions are combined to a solution for the whole problem. It is shown that together with a problem modification strategy the heuristic nearly always extends and never reduces the facilities of motion planning algorithms in static environments.

• Yonggang Guan, Günter Hotz, and Armin Reichert. Tree grammars with multilinear interpretation. Technischer Bericht FB14-92-01, Fachbereich Informatik, Universität des Saarlandes, 1992. (Gzipped PostScript, 57 pages, 135009 bytes)

  We consider context-free grammars on trees and multilinear interpretations of the generated tree languages. An equivalent class of string rewriting systems, the coupled-context-free grammars are introduced and investigated. A hierarchy of language classes between CFL and CSL is obtained. Stepping up the hierarchy increases generation power only slightly which is measured by the ability for ``counting'' and ``copying''. Our grammars and language classes could be of practical interest for linguistic applications, i.e. for defining syntax of natural languages since they belong to the class of ``mildly-context-sensitive languages'' and provide a generalization of the Tree Adjoining Languages (TAL).

• Günter Hotz, Gero Vierke, and Börn Schieffer. Analytic machines. Technical Report TR95-025, Electronic Colloquium on Computational Complexity, 1995. (Gzipped PostScript, 23 pages, 75883 bytes)

  In this paper the R-machines defined by Blum, Shub and Smale are generalized by allowing infinite convergent computations. The description of real numbers is infinite. Therefore, considering arithmetic operations on real numbers should also imply infinite computations on analytic machines. We prove that R -computable functions are Q -analytic. We show that R-machines extended by finite sets of strong analytic operations are still Q -analytic. The halting problem of the analytic machines contains the stability problem of dynamic systems. It follows with well known methods that this problem is not analytical decidable. This is in a sense a stronger result as the numerical undecidable stability in the theory of Kolmogoroff, Arnold and Moser. Keywords: R -computability, stability, approximation