City Research Online

Positive Boolean Functions as Multiheaded Clauses

Howe, J. M. & King, A. (2001). Positive Boolean Functions as Multiheaded Clauses. In: Codognet, P (Ed.), LNCS. International Conference on Logic Programming, 26 Nov - 01 Dec 2001, Cyprus.

Abstract

Boolean functions are ubiquitous in the analysis of (constraint) logic programs. The domain of positive Boolean functions, Pos, has been used for expressing, for example, groundness, finiteness and sharing dependencies. The performance of an analyser based on Boolean functions is critically dependent on the way in which the functions are represented. This paper discusses multiheaded clauses as a representation of positive Boolean functions. The domain operations for multiheaded clauses are conceptually simple and can be implemented straightforwardly in Prolog. Moreover these operations generalise those for the less algorithmically complex operations of propositional Horn clauses, leading to naturally stratified algorithms. The multiheaded clause representation is used to build a Pos-based groundness analyser. The analyser performs surprisingly well and scales smoothly, not requiring widening to analyse any program in the benchmark suite.

Publication Type: Conference or Workshop Item (Paper)
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
[thumbnail of Positive_Boolean_Functions_as_Multiheaded_Clauses.pdf]
Preview
PDF
Download (225kB) | Preview

Export

Add to AnyAdd to TwitterAdd to FacebookAdd to LinkedinAdd to PinterestAdd to Email

Downloads

Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login