Wyniki wyszukiwania - BazTech

1

A Schema for Generating Relevant Logic Programming Semantics and its Applications in Argumentation Theory

Nieves J.C., Osorio M., Zepeda C.

Fundamenta Informaticae

|

2011

|

Vol. 106, nr 2-4

295-311

EN

In the literature, there are several approaches which try to perform common sense reasoning. Among them, the approaches which have probably received the most attention the last two decades are the approaches based on logic programming semantics with negation as failure and argumentation theory. Even though both approaches have their own features, it seems that they share some common behaviours which can be studied by considering the close relationship between logic programming semantics and extension-based argumentation semantics. In this paper, we will present a general recursive schema for defining new logic programming semantics. This schema takes as input any basic logic programming semantics, such as the stable model semantics, and gives as output a new logic programming semantics which satisfies some desired properties such as relevance and the existence of the intended models for every normal program. We will see that these new logic programming semantics can define candidate extension-based argumentation semantics. These new argumentation semantics will overcome some of the weakness of the extension-based argumentation semantics based on admissible sets. In fact, we will see that some of these new argumentation semantics have similar behaviour to the extension-based argumentation semantics built in terms of strongly connected components.

2

GASP: Answer Set Programming with Lazy Grounding

Dal Palu A., Dovier A., Pontelli E., Rossi G.

Fundamenta Informaticae

|

2009

|

Vol. 96, nr 3

297-322

EN

In recent years, Answer Set Programming has gained popularity as a viable paradigm for applications in knowledge representation and reasoning. This paper presents a novel methodology to compute answer sets of an answer set program. The proposed methodology maintains a bottom-up approach to the computation of answer sets (as in existing systems), but it makes use of a novel structuring of the computation, that originates from the non-ground version of the program. Grounding is lazily performed during the computation of the answer sets. The implementation has been realized using Constraint Logic Programming over finite domains.

3

A General Similarity Framework for Horn Clause Logic

Ferilli S., Basile T.M.A., Biba M., Di Mauro N., Esposito F.

Fundamenta Informaticae

|

2009

|

Vol. 90, nr 1-2

43-66

EN

First-Order Logic formulć are a powerful representation formalism characterized by the use of relations, that cause serious computational problems due to the phenomenon of indeterminacy (various portions of one description are possibly mapped in different ways onto another description). Being able to identify the correct corresponding parts of two descriptions would help to tackle the problem: hence, the need for a framework for the comparison and similarity assessment. This could have many applications in Artificial Intelligence: guiding subsumption procedures and theory revision systems, implementing flexible matching, supporting instance-based learning and conceptual clustering. Unfortunately, few works on this subject are available in the literature. This paper focuses on Horn clauses, which are the basis for the Logic Programming paradigm, and proposes a novel similarity formula and evaluation criteria for identifying the descriptions components that are more similar and hence more likely to correspond to each other, based only on their syntactic structure. Experiments on real-world datasets prove the effectiveness of the proposal, and the efficiency of the corresponding implementation in the above tasks.

4

Predicate Introduction for Logics with a Fixpoint Semantics. Part I: Logic Programming

Vennekens J., Wittocx J., Mariën M., Denecker M.

Fundamenta Informaticae

|

2007

|

Vol. 79, nr 1-2

187-208

EN

We study the transformation of "predicate introduction" in non-monotonic logics. By this, we mean the act of replacing a complex formula by a newly defined predicate. From a knowledge representation perspective, such transformations can be used to eliminate redundancy or to simplify a theory. From a more practical point of view, they can also be used to transform a theory into a normal form imposed by certain inference programs or theorems. In this paper, we study predicate introduction in the algebraic framework of "approximation theory"; this is a fixpoint theory for non-monotone operators that generalizes all main semantics of various non-monotonic logics, including logic programming, default logic and autoepistemic logic. We prove an abstract, algebraic equivalence result in this framework. This can then be used to show that, in logic programming, certain transformations are equivalence preserving under, among others, both the stable and well-founded semantics. Based on this result, we develop a general method of eliminating universal quantifiers in the bodies of rules. Our work is, however, also applicable beyond logic programming. In a companion paper, we demonstrate this, by using the same algebraic results to derive a transformation which reduces the nesting depth of the modal operator K in autoepistemic logic.

5

Logic Programming Representation of the Compound Term Composition Algebra

Analyti A., Pachoulakis I.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 3

321-360

EN

The Compound Term Composition Algebra (CTCA) is an algebra with four algebraic operators, which can be used to generate the valid (meaningful) compound terms of a given faceted taxonomy, in an efficient and flexible manner. The positive operations allow the derivation of valid compound terms through the declaration of a small set of valid compound terms. The negative operations allow the derivation of valid compound terms through the declaration of a small set of invalid compound terms. In this paper, we show how CTCA can be represented in logic programming with negation-as-failure, according to both Clark's and well-founded semantics. Indeed, the SLDNF-resolution can be used for checking compound term validity and well-formedness of an algebraic expression in polynomial time w.r.t. the size of the expression and the number of terms in the taxonomy. This result makes our logic programming representation a competitive alternative to imperative algorithms. Embedding of our logic programming representation to the programming environment of a web portal for a computer sales company is demonstrated.

6

Control Generation by Program Transformation

King A., Martin J.C.

Fundamenta Informaticae

|

2006

|

Vol. 69, nr 1,2

179-218

EN

The objective of control generation in logic programming is to derive a computation rule for a program that is efficient and yet does not compromise program correctness. Progress in solving this fundamental problem in logic programming has been slow and, to date, only partial solutions have been proposed. Previously proposed schemes are either inefficient, incomplete (incorrect) or difficult to apply for programs consisting of many components (the scheme is not modular). This paper shows how the control generation problem can be tackled by program transformation. The transformation relies on information about the depths of derivations to derive delay declarations which orchestrate the control. To prove correctness of the transformation, the notion of semi-delay recurrency is introduced, which generalises previous ideas in the termination literature for reasoning about logic programs with delay declarations. In contrast to previous work, semi-delay recurrency does not require an atom to be completely resolved before another is selected for reduction. This enhancement permits the transformation to introduce control which is flexible and relatively efficient.

7

A Value-propagating Transformation Technique for Datalog Programs Based on Non-Deterministic Constructs

Potikas P., Rondogiannis P., Gergatsoulis M.

Fundamenta Informaticae

|

2006

|

Vol. 72, nr 4

485-527

EN

The branching-time transformation is a recent technique for optimizing Chain Datalog programs. In this paper we propose a significant extension of the branching-time transformation which we believe opens up a promising new direction of research in the area of value-propagating Datalog optimizations. More specifically, the proposed transformation can handle more general programs that allow multiple consumptive occurrences of variables in the bodies of clauses. This extension is achieved by using as target language the temporal logic programming formalism DatalognS enriched with choice predicates (a non-deterministic construct that was originally introduced in the area of intensional logic programming). We demonstrate the correctness of the transformation and propose several optimizations that can be applied to the target code. Moreover, we define a bottom-up proof procedure that applies to the target programs and demonstrate that it always terminates (despite the fact that the Herbrand base of these programs is generally infinite).

8

On the complexity of perfect models of logic programs

Dudakov S.

Fundamenta Informaticae

|

1999

|

Vol. 39, Nr 3

249-258

EN

In this paper we investigate computational complexity of the PERF-consistency and PERF-entailment problems for ground normal logic programs. In [3] it is proved that these problems belong to [Sigma]2P and Pi2P correspondingly. The question of obtaining more accurate results was left as open. We prove that both problems belong to [Delta]2P. Lower bounds on the complexity of these problems are also established in terms of a new complexity class D2 which is a subset of[Delta]2P. It is shown that PERF-consistency is a D2-complete problem and PERF-entailment is co-D2-complete

9

Executing suspended logic programs

Kowalski R. A., Toni F., Wetzel G.

Fundamenta Informaticae

|

1998

|

Vol. 34, nr 3

203-224

EN

We present an extension of Logic Programming (LP) which, in addition to ordinary LP clauses, also includes integrity constraints, explicit representation of disjunction in the bodies of clauses and in goals, and suspension of atoms as in concurrent logic languages. The resulting framework aims to unify Constraint Logic Programming (CLP), Abductive Logic Programming (ALP) and Semantic Query Optimisation (SQO) in deductive databases. We present a proof procedure for the new framework, simplifying and generalising previously proposed proof procedures for ALP. We discuss applications of the framework, formulating traditional problems from LP, ALP, CLP and SQO.