On structural analysis of non-ground answer-set programs - (:unkn) unknown (CEUR-WS, 2015)
The development of answer-set programs often involves domain experts without a background in logic programming. In such situations, it would be beneficial to translate programs into a form which is easier to understand and closer to natural language. Since the structure of a program determines to a great extent how a program should be explained in a clear and comprehensible way, as a first step towards a natural-language representation of answer-set programs, in this paper, we introduce methods for analysing the structure of disjunctive non-ground answer-set programs. In particular, as most programs follow the generate-define-test paradigm, we introduce formal definitions to characterise the respective generate, define, and test parts of a program. Thereby, we define the non-deterministic core of a program, effectively determining the program's active solution-space generators, following ideas of the weakly perfect model semantics as introduced by Przymusinska and Przymusinski, and we prove that our definitions fulfil desirable properties. Moreover, we also provide an implementation of a tool, using a metaprogramming approach, which classifies the rules of a given program according to our definitions. Finally, we propose an algorithm that, based on our generate-define-test classification, computes the order in which the rules of a program should be explained when translated into natural language.
Keywords: Answer-set programming; Generate-define-test paradigm; Program analysis