Graphenbasierte Funktionsdarstellung: Boolesche und Pseudo-Boolesche Funktionen

نمایش فشرده و دستکاری کارآمد توابع بولی یک وظیفه اصلی در بسیاری از کاربردها، به ویژه در طراحی مدار به کمک کامپیوتر است. با توجه به کاربردها، یافتن یک سازش خوب بین فشردگی و کارایی فوق الذکر بسیار جالب است. در این زمینه، نمودارهای تصمیم گیری دودویی مرتب (OBDD) که توسط برایانت در سال 1985 معرفی شد، از اهمیت ویژه ای برخوردار است: آنها همچنین به طور موفقیت آمیزی به صورت صنعتی، به ویژه در زمینه های تأیید و سنتز منطقی استفاده می شوند. با افزایش تعداد کاربردها، معایب ذاتی نیز آشکار شده و منجر به توسعه بیشتر مفهوم اساسی، به ویژه در سه سال گذشته شده است. یک خانواده کامل از نمایش های عملکردی مبتنی بر نمودار ایجاد شده است که بسته به منطقه کاربرد، مزایایی نسبت به OBDD های کلاسیک ارائه می دهد. در این کتاب طبقه‌بندی رویکردهای مختلف هم از منظر نظری و هم از دیدگاه عملی ارائه شده است. ساختارهای داده های مختلف برای توابع بولی (و عدد صحیح) ارائه شده و مزایا و معایب آنها بررسی می شود. این کتاب هم برای مبتدیان به عنوان یک ارائه مقدماتی و هم برای کاربر با تجربه طراحی شده است. کاربردهای مختلفی مورد بحث قرار می گیرد و به خواننده درک عمیق تری از موضوع می دهد. \"... مونوگراف به خوبی نوشته شده است و خواننده مقدمه خوبی با موضوع پیدا می کند.\" I.Wegener. آمار و تصمیمات، مونیخ

Kompakte Darstellung und effiziente Manipulation Boolescher Funktionen ist in vielen Anwendungen, insbesondere des computergestützten Schaltkreisentwurfes, eine zentrale Aufgabe. Im Hinblick auf Anwendungen ist es dabei von großem Interesse, einen guten Kompromiß zwischen oben angesprochener Kompaktheit und Effizienz zu finden. Besonderes Interesse finden in diesem Zusammenhang die von Bryant 1985 eingeführten Ordered Binary Decision Diagrams (OBDDs): Sie werden insbesondere in den Bereichen Verifikation und Logiksynthese auch industriell erfolgreich eingesetzt. Mit wachsender Zahl von Anwendungen sind auch inhärente Nachteile sichtbar geworden und haben insbesondere in den letzten drei Jahren zu Weiterentwicklungen des Basiskonzeptes geführt. Dabei hat sich eine ganze Familie von graphenbasierten Funktionsdarstellungen entwickelt, die je nach Anwendungsgebiet Vorteile gegenüber den klassischen OBDDs bieten. In diesem Buch wird eine Klassifizierung der verschiedenen Ansätze sowohl aus theoretischer wie auch praktischer Sicht gegeben. Es werden diverse Datenstrukturen für Boolesche (und ganzzahlige) Funktionen vorgestellt und deren Vor- und Nachteile untersucht. Das Buch wendet sich sowohl an den Einsteiger als einführende Darstellung als auch an den erfahrenen Benutzer. Es werden verschiedene Anwendungen diskutiert, die dem Leser ein tieferes Verständnis der Materie ermöglichen. "... The monograph is well written and the reader gets a good introduction into the subject." I.Wegener. Statistics & Decisions, München