Name
Abstract | ||
|---|---|---|
Many static analyses for declarative programming/database languages use Boolean functions to express dependencies among variables or argument positions. Examples include groundness analysis, arguably the most important analysis for logic programs, finiteness analysis and functional dependency analysis for databases. We identify two classes of Boolean functions that have been used: positive and definite functions, and we systematically investigate these classes and their efficient implementation for dependency analyses. On the theoretical side, we provide syntactic characterizations and study the expressiveness and algebraic properties of the classes. In particular, we show that both are closed under existential quantification. On the practical side, we investigate various representations for the classes based on reduced ordered binary decision diagrams (ROBDDs), disjunctive normal form, conjunctive normal form, Blake canonical form, dual Blake canonical form, and a form specific to definite functions. We compare the resulting implementations of groundness analyzers based on the representations for precision and efficiency. |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1016/S0167-6423(96)00039-1 | Sci. Comput. Program. |
Keywords | Field | DocType |
boolean function,dependency analysis,dependence analysis,declarative programming,disjunctive normal form,functional dependency,canonical form,conjunctive normal form | Boolean function,Functional programming,Computer science,Binary decision diagram,Disjunctive normal form,Theoretical computer science,Functional dependency,Canonical form,Conjunctive normal form,Blake canonical form | Journal |
Volume | Issue | ISSN |
31 | 1 | Science of Computer Programming |
Citations | PageRank | References |
65 | 2.00 | 30 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Tania Armstrong | 1 | 98 | 3.38 |
| Kim Marriott | 2 | 452 | 37.84 |
| Peter Schachte | 3 | 256 | 22.76 |
| Harald Søndergaard | 4 | 858 | 79.52 |