@string{IEEECAD = "IEEE Transactions on Computer Aided Design"} @string{IEEETOVLSI = "IEEE Transactions on VLSI Systems"} @string{IEEETC = "IEEE Transactions on Computers"} @string{FUNDAMENTA = "Fundamenta Informaticae, Annales Societatis, Mathematicae Polonae"} @string{INTEGRATION = "INTEGRATION, the VLSI Journal"} @string{JCSS = "J. Comp. System Sci."} @string{JACM = "J. Assoc. Comput. Mach."} @string{siemens = "Siemens Forsch.-- u. Entwickl.--Ber."} @string{IPL = "Information Processing Lett."} @string{TCS = "Theoretical Computer Science"} @string{Freeman = "W.H.Freeman and Company"} @string{INFaCONTR = "Information and Control"} @string{EIK = "EIK Journal of Information Processing and Cybernetics"} @string{AcInf = "Acta Informatica"} @string{SIAM = "SIAM Journal on Computing"} @string{euromicro = "The EuroMicro Journal, Microprocessing and Microprogramming"} @string{FuE = "INFORMATIK, Forschung \& Entwicklung"} @string{IaC = "Information and Computation"} @string{ORL = "Operations Research Letters"} @string{FCT = "Fundamentals of Computation Theory"} @string{AdW = "Akademie der Wissenschaften"} @string{teubner = "B.G. Teubner Verlag, Stuttgart"} @string{AV = "Akademie Verlag"} @string{SV = "Springer Verlag"} @string{springer = "Springer Verlag"} @string{bi = "B.I. Wissenschaftsverlag"} @string{gruyter = "Walter de Gruyter Verlag"} @string{AMSE = "Association for the Advancement of Modelling-- and Simulation--Techniques in Enterprises"} @string{FOCS = "Foundations of Computer Science"} @string{IEEEpub = "IEEE Computer Society Press"} @string{IEEEadr = "IEEE Computer Society, Post Office Box 80452, Worldway Postal Center, Los Angeles, CA 90080"} @string{sfb124 = {Sonderforschungsbereich 124 {\em VLSI Entwurfsmethoden und Parallelit\"at}}} @string{sfbadr = {Fachbereich Informatik, Universit{\"a}t des Saarlandes, Postfach 15 11 50, 66041 Saarbr{\"u}cken, FRG}} @string{fb14adr = {66041 Saarbr{\"u}cken}} @string{fb14 = {Fachbereich Informatik, Universit{\"a}t des Saarlandes}} @string{IEEECAD = "IEEE Transactions on Computer Aided Design"} @string{IEEETOVLSI = "IEEE Transactions on VLSI Systems"} @string{IEEETC = "IEEE Transactions on Computers"} @string{FUNDAMENTA = "Fundamenta Informaticae, Annales Societatis, Mathematicae Polonae"} @string{INTEGRATION = "INTEGRATION, the VLSI Journal"} @string{JCSS = "J. Comp. System Sci."} @string{JACM = "J. Assoc. Comput. Mach."} @string{siemens = "Siemens Forsch.-- u. Entwickl.--Ber."} @string{IPL = "Information Processing Lett."} @string{TCS = "Theoretical Computer Science"} @string{Freeman = "W.H.Freeman and Company"} @string{INFaCONTR = "Information and Control"} @string{EIK = "EIK Journal of Information Processing and Cybernetics"} @string{AcInf = "Acta Informatica"} @string{euromicro = "The EuroMicro Journal, Microprocessing and Microprogramming"} @string{FuE = "INFORMATIK, Forschung \& Entwicklung"} @string{IaC = "Information and Computation"} @string{ORL = "Operations Research Letters"} @string{FCT = "Fundamentals of Computation Theory"} @string{AdW = "Akademie der Wissenschaften"} @string{teubner = "B.G. Teubner Verlag, Stuttgart"} @string{AV = "Akademie Verlag"} @string{SV = "Springer Verlag"} @string{springer = "Springer Verlag"} @string{bi = "B.I. Wissenschaftsverlag"} @string{gruyter = "Walter de Gruyter Verlag"} @string{AMSE = "Association for the Advancement of Modelling-- and Simulation--Techniques in Enterprises"} @string{FOCS = "Foundations of Computer Science"} @string{IEEEpub = "IEEE Computer Society Press"} @string{IEEEadr = "IEEE Computer Society, Post Office Box 80452, Worldway Postal Center, Los Angeles, CA 90080"} @string{sfb124 = {Sonderforschungsbereich 124 {\em VLSI Entwurfsmethoden und Parallelit\"at}}} @STRING{ASPDAC = {ASP Design Automation Conf.}} @STRING{GLS = {Great Lakes Symp. VLSI}} @STRING{EDTC = {European Design \& Test Conf.}} @STRING{GIW = {GI/ITG Workshop ``Testmethoden und Zuverl\"assigkeit von Schaltungen und Systemen''}} @inproceedings{AMAI, author = {J{\"u}rgen Sellen}, title = {On the Topological Structure of Configuration Spaces}, booktitle = {Annals of Mathematics and Artificial Intelligence}, note = {to appear}, postscript = {AMAI.ps.Z} } @inproceedings{SIAM, author = {J{\"u}rgen Sellen}, title = {Lower Bounds for Geometrical and Physical Problems}, booktitle = {SIAM Journal on Computing}, note = {to appear}, postscript = {SIAM.ps.Z} } @inproceedings{ho:reduktion, author = {G. Hotz}, title = {{Z}ur {R}eduktionstheorie der booleschen {A}lgebra}, booktitle = {{C}olloquium \mbox{\"uber} {S}chaltkreis- und {S}chaltwerk-{T}heorie (1960)}, year = {1961}, publisher = {\mbox{{B}irkh\"auser} {V}erlag} } @article{ho:sprachen-artikel, author = {G. Hotz}, title = {{E}indeutigkeit und {M}ehrdeutigkeit formaler {S}prachen}, journal = EIK, pages = {235-246}, year = {1966}, volume = {2} } @article{ho:kategorie-artikel, author = {G. Hotz}, title = {{E}ine {A}lgebraisierung des {S}yntheseproblems f\"ur {S}chaltkreise}, journal = EIK, pages = {185-205,209-231}, year = {1965}, volume = {1} } @article{ho:dreifach-artikel, author = {G. Hotz}, title = {{E}inbettung von {S}treckenkomplexen in die {E}bene}, journal = {Mathematische Annalen}, pages = {214-223}, year = {1962}, volume = {167} } @article{grho:lp, author = {U. Becker-Groh and G. Hotz}, title = {{E}in {P}lanarit\"atstest f\"ur planar-konvexe {G}rapheinbettungen mit linearer {K}omplexit\"at}, journal = {Beitr\"age zur Algebra und Geometrie}, pages = {191-200}, year = {1984}, volume = {18} } @inproceedings{bbos:stacs85, author = {B. Becker and H.G. Osthof}, title = {Layouts with Wires of Balanced Length}, booktitle = {Proceedings of the 2nd Annual Symposium on Theoretical Aspects of Computer Science (STACS85)}, pages = {21-31}, year = {1985}, month = {January} } @article{mo:euromicro85, author = {P. Molitor}, title = {Layer Assignment by Simulated Annealing}, journal = euromicro, pages = {345-350}, year = {1985}, volume = {16} } @inproceedings{bbsi:focs87, author = {B. Becker and H.U. Simon}, title = {How Robust is the n-Cube?}, booktitle = {Proceedings of the 27th FOCS}, pages = {283-291}, year = {1986}, month = {October} } @article{bhkm:cadic, author = {B. Becker and G. Hotz and R. Kolla and P. Molitor}, title = {Ein logisch topologischer {K}alk\"ul zur {K}onstruktion von integrierten {S}chaltkreisen}, journal = {INFORMATIK, FORSCHUNG \& ENTWICKLUNG}, pages = {38-47,72-82}, year = {1986}, volume = {1}, number = {1,2} } @inproceedings{hkm:gragra, author = {G. Hotz and R. Kolla and P. Molitor}, title = {On Network Algebras and Recursive Functions}, booktitle = {Proceedings of the 3rd International Workshop on Graph Grammars and Their Applications to Computer Science, LNCS 291}, pages = {250-261}, year = {1986}, publisher = springer } @article{bbecker:multiplier, author = {B. Becker}, title = {An Easily Testable Optimal Time {VLSI}-Multiplier}, journal = AcInf, pages = {363-380}, year = {1987}, volume = {24} } @article{bbho:lp, author = {B. Becker and G. Hotz}, title = {On the Optimal Layout of Planar Graphs with fixed Boundary}, journal = SIAM, year = {1987}, month = {October}, volume = {16}, number = {5} } @article{bbos:lp, author = {B. Becker and H.G. Osthof}, title = {Layouts with Wires of Balanced Length}, journal = IaC, pages = {45-58}, year = {1987}, month = {April}, volume = {73}, number = {1} } @article{bbso:euromicro87, author = {B. Becker and H. Soukup}, title = {{CMOS} Stuck-Open Self-Test for an Optimal {VLSI}-Multiplier}, journal = euromicro, pages = {153-157}, year = {1987}, volume = {20} } @inproceedings{bhkmo:dac87, author = {B. Becker and G. Hotz and R. Kolla and P. Molitor and H.G. Osthof}, title = {Hierarchical Design based on a Calculus of Nets}, booktitle = {Proceedings of the 24th ACM/IEEE Design Automation Conference (DAC87)}, pages = {649-653}, year = {1987}, month = {June} } @inproceedings{bhkmo:eis87, author = {B. Becker and G. Hotz and R. Kolla and P. Molitor and H.G. Osthof}, title = {{CADIC} - {E}in {S}ystem zum hierarchischen {E}ntwurf integrierter {S}chaltungen}, booktitle = {Tagungsband des 3-ten E.I.S.-Workshops}, pages = {235-245}, year = {1987} } @inproceedings{mo:stacs87, author = {P. Molitor}, title = {On the Contact Minimization Problem}, booktitle = {Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science (STACS87)}, pages = {420-431}, year = {1987}, month = {February} } @article{Sim88a, author = {H.U. Simon}, title = {{Approximative L\"osungen des Mehrprozessor--Scheduling--Problems}}, journal = siemens, pages = {18--24}, year = {1988}, volume = {17}, number = {1} } @article{Sim88b, author = {H.U. Simon}, title = {A Continuous Bound on the Performance of Critical--Path Schedules}, journal = EIK, pages = {171--189}, year = {1988}, volume = {24}, number = {4/5} } @article{Sim88c, author = {B. Becker and H.U. Simon}, title = {How Robust is the $n$--Cube ?}, journal = IaC, pages = {162--178}, year = {1988}, volume = {77}, number = {2} } @article{Sim88d, author = {A. B{\"o}ttcher and G. Lawitzky and H. U. Simon}, title = {Worstcase--Analysis of Heuristics for the Local Microcode Optimization Problem}, journal = ORL, pages = {127--130}, year = {1988}, volume = {7}, number = {3} } @article{bbecker:adder, author = {B. Becker}, title = {Efficient Testing of Optimal-Time Adders}, journal = IEEETC, pages = {1113-1121}, year = {1988}, volume = {C-37} } @inproceedings{bbsp:awoc88, author = {B. Becker and U. Sparmann}, title = {Regular structures and testing: {RCC}-adders}, booktitle = {Proceedings of the 3rd Aegean Workshop on Computing}, pages = {288-300}, year = {1988} } @article{mo:free, author = {P. Molitor}, title = {Free Net Algebras in {VLSI}-Theory}, journal = FUNDAMENTA, pages = {117-142}, year = {1988}, month = {June}, volume = {XI} } @article{sp:eik88, author = {U. Sparmann}, title = {Design and Test of a Pattern Matching Circuit}, journal = EIK, pages = {329--338}, year = {1988}, volume = {24} } @article{bbko:stacs88, author = {B. Becker and R. Kolla}, title = {On the Construction of Optimal Time Adders}, journal = FUNDAMENTA, pages = {205-220}, year = {1989}, volume = {XII} } @inproceedings{bbsp:ftcs89, author = {B. Becker and U. Sparmann}, title = {Computations over Finite Monoids and their Test Complexity ({E}xtended {A}bstract)}, booktitle = {19th International Symposium on Fault-Tolerant Computing}, pages = {299-306}, year = {1989} } @inproceedings{hart:itggi89, author = {J. Hartmann}, title = {{\"U}ber probabilistisches und deterministisches {T}esten}, booktitle = {Tagungsband des 1.\ ITG/GI-Workshops `Testmethoden und Zuverl\"assigkeit von Schaltungen und Systemen'}, year = {1989}, note = {4 Seiten} } @article{komo:layer, author = {R. Kolla and P. Molitor}, title = {A note on hierarchical layer assignment}, journal = INTEGRATION, pages = {213-230}, year = {1989}, volume = {7} } @inproceedings{HiKo, author = {U. Hinsberger and R. Kolla}, title = {{C}ell based performance optimization of combinational circuits}, booktitle = {Proceedings of the 1st European Design Automation Conference (EDAC90)}, pages = {594-599}, year = {1990} } @article{bbha:eik90, author = {B. Becker and J. Hartmann}, title = {{O}ptimal-Time Multipliers and C-Testability}, journal = EIK, pages = {547-561}, year = {1990}, note = {Has also appeared in {\it Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures (SPAA90)}} } @inproceedings{bbha:spaa90, author = {B. Becker and J. Hartmann}, title = {{O}ptimal-Time Multipliers and {C}-Testability}, booktitle = {Proceedings of the 2nd Annual Symposium on Parallel Algorithms and Architectures}, pages = {146-154}, year = {1990} } @inproceedings{burch90, author = {Th. Burch and W. Vogelgesang}, title = {A graphical system for recursive circuit specifications and fast transformations to {EDIF}}, booktitle = {Proceedings of the 4th European EDIF Forum}, year = {1990}, month = {October}, note = {6 pages} } @inproceedings{cadic:edac90, author = {B. Becker and Th. Burch and G. Hotz and D. Kiel and R. Kolla and P. Molitor and H. G. Osthof and G. Pitsch and U. Sparmann}, title = {A Graphical System for Hierarchical Specifications and Checkups of {VLSI} Circuits}, booktitle = {Proceedings of the 1st European Design Automation Conference (EDAC90)}, pages = {174-179}, year = {1990} } @inproceedings{hart:itggi90, author = {J. Hartmann}, title = {{A}nalyse zweier {T}echniken zur {E}rh\"ohung der {Z}ufallstestbarkeit}, booktitle = {Tagungsband des 2.\ ITG/GI-Workshops `Testmethoden und Zuverl\"assigkeit von Schaltungen und Systemen'}, year = {1990}, note = {6 Seiten} } @inproceedings{ko:spannver, author = {R. Kolla}, title = {A Dynamic Programming Approach to the Power Supply Net Sizing Problem}, booktitle = {Proceedings of the 1st European Design Automation Conference (EDAC90)}, pages = {600-604}, year = {1990} } @article{kolla:eik, author = {R. Kolla}, title = {Minimum Area Sizing of Power Supply Nets in {VLSI} Circuits}, journal = EIK, pages = {585-605}, year = {1990}, volume = {11-12} } @article{mo:torus, author = {P. Molitor}, title = {Constrained Via Minimization for Systolic Arrays}, journal = IEEECAD, pages = {537-542}, year = {1990}, month = {May}, volume = {CAD-9}, number = {5} } @inproceedings{uwe:itggi90, author = {U. Sparmann and W. Weber}, title = {{Z}ur {E}rstellung qualitativ hochwertiger {T}ests f\"ur gro\3e kombinatorische {S}chaltkreise}, booktitle = {Tagungsband des ITG/GI-Workshops `Testmethoden und Zuverl\"assigkeit von Schaltungen und Systemen'}, year = {1990}, note = {7 Seiten} } @inproceedings{ITG91, author = {Joachim Hartmann and Bj\"orn Schieffer and Uwe Sparmann}, title = {{COFS} - A cell oriented fault simulator}, booktitle = {Tagungsband des 3.\ ITG/GI-Workshops `Testmethoden und Zuverl\"assigkeit von Schaltungen und Systemen'}, year = {1991}, postscript = {ITG91.ps.Z}, abstract = {Currently, in most fault simulators physical defects have to be modeled as stuck-at faults in networks of primitive gates such as AND, NAND, etc. On the other hand, the inadequacy of the stuck-at fault model for today's technologies has been pointed out by many authors. In this paper, a compiler driven fault simulator is presented which handles arbitrary combinational faults. The set of basic cells and their fault models are not coded into the algorithm but can be specified by the user in a library. It is shown that this increased flexibility, which is obtained by cell instead of line oriented fault injection, does not degrade the performance of the simulator but, in contrast, results in a considerable speed-up (up to factor 40).} } @article{bbsp:fi, author = {B. Becker and U. Sparmann}, title = {A Uniform Test Approach for {RCC}-{A}dders}, journal = FUNDAMENTA, pages = {185-219}, year = {1991} } @article{bbsp:tcs, author = {B. Becker and U. Sparmann}, title = {Computations over Finite Monoids and their Test Complexity}, journal = TCS, pages = {225-250}, year = {1991} } @inproceedings{behakrsp:sim, author = {B. Becker and R. Hahn and R. Krieger and U. Sparmann}, title = {Structure Based Methods for Parallel Pattern Fault Simulation in Combinational Circuits}, booktitle = {Proceedings of the 2nd European Design Automation Conference (EDAC91)}, year = {1991} } @inproceedings{gpes:stacs91, author = {G. Pitsch and E. Sch\"omer}, title = {{O}ptimal {P}arallel {R}ecognition of {B}racket {L}anguages on {H}ypercubes}, booktitle = {Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science (STACS91)}, pages = {434-443}, year = {1991}, month = {February} } @inproceedings{ha:stacs91, author = {J. Hartmann}, title = {The random testability of the n-input {AND} gate}, booktitle = {Proceedings of the 8th Annual Symposium on Theoretical Aspects of Computer Science}, pages = {488-498}, year = {1991}, month = {February} } @article{kose:sim, author = {R. Kolla and B. Serf}, title = {The virtual feedback problem in hierarchical representations of combinational circuits}, journal = AcInf, pages = {463--476}, year = {1991}, volume = {28} } @inproceedings{marzin:issac91, author = {R. Marzinkewitsch}, title = {Operating computer algebra systems by handprinted input}, booktitle = {Proceedings of ISSAC 91}, year = {1991} } @article{mo:survey, author = {P. Molitor}, title = {A survey on wiring}, journal = EIK, pages = {3-19}, year = {1991}, volume = {{\bf EIK} 27}, number = {1} } @article{molitor-kaufmann, author = {M. Kaufmann and P. Molitor}, title = {Minimal stretching of a layout to ensure 2-layer wirability}, journal = INTEGRATION, pages = {339-352}, year = {1991}, month = {December}, volume = {12} } @inproceedings{molitor:euroasic91, author = {G. Hotz and P. Molitor and W. Zimmer}, title = {On the construction of very large integer multipliers}, booktitle = {Proceedings of EURO ASIC 91}, pages = {266--269}, year = {1991}, month = {May} } @inproceedings{wu90, author = {H. Wu}, title = {On the construction of L$\times$n boolean matrices with all L$\times$k submatrices having $2^k$ distinct row vectors}, booktitle = {Proceedings of the 2nd European Design Automation Conference (EDAC91)}, year = {1991} } @inproceedings{ESM92, author = {Joachim Hartmann and Bj\"orn Schieffer and Uwe Sparmann}, title = {Cell Oriented Fault Simulation}, booktitle = {Proceedings of the European Simulation Multiconference 92}, pages = {424--429}, year = {1992}, postscript = {ESM92.ps.Z}, abstract = {Currently, in most fault simulators physical defects have to be modeled as stuck-at faults in networks of primitive gates such as AND, NAND etc. Especially for complex gates this modeling technique is rather inexact. In this paper, a fault simulation approach supporting a more powerful and variable fault model is presented. Specification of faults is done in a cell oriented manner. To achieve maximum flexibility, the set of basic cells and their failure modes are not coded into the algorithm but can be specified by the user in a library. For the special case of compiler driven fault simulation it is shown that this increased flexibility does not degrade the performance of the simulator but, in contrast, results in a considerable speed-up (up to factor 35).} } @inproceedings{ITG92, author = {Joachim Hartmann and Bj\"orn Schieffer and Uwe Sparmann}, title = {Zur effizienten {T}esterzeugung f\"ur sequentielle {F}ehlermodelle}, booktitle = {Tagungsband des 4.\ ITG/GI-Workshops `Testmethoden und Zuverl\"assigkeit von Schaltungen und Systemen'}, year = {1992}, postscript = {ITG92.ps.Z}, abstract = {Es wird ein allgemeiner Ansatz der Modellierung sequentieller Fehler auf seine Anwendbarkeit f\"ur Fehlersimulation und Testmustergenerierung untersucht. Zur Steigerung der Effizienz wird das Konzept der {\em blind homing sequence} vorgestellt.} } @inproceedings{bbdr:eurodac92, author = {B. Becker and R. Drechsler}, title = {A Time Optimal Robust Path-Delay-Fault Self-Testable Adder}, booktitle = {Proceedings of the 1st European Design Automation Conference (EURODAC92)}, pages = {376-381}, year = {1992}, month = {September} } @inproceedings{bbha:ila, author = {B. Becker and J. Hartmann}, title = {Some Remarks on the Test Complexity of Iterative Logic Arrays}, booktitle = {Proceedings of the 17th International Symposium on Mathematical Foundations of Computer Science}, year = {1992} } @inproceedings{bbmo:eurodac92, author = {B. Becker and P. Molitor}, title = {A performance driven generator for efficient testable adders}, booktitle = {Proceedings of the 1st European Design Automation Conference (EURODAC92)}, pages = {370-375}, year = {1992}, month = {September} } @inproceedings{drbbmo:itggi92, author = {R. Drechsler and B. Becker and P. Molitor}, title = {A Performance Oriented Generator for Robust Path-Delay-Fault Testable Adders}, booktitle = {Tagungsband des 4.\ ITG/GI-Workshops `Testmethoden und Zuverl\"assigkeit von Schaltungen und Systemen'}, year = {1992} } @inproceedings{drefenstedt:edac92, author = {R. Drefenstedt and Th. Walle}, title = {Parametric {ASIC}--Design by {CADIC}}, booktitle = {Proceedings of the $3$rd European Design Automation Conference (EDAC92)}, year = {1992} } @inproceedings{gl:edac92, author = {U. Sparmann}, title = {Derivation of High Quality Tests for Large Heterogeneous Circuits: Floating-Point Operations (Extended Abstract)}, booktitle = {Proceedings of the $3$rd European Conference on Design Automation 92}, pages = {355--360}, year = {1992} } @inproceedings{kamovo:stacs92, author = {M. Kaufmann and P. Molitor and W. Vogelgesang}, title = {Performance driven $k$-layer wiring}, booktitle = {Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS92), LNCS 577}, pages = {489--500}, year = {1992}, month = {February} } @inproceedings{marzin:neuro92, author = {R. Marzinkewitsch and others}, title = {Fast preprocessing of handprinted symbols for pattern recognition with neural networks}, booktitle = {Tagungsband der G\"ottinger Neurobiologenkonferenz}, year = {1992} } @inproceedings{sellen:conf92, author = {J. Sellen}, title = {About the topological structure of configuration spaces}, booktitle = {Proceedings of the Conference on Artificial Intelligence and Symbolic Mathematical Computations}, year = {1992}, month = {August} } @inproceedings{wu:conpar92, author = {H. Wu}, title = {On tests of uniform tree circuits}, booktitle = {Proceedings of the CONPAR'92 VAPP V Conference}, pages = {527--538}, year = {1992}, month = {September} } @inproceedings{wusp:iscis92, author = {H. Wu and U. Sparmann}, title = {On the {A}ssignment {C}omplexity of {VLSI} {T}ree Systems}, booktitle = {Proceedings of the ISCIS VII Conference}, pages = {97--104}, year = {1992}, month = {November} } @article{IEEECAD_93, author = {Bin Zhu and Xinyu Wu and Wenjun Zhuang and Wai-Kai Chen}, title = {A {N}ew {O}ne-and-{H}alf {L}ayer {C}hannel {R}outing {A}lgorithm {B}ased on {A}ssigning {R}esources for {CMOS} {G}ate {A}rray}, journal = {IEEE Trans. CAD, Vol.12, No.2}, pages = {250-264}, year = {1993}, type = {IEEECAD_93} } @inproceedings{bedrmo:eurodac93, author = {B. Becker and R. Drechsler and P. Molitor}, title = {On the implementation of an efficient performance driven generator for conditional-sum adders}, booktitle = {Proceedings of the 2nd European Design Automation Conference (EURODAC93)}, pages = {402--407}, year = {1993}, month = {September} } @inproceedings{ha:edac93, author = {J. Hartmann}, title = {On Numerical Weight Optimization for Random Testing}, booktitle = {Proceedings of the joint EDAC-EUROASIC Conference}, pages = {223--230}, year = {1993} } @inproceedings{hake:iccad93, author = {J. Hartmann and G. Kemnitz}, title = {How to do weighted random testing for {BIST}?}, booktitle = {Proceedings of the International Conference on {CAD} (ICCAD'93)}, year = {1993} } @article{hotz:searchtrees, author = {G. Hotz}, title = {Search {T}rees and {S}earch {G}raphs for {M}arkov {S}ources}, journal = EIK, pages = {283--292}, year = {1993}, volume = {29} } @inproceedings{moeller:iccad93, author = {D. Moeller and J. Mohnke}, title = {Detection of Symmetry of Boolean Functions Represented by ROBDDs}, booktitle = {Proceedings of the International Conference on {CAD} (ICCAD'93)}, year = {1993} } @inproceedings{mohnke:edac93, author = {J. Mohnke and S. Malik}, title = {Permutation and phase independent boolean comparison}, booktitle = {Proceedings of the joint EDAC-EUROASIC Conference}, year = {1993} } @article{molitor:hierarchy93, author = {P. Molitor}, title = {A hierarchy preserving hierarchical bottom-up 2-layer wiring algorithm with respect to via minimization}, journal = INTEGRATION, pages = {73--95}, year = {1993}, volume = {15} } @inproceedings{rollwage:93, author = {U. Rollwage}, title = {The Complexity of Mod-2 Sum {PLA}s for symmetric functions}, booktitle = {IFIP WG 10.5 Workshop on Applications of the Reed-Muller Expansion in Circuit Design}, year = {1993} } @inproceedings{sp:its93, author = {U. Sparmann}, title = {On the Check Base Selection Problem for Fast Adders}, booktitle = {Proceedings of the 11th IEEE VLSI Test Symposium}, pages = {62--65}, year = {1993} } @inproceedings{wu:fct93, author = {H. Wu}, title = {Synthesis of {$O(\lg n)$} {T}estable {T}rees}, booktitle = {Proceedings of the 9th International Conference on Fundamentals of Computation Theory FCT93}, pages = {452--461}, year = {1993} } @inproceedings{wu:issac93, author = {H. Wu}, title = {On the {A}ssignment {C}omplexity of {U}niform {T}rees}, booktitle = {Proceedings of the International Symposium on Symbolic and Algebraic Computation}, pages = {95--104}, year = {1993} } @inproceedings{ESM94, author = {Bj\"orn Schieffer}, title = {Fast Compiler-Driven Hierarchical Logic Simulation}, booktitle = {Proceedings of the European Simulation Multiconference 94}, pages = {991--998}, year = {1994}, postscript = {ESM94.ps.Z}, abstract = {Hierarchy can be used to make compiler-driven logic simulation available for very large circuits where the size of a flat simulation routine is too big. But due to many parameter evaluations, hierarchical simulators have an unacceptable runtime. In this paper, it is shown how to reach the performance of a flat simulator using hierarchical code but avoiding the expensive information transport with parameters.} } @inproceedings{FTCS-94-olmul, author = {U. Sparmann and S.M. Reddy}, title = {On the Effectiveness of Residue Code Checking for Parallel Two's Complement Multipliers}, booktitle = {Proceedings of the 24th International Symposium on Fault-Tolerant Computing}, year = {1994}, postscript = {FTCS-94-olmul.ps.Z}, abstract = {The effectiveness of residue code checking for on-line error detection in parallel two's complement multipliers has up to now only been evaluated experimentally for few architectures. In this paper a formal analysis is given for most of the current multiplication schemes. Based on this analysis it is shown which check bases are appropriate, and how the original scheme has to be extended for complete error detection at the input registers and Booth recoding circuitry. In addition, we argue that the hardware overhead for checking can be reduced by approximately one half if a small latency in error detection is acceptable. Schemes for structuring the checking logic in order to guarantee it to be self-testing, and thus achieve the totally self-checking goal for the overall circuit, are also derived.} } @inproceedings{MS:94b, author = {P. Molitor and C. Scholl}, title = {{C}ommunication {B}ased {M}ultilevel {S}ynthesis for {M}ulti-{O}utput {B}oolean {F}unctions}, booktitle = GLS, pages = {101--104}, year = {1994}, language = {USenglish}, postscript = {MS_94b.ps.gz} } @inproceedings{SM:94, author = {C. Scholl and P.Molitor}, title = {{E}fficient {ROBDD} {B}ased {C}omputation of {C}ommon {D}ecomposition {F}unctions of {M}ulti-{O}utput {B}oolean {F}unctions}, booktitle = {IFIP Workshop on Logic and Architecture Synthesis, Grenoble}, pages = {61--70}, year = {1994}, language = {USenglish}, postscript = {SM_94.ps.gz} } @inproceedings{SOCG94, author = {Joonsoo Choi and J{\"u}rgen Sellen and Chee Yap}, title = {Approximate Euclidean Shortest Path in 3-Space}, booktitle = {Proceedings 10th Annual ACM Symposium on Computational Geometry}, year = {1994}, postscript = {SOCG94.ps.Z} } @inproceedings{hit:itc, author = {T. Burch and J. Hartmann and G. Hotz and M. Krallmann and U. Nikolaus and S.M. Reddy and U. Sparmann}, title = {A hierarchical enviroment for interactive test engineering}, booktitle = {Proceedings of the International Test Conference 1994}, pages = {461--470}, year = {1994} } @inproceedings{hopi:lncs820, author = {G. Hotz and G. Pitsch}, title = {Fast uniform analysis of coupled context free grammars}, booktitle = {Proceedings of the 21th International Colloquium on Automata, Languages and Programing, LNCS 820}, pages = {412-423}, year = {1994}, publisher = springer } @inproceedings{hopi:porto94, author = {G. Hotz and G. Pitsch}, title = {A representation theorem for coupled context free grammars}, booktitle = {Proceedings of the International Conference on Semigroups, Automata and Languages}, pages = {88-92}, year = {1994} } @inproceedings{mospwa94, author = {P. Molitor and U. Sparmann and D. Wagner}, title = {Two-layer assignment with pin preassignment is easier if power supply is already generated}, booktitle = {Proceeding of the 7th International Conference on {VLSI} Design, Calcutta, India}, year = {1994}, month = {January} } @inproceedings{olmul:ftcs, author = {U. Sparmann and S.M. Reddy}, title = {On the effectiveness of residue code checking for parallel two's complement multipliers}, booktitle = {Proceedings of the 24th International Symposium on Fault-Tolerant Computing}, pages = {219-228}, year = {1994} } @article{pitsch:compint94, author = {G. Pitsch}, title = {{LL(k)}-parsing of coupled context free grammars}, journal = {Comput. Intelligence}, year = {1994}, volume = {10} } @article{wu:acinf94, author = {H. Wu}, title = {On $n$-column 0,1-matrices with all $k$-projections surjective}, journal = AcInf, year = {1994}, note = {to appear} } @inproceedings{CCCG95, author = {F. Follert}, title = {Maxmin Location of an Anchored ray in 3-space and Related Problems}, booktitle = {7th Canadian Conference on Computational Geometry}, pages = {??--??}, year = {1995}, month = {August}, abstract = {We consider the problem of locating a ray emanating from the origin of 3-space such as to maximize the minimum weighted Euclidean distance to a set of weighted obstacles (points, lines or line segments). We present algorithms based on the parametric search paradigm which run in $O(n \log^4 n)$ time in the case of point obstacles, and in $O(n^2 \log^2 n)$ ($O(n^2 \log^2 n \; 2^{\alpha(n)})$) time in the case of line (segment) obstacles. We also show that for practically interesting restricted settings of the line obstacle problem, subquadratic algorithms can be obtained. Furthermore we discuss some related problems.} } @inproceedings{CCCG95b, author = {E. Sch{\"o}mer and J. Sellen and M. Welsch}, title = {Exact geometric collision detection}, booktitle = {7th Canadian Conference on Computational Geometry}, pages = {211--216}, year = {1995}, month = {August}, abstract = {Exact computation is an important paradigm for the implementation of geometric algorithms. In this paper, we consider for the first time the practically important problem of collision detection under this aspect. The task is to decide whether a polyhedral object can perform a prescribed {\em sequence} of translations and rotations in the presence of stationary polyhedral obstacles. We present an exact decision method for this problem which is purely based on integer arithmetic. Our approach guarantees that the required binary length of intermediate numbers is bounded by $14L+22$, where $L$ denotes the maximal bit-size of any input value.}, postscript = {EGCD.ps.gz} } @inproceedings{CCCG95c, author = {F. Follert and E. Sch{\"o}mer and J. Sellen}, title = {Subquadratic Algorithms for the Weighted Maximin Facility Location Problem}, booktitle = {7th Canadian Conference on Computational Geometry}, pages = {1--6}, year = {1995}, month = {August}, abstract = {Let $S$ be a set of $n$ points in the plane, and let each point $p$ of $S$ have a positive weight $w(p)$. We consider the problem of positioning a point $x$ inside a compact region $R \subseteq R^2$ such that $\min \{~w(p)^{-1} \cdot d(\Bx,p)~;~p \in S~\}$ is maximized. Based on the parametric search paradigm, we give the first subquadratic algorithms for this problem, with running time $O(n \log^4 n)$. \\ Furthermore, we shall introduce the concept of `exact approximation' as the bit model counterpart to parametric search. Exploiting ideas from exact computation, we show that the considered problem can be solved in time $O(L \mu(L) n \log n)$, where $L$ denotes the maximal bit-size of input numbers, and $\mu(L)$ the complexity of multiplying two $L$-bit integers.}, postscript = {WMFLP.ps.gz} } @techreport{ECCC-AM, author = {G\"unter Hotz and Gero Vierke and B\"orn Schieffer}, title = {Analytic Machines}, institution = {Electronic Colloquium on Computational Complexity}, year = {1995}, number = {TR95-025}, postscript = {ECCC-AM.ps.Z}, abstract = {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 {\em analytic machines}. We prove that $\R$-computable functions are $\Q$-analytic. We show that $R$-machines extended by finite sets of {\em 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 {\em numerical undecidable} stability in the theory of Kolmogoroff, Arnold and Moser. \\ Keywords: $\R$-computability, stability, approximation} } @inproceedings{ICRA95-1, author = {J{\"u}rgen Sellen}, title = {Direction Weighted Shortest Path Planning}, booktitle = {Proceedings IEEE Conference on Robotics and Automation}, year = {1995}, postscript = {ICRA95-1.ps.Z} } @inproceedings{ICRA95-1a, author = {J{\"u}rgen Sellen}, title = {Planning Paths of Minimal Curvature}, booktitle = {Proceedings IEEE Conference on Robotics and Automation}, year = {1995}, postscript = {ICRA95-1.ps.Z} } @inproceedings{SCG95, author = {E. Sch{\"o}mer and C. Thiel}, title = {Efficient collision detection for moving polyhedra}, booktitle = {11th Annual Symposium on Computational Geometry}, pages = {51--60}, year = {1995}, month = {June}, abstract = {In this paper we consider the following problem: given two general polyhedra of complexity $n$, one of which is moving translationally or rotating about a fixed axis, determine the first collision (if any) between them. We present an algorithm with running time $O(n^{8/5+\epsilon})$ for the case of translational movements and running time $O(n^{5/3+\epsilon})$ for rotational movements, where $\epsilon$ is an arbitrary positive constant. This is the first known algorithm with sub-quadratic running time.}, postscript = {ECDFMP.ps.gz} } @incollection{SM:95, author = {C. Scholl and P. Molitor}, editor = {G.~Saucier and A.~Mignotte}, title = {Efficient {ROBDD} based computation of common decomposition functions of multioutput boolean functions}, booktitle = {Novel Approaches in Logic and Architecture Synthesis}, pages = {57-63}, year = {1995}, publisher = {Chapman\,\&\,Hall}, language = {USenglish}, postscript = {SM_95.ps.gz} } @inproceedings{SM:95b, author = {C. Scholl and P. Molitor}, title = {Communication {B}ased {FPGA} {S}ynthesis for {M}ulti-{O}utput {B}oolean {F}unctions}, booktitle = ASPDAC, pages = {279-287}, year = 1995, language = {USenglish}, postscript = {SM_95b.ps.gz} } @inproceedings{SOCG95, author = {Joonsoo Choi and J{"u}rgen Sellen and Chee Yap}, title = {Precision-Sensitive Euclidean Shortest Path in 3-Space}, booktitle = {Proceedings 11th Annual ACM Symposium on Computational Geometry}, year = {1995}, postscript = {SOCG95.ps.gz} } @article{ila:integration, author = {B. Becker and R. Hahn and J. Hartmann and U. Sparmann}, title = {On the testability of iterative logic arrays}, journal = INTEGRATION, pages = {201-218}, year = {1995}, month = {June}, volume = {18} } @inproceedings{rdid:dac, author = {U. Sparmann and D. Luxenburger and K.T. Cheng and S.M. Reddy}, title = {Fast Identification of Robust Dependent Path Delay Faults}, booktitle = {Proceedings of the 32nd Design Automation Conference}, pages = {119-125}, year = {1995} } @inproceedings{ATS-96, author = {U. Sparmann and H. M\"uller and S.M. Reddy}, title = {Minimal Delay Test Sets for Unate Gate Networks}, booktitle = {Proceedings of the 5th Asian Test Symposium}, year = {1996}, postscript = {ATS-96.ps.Z}, abstract = {We consider delay testing of a specific class of logic circuits, the so called `unate gate networks (UGNs)', which are of importance for the realization of dynamic CMOS logic and in the field of on-line error detection. It has been shown earlier, that UGNs can be tested completely for delay faults with `universal' test sets. This result even holds for designs which are not completely path delay testable, since the above test sets check the temporal correctness of a circuit by testing `path systems' instead of single paths. A universal test set only depends on the computed function and thus, is valid for any unate gate network implementation of this function. This universal test property has to be paid by an increase in test set size, since a design independent test set will in general be larger than a design dependent one. In this paper, we show how to tailor a universal test set to a specific design in order to reduce its size maximally without loosing test quality. Experimental results demonstrate that the resulting delay test sets are very compact, and large savings in test set size of up to $96.71 \%$ can be achieved compared to the universal test set.} } @inproceedings{CCCG96-1, author = {J. Eckstein and Th. Chadzelek and E. Sch\"omer}, title = {Heuristic Motion Planning With Movable Obstacles}, booktitle = {8th Canadian Conference on Computational Geometry}, year = {1996}, postscript = {CCCG96-1.ps.gz}, abstract = {We present a heuristic approach to geometric path planning with movable obstacle s. Treating movable obstacles as mobile robots leads to path planing problems with many degrees of freedom which are intractable. Our strategy avoids this computational complexity by decoupling the whole motion planning problem into a series of tractable problems, which are solved using kn own path planning algorithms. The individually computed solutions are then coordinated to a path plan. This method results in a powerful and practicable strategy for path planning wit h movable obstacles, which can be applied using a wide variety of known motion p lanning algorithms.} } @inproceedings{CCCG96-2, author = {Thomas Chadzelek and Jens Eckstein and Elmar Sch{\"o}mer}, title = {Heuristic Motion Planning with Many Degrees of Freedom}, booktitle = {8th Canadian Conference on Computational Geometry}, year = 1996, month = May, abstract = {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.}, postscript = {CCCG96-2.ps.gz} } @inproceedings{CEE96, author = {Bj\"orn Schieffer and G\"unter Hotz}, title = {Fault Diagnosis in Heterogeneous Complex Systems}, booktitle = {Proceedings of the 3rd International Conference On Concurrent Engineering \& Electronic Design Automation, CEE96}, year = {1996}, postscript = {CEE96.ps.Z}, abstract = {In this paper a new approach for the diagnosis problem of complex heterogeneous systems is presented. It needs no linearization of the system and allows arbitrary influences between the subsystems, while this is not the case for many approaches in literature. As a domain example, ballast tanks in offshore plants are used.} } @inproceedings{EWCG96, author = {E. Sch{\"o}mer and C. Thiel}, title = {Subquadratic algorithms for the general collision detection problem}, booktitle = {12th European Workshop on Computational Geometry}, pages = {95--101}, year = {1996}, month = {March}, abstract = {We present the first subquadratic collision detection algorithm for simultaneously moving geometric objects which works in a fairly general setting. Geometric objects are regarded as rigid bodies in $3$-space and are represented by unions of triangles (polyhedra) or unions of spheres (molecules). The motions of all objects are specified by polynomial functions which describe their position and orientation at any point in time. The general framework we develop for the solution of our specific problem is interesting of its own because it may be applicable for a wide range of other problems which require the solution of systems of polynomial (in)equalities.}, postscript = {EWCG96.ps.gz} } @inproceedings{ICALP96a, author = {Frank Schulz and Elmar Schoemer}, title = {Self-organizing data structures with dependent accesses}, booktitle = {ICALP'96}, pages = {526-537}, year = {1996}, month = {July}, postscript = {ICALP96.ps.gz}, abstract = {We consider self-organizing data structures in the case where the sequence of accesses can be modeled by a first order Markov chain. For the simple-$k$- and batched-$k$--move-to-front schemes, explicit formulae for the expected search costs are derived and compared. We use a new approach that employs the technique of expanding a Markov chain. This approach generalizes the results of Gonnet/Munro/Suwanda. In order to analyze arbitrary memory-free move-forward heuristics for linear lists, we restrict our attention to a special access sequence, thereby reducing the state space of the chain governing the behaviour of the data structure. In the case of accesses with locality (inert transition behaviour), we find that the hierarchies of self-organizing data structures with respect to the expected search time are reversed, compared with independent accesses. Finally we look at self-organizing binary trees with the move-to-root rule and compare the expected search cost with the entropy of the Markov chain of accesses.} } @inproceedings{ITC-96, author = {U. Sparmann and H. M\"uller and S.M. Reddy}, title = {Local Transformations and Robust Dependent Path Delay Faults}, booktitle = {Proceedings of the International Test Conference}, year = {1996}, postscript = {ITC-96.ps.Z}, abstract = {Local transformations are used in several synthesis approaches. During application of such transformations attention has to be paid to many important properties, e.g. area, speed, power consumption, and testability. In this paper we study relations between local transformations and delay fault testability. In delay testing it is not necessary to test every path in a circuit to ascertain correct timing behavior. For example, a set of robust dependent path delay faults need not be considered for testing if all paths that are not robust dependent are tested. We present sufficient conditions for local transformations which ensure that a test set for all non-robust-dependent paths in the original circuit is also a test set for all non-robust-dependent paths in the transformed circuit. These conditions are applied to some local transformations which are often used in logic synthesis and it is shown that they preserve testability. The impact of local transformations on robust dependent testability is demonstrated by experimental results performed on benchmark circuits.} } @article{TOVLSI-96-02, author = {U. Sparmann and S.M. Reddy}, title = {On the Effectiveness of Residue Code Checking for Parallel Two's Complement Multipliers}, journal = {IEEE Transactions on VLSI Systems}, year = {1996}, volume = {4}, number = {2}, postscript = {TOVLSI-96-02.ps.Z}, abstract = {The effectiveness of residue code checking for on-line error detection in parallel two's complement multipliers has up to now only been evaluated experimentally for few architectures. In this paper a formal analysis is given for most of the current multiplication schemes. Based on this analysis it is shown which check bases are appropriate, and how the original scheme has to be extended for complete error detection at the input registers and Booth recoding circuitry. In addition, we argue that the hardware overhead for checking can be reduced by approximately one half if a small latency in error detection is acceptable. Schemes for structuring the checking logic in order to guarantee it to be self-testing, and thus achieve the totally self-checking goal for the overall circuit, are also derived.} } @article{monot:tovlsi, author = {U. Sparmann and H. M\"uller and S.M. Reddy}, title = {Universal Delay Test Sets for Logic Networks}, journal = {to appear in: {IEEE} {T}ransactions on {VLSI} {S}ystems}, year = {1996}, note = {(Preliminary version available as technical report 5-30-94, Department of ECE, University of Iowa, Iowa City, IA 52242, USA)} } @inproceedings{SDB:97, author = {C. Scholl and R. Drechsler and B. Becker}, title = {Functional Simulation using Binary Decision Diagrams}, booktitle = {GI/ITG/GME Workshop ``Methoden des Entwurfs und der Verifikation digitaler Systeme''}, year = {1997}, language = {USenglish}, postscript = {SDB_97.ps.gz} } @inproceedings{Sch:97, author = {C. Scholl}, title = {Functional Decomposition with Integrated Test Generation}, booktitle = GIW, year = 1997, language = {USenglish}, postscript = {Sch_97.ps.gz} } @inproceedings{SMHM:97, author = {C. Scholl and St. Melchior and G. Hotz and P. Molitor}, title = {Minimizing {ROBDD} Sizes of Incompletely Specified Functions by Exploiting Strong Symmetries}, booktitle = {Proceedings of the European Design and Test Conference 1997}, month = {March}, year = {1997}, language = {USenglish}, postscript = {SMHM_97.ps.gz} } @Article{HHLMQ-OFRSH-95, author = {J. Hartmann and G. Hotz and R. Loos and R. Marzinkewitsch and J. Quapp and F. Weigel and A. Weber}, journal = {J. Symbolic Computation}, title = {The ``Optical Formula Recognition'' System for Handprinted Input}, year = 1995, language = {english}, month = {10~} # Mar, note = {}, pages = {1-8}, volume = 11, postscript = {ofrjsc.ps.gz}, } @article{CHAHO:99, author = {T. Chadzelek and G. Hotz}, title = {Analytic machines}, journal = TCS, pages = {151-167}, year = {1999}, language = {USenglish}, volume = 219, } @article{HOGAM:98, author = {G. Hotz and A. Gamkrelidze}, title = {A note on the addition of $m$ $k$-bit numbers}, year = {1998}, language = {USenglish}, postscript = {hogam_98.ps.gz}, abstract = {We give a method to construct a parallel adder of m k-bit numbers based on the school method of addition. As a result, we get a parallel adder with depth $1 log(n) + 12$ and hardware cost $k · m$. We apply our method to develop a parallel multiplier with asymptotical depth $c log n$ and hardware cost $n^2$} }