Conference Proceedings

Boolean functions for dependency analysis: Algebraic properties and efficient representation

T Armstrong, K Marriott, P Schachte, H Søndergaard

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Published : 1994


Many analyses for logic programming languages use Boolean functions to express dependencies between variables or argument positions. Examples include groundness analysis, arguably the most important analysis for logic programs, finiteness analysis and functional dependency analysis. 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. We provide syntactic characterizations and study their algebraic properties. In particular, we show that both classes are closed under existential quantification. We investigate representations for these class..

View full abstract