Abstract interpretation over non-deterministic finite tree automate for set-based analysis of logic programs

    Research output: Chapter in Book/Report/Conference proceedingBook chapterResearch

    Abstract

    Set-based program analysis has many potential applications, including compiler optimisations, type-checking, debugging, verification and planning. One method of set-based analysis is to solve a set of {\it set constraints} derived directly from the program text. Another approach is based on abstract interpretation (with widening) over an infinite-height domain of regular types. Up till now only deterministic types have been used in abstract interpretations, whereas solving set constraints yields non-deterministic types, which are more precise. It was pointed out by Cousot and Cousot that set constraint analysis of a particular program $P$ could be understood as an abstract interpretation over a finite domain of regular tree grammars, constructed from $P$. In this paper we define such an abstract interpretation for logic programs, formulated over a domain of non-deterministic finite tree automata, and describe its implementation. Both goal-dependent and goal-independent analysis are considered. Variations on the abstract domains operations are introduced, and we discuss the associated tradeoffs of precision and complexity. The experimental results indicate that this approach is a practical way of achieving the precision of set-constraints in the abstract interpretation framework.
    Original languageEnglish
    Title of host publicationPractical aspects of declarative languages, 4th International Symposium, PADL 2002 : Portland, OR, USA
    EditorsShriram Krishnamurthi, C.R. Ramakrishnan
    PublisherSpringer
    Publication date2002
    Pages243-261
    Publication statusPublished - 2002
    SeriesLecture Notes in Computer Science
    Volume2257
    ISSN0302-9743

    Cite this

    Gallagher, J. P., & Puebla, G. (2002). Abstract interpretation over non-deterministic finite tree automate for set-based analysis of logic programs. In S. Krishnamurthi, & C. R. Ramakrishnan (Eds.), Practical aspects of declarative languages, 4th International Symposium, PADL 2002: Portland, OR, USA (pp. 243-261). Springer. Lecture Notes in Computer Science, Vol.. 2257