Howe, Jacob M., King, Andy (2001) Widening BDDs. University of Kent, School of Computing, 9 pp. (KAR id:13611)
PDF
Language: English |
|
Download this file (PDF/200kB) |
Preview |
Request a format suitable for use with assistive technology e.g. a screenreader |
Abstract
Boolean functions are often represented as binary decision diagrams (BDDs). BDDs are potentially of exponential size in the number of variables of the function. Boolean functions drawn from Pos (the class of positive Boolean functions) and Def (the class of definite Boolean functions) are often used to describe the groundness of, and grounding dependencies between, program variables in (constraint) logic programs. mypos-based analyses are often implemented using BDDs which are sometimes problematically large. Since the complexities of the most frequently used domain operations are quadratic in the size of the input BDDs, widening BDDs for space is also a widening for time, hence is important for scalability. Two algorithms for widening BDDs for space are presented and are discussed (with relation to groundness analysis).
Item Type: | Research report (external) |
---|---|
Subjects: | Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, |
Divisions: | Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing |
Depositing User: | Andy King |
Date Deposited: | 24 Nov 2008 17:59 UTC |
Last Modified: | 05 Nov 2024 09:47 UTC |
Resource URI: | https://kar.kent.ac.uk/id/eprint/13611 (The current URI for this page, for reference purposes) |
- Link to SensusAccess
- Export to:
- RefWorks
- EPrints3 XML
- BibTeX
- CSV
- Depositors only (login required):