Logic program synthesis as problem reduction using combining forms

Jørgen Fischer Nilsson, Andreas Hamfelt, Steen Nikolaj Oldager

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    This paper presents an approach to inductive synthesis of logic programs from examples using problem decomposition and problem reduction principles. This is in contrast to the prevailing logic program induction paradigm, which relies on generalization of programs from examples. The problem reduction is accomplished as a constrained top-down search process, which eventually is to reach trivial problems. Our induction scheme applies a distinguished logic programming language in which programs are combined from elementary predicates by means of combinators conceived of as problem reduction operators including list recursion forms. The operator form admits inductive synthesis as a top-down piecewise composition of semantically meaningful program elements according to the compositional semantics principle and with appeals neither to special generalization mechanisms nor to alternative forms of resolution and unification, or predicate invention. The search space is reduced by subjecting the induction process to various constraints concerning syntactical form, modes, data types, and computational resources. This is illustrated in the paper with well-modedness constraints with the aim of synthesising well-moded, procedurally acceptable programs. Preliminary experiments with the proposed induction method lead us to tentatively conclude that the presented approach forms a viable alternative to the prevailing inductive logic programming methods applying generalization from examples.
    Original languageEnglish
    JournalAutomated Software Engineering
    Volume8
    Issue number2
    Pages (from-to)167-193
    ISSN0928-8910
    DOIs
    Publication statusPublished - 2001

    Fingerprint

    Dive into the research topics of 'Logic program synthesis as problem reduction using combining forms'. Together they form a unique fingerprint.

    Cite this