Christoph Meinel, Thorsten Theobald

Algorithms and Data Structures in VLSI Design (eBook, PDF)

OBDD - Foundations and Applications

• Format: PDF

Produktbeschreibung

One of the main problems in chip design is the huge number of possible combinations of individual chip elements, leading to a combinatorial explosion as chips become more complex. New key results in theoretical computer science and in the design of data structures and efficient algorithms can be applied fruitfully here. The application of ordered binary decision diagrams (OBDDs) has led to dramatic performance improvements in many computer-aided design projects. This textbook provides an introduction to the foundations of this interdisciplinary research area with an emphasis on applications in computer-aided circuit design and formal verification.

---

Dieser Download kann aus rechtlichen Gründen nur mit Rechnungsadresse in A, B, BG, CY, CZ, D, DK, EW, E, FIN, F, GR, HR, H, IRL, I, LT, L, LR, M, NL, PL, P, R, S, SLO, SK ausgeliefert werden.

Produktdetails

• Verlag: Springer Berlin Heidelberg
• Seitenzahl: 268
• Erscheinungstermin: 6. Dezember 2012
• Englisch
• ISBN-13: 9783642589409
• Artikelnr.: 53397005

Autorenporträt

Dr. sc. nat. Christoph Meinel (1954) ist Direktor und Geschäftsführer des Hasso-Plattner-Instituts für Softwaresystemtechnik GmbH (HPI) und ordentlicher Professor (C4) für Internet-Technologien und Systeme. Er hat Mathematik und Informatik an der Humboldt-Universität in Berlin studiert, dort 1981 promoviert und sich 1988 an der Akademie der Wissenschaften in Berlin habilitiert. Er wurde 1992 zum ordentlichen Professor (C4) für Informatik an die Univ. Trier berufen und hat dort in den Jahren 1998-2002 neben seinem Lehrstuhl das von der Fraunhofer-Gesellschaft betreute Institut für Telematik e.V. geleitet. Seit 2004 ist er Direktor und Geschäftsführer des HPIs und hat einen Lehrstuhl (C4) für Internet-Technologien und Systeme an der Universität Potsdam. Neben seiner Lehrtätigkeit in Potsdam ist er Gastprofessor an der Univ. Luxembourg (Luxembourg) und an der TU Peking (China) und als Programmdirektor des HPI-Stanford Forschungsprogramms zum Design Thinking Research tätig. Christoph

Meinel ist Autor bzw. Co-Autor und Inhaber internationaler Patente. Seine aktuellen Forschungsinteressen liegen in den Bereichen IT-Sicherheit, Teleteaching, Semantic/Social Web und e-Health. Er war wissenschaftlich aktiv auch auf dem Gebiet der Komplexitätstheorie und hat (BDD-basierte) Datenstrukturen und effiziente Algorithmen untersucht und entworfen. Er ist Chairman des 2007 gegründeten deutschen IPv6-Rats, Herausgeber von ECCC - Electronic Colloquiums on Computational Complexity, des IT-Gipfelblog und des tele-TASK-Archivs. 1996-2007 gehörte er dem Direktorium des IBFI Schloss Dagstuhl an und war Sprecher der GI-Fachgruppe 'Komplexität'. Er hat in einer großen Zahl internationaler Programm-Komitees mitgewirkt, diverse Konferenzen und Symposien veranstaltet und ist in wissenschaftlichen Aufsichtsräten aktiv.

Inhaltsangabe

1. Introduction.- 2. Basics.- 2.1 Propositions and Predicates.- 2.2 Sets, Relations, and Functions.- 2.3 Graphs.- 2.4 Algorithms and Data Structures.- 2.5 Complexity of Algorithms.- 2.6 Hashing.- 2.7 Finite Automata and Finite State Machines.- 2.8 References.- I. Data Structures for Switching Functions.- 3. Boolean Functions.- 4. Classical Representations.- 5. Requirements on Data Structures in Formal Circuit Verification.- II. OBDDs: An Efficient Data Structure.- 6. OBDDs - Ordered Binary Decision Diagrams.- 7. Efficient Implementation of OBDDs.- 8. Influence of the Variable Order on the Complexity of OBDDs.- 9. Optimizing the Variable Order.- III. Applications and Extensions.- 10. Analysis of Sequential Systems.- 11. Symbolic Model Checking.- 12. Variants and Extensions of OBDDs.- 13. Transformation Techniques for Optimization.