Exact OBDD Bounds for Some Fundamental Functions.
Saved in:
| Title: | Exact OBDD Bounds for Some Fundamental Functions. |
|---|---|
| Authors: | Bollig, Beate1 beate.bollig@uni-dortmund.de, Range, Niko1 niko@range.at, Wegener, Ingo |
| Source: | Theory of Computing Systems. Aug2010, Vol. 47 Issue 2, p593-609. 17p. 2 Diagrams, 19 Charts. |
| Subjects: | Computational complexity, Dynamic data exchange, Data transmission systems, Boolean algebra, Graphic methods, Computer-aided design, Relation algebras |
| Abstract: | Ordered binary decision diagrams (OBDDs) are nowadays one of the most common dynamic data structures or representation types for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many exponential lower bounds on the OBDD size of Boolean functions are known, there are only few functions where the OBDD size is asymptotically known exactly. In this paper the exact OBDD sizes of the fundamental functions multiplexer and addition of n-bit numbers are determined. [ABSTRACT FROM AUTHOR] |
| Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) | |
| Database: | Engineering Source |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 50808883 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Exact OBDD Bounds for Some Fundamental Functions. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Bollig%2C+Beate%22">Bollig, Beate</searchLink><relatesTo>1</relatesTo><i> beate.bollig@uni-dortmund.de</i><br /><searchLink fieldCode="AR" term="%22Range%2C+Niko%22">Range, Niko</searchLink><relatesTo>1</relatesTo><i> niko@range.at</i><br /><searchLink fieldCode="AR" term="%22Wegener%2C+Ingo%22">Wegener, Ingo</searchLink> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Theory+of+Computing+Systems%22">Theory of Computing Systems</searchLink>. Aug2010, Vol. 47 Issue 2, p593-609. 17p. 2 Diagrams, 19 Charts. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Dynamic+data+exchange%22">Dynamic data exchange</searchLink><br /><searchLink fieldCode="DE" term="%22Data+transmission+systems%22">Data transmission systems</searchLink><br /><searchLink fieldCode="DE" term="%22Boolean+algebra%22">Boolean algebra</searchLink><br /><searchLink fieldCode="DE" term="%22Graphic+methods%22">Graphic methods</searchLink><br /><searchLink fieldCode="DE" term="%22Computer-aided+design%22">Computer-aided design</searchLink><br /><searchLink fieldCode="DE" term="%22Relation+algebras%22">Relation algebras</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: Ordered binary decision diagrams (OBDDs) are nowadays one of the most common dynamic data structures or representation types for Boolean functions. Among the many areas of application are verification, model checking, computer aided design, relational algebra, and symbolic graph algorithms. Although many exponential lower bounds on the OBDD size of Boolean functions are known, there are only few functions where the OBDD size is asymptotically known exactly. In this paper the exact OBDD sizes of the fundamental functions multiplexer and addition of n-bit numbers are determined. [ABSTRACT FROM AUTHOR] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>Copyright of Theory of Computing Systems is the property of Springer Nature and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=50808883 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.1007/s00224-009-9217-3 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 17 StartPage: 593 Subjects: – SubjectFull: Computational complexity Type: general – SubjectFull: Dynamic data exchange Type: general – SubjectFull: Data transmission systems Type: general – SubjectFull: Boolean algebra Type: general – SubjectFull: Graphic methods Type: general – SubjectFull: Computer-aided design Type: general – SubjectFull: Relation algebras Type: general Titles: – TitleFull: Exact OBDD Bounds for Some Fundamental Functions. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Bollig, Beate – PersonEntity: Name: NameFull: Range, Niko – PersonEntity: Name: NameFull: Wegener, Ingo IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Text: Aug2010 Type: published Y: 2010 Identifiers: – Type: issn-print Value: 14324350 Numbering: – Type: volume Value: 47 – Type: issue Value: 2 Titles: – TitleFull: Theory of Computing Systems Type: main |
| ResultId | 1 |
