Wyniki wyszukiwania - BazTech

1

A Knowledge Representation Framework Based on Epistemic Logic

Przymusiński T.

Zeszyty Naukowe Warszawskiej Wyższej Szkoły Informatyki

|

2014

|

nr 11

41--53

EN

We introduce a uniform non-monotonic framework for knowledge representation based on epistemic logic which is sufficiently general to encompass several nonmonotonic formalisms, including circumscription, autoepistemic logic, various semantics proposed for logic programs and deductive databases (stable semantics, well-founded semantics and stationary semantics) as well as Gelfond’s epistemic specifications. The existence of such a uniform framework allows us not only to provide simpler and perhaps more natural definitions of various formalisms but it also enables us to better understand mutual relationships existing between them.

2

Nested Weight Constraints in ASP

Costantini S., Formisano A.

Fundamenta Informaticae

|

2013

|

Vol. 124, nr 4

449--464

EN

Weight constraints are a powerful programming construct that has proved very useful within the Answer Set Programming paradigm. In this paper, we argue that practical Answer Set Programming might take profit from introducing some forms of nested weight constraints. We define such empowered constraints (that we call 'Nested Weight Constraints') and discuss their semantics and their complexity.

3

Look-back Techniques for ASP Programs with Aggregates

Faber W., Leone N., Maratea M., Ricca F.

Fundamenta Informaticae

|

2011

|

Vol. 107, nr 4

379-413

EN

The introduction of aggregates has been one of the most relevant language extensions to Answer Set Programming (ASP). Aggregates are very expressive, they allow to represent many problems in a more succinct and elegant way compared to aggregate-free programs. A significant amount of research work has been devoted to aggregates in the ASP community in the last years, and relevant research results on ASP with aggregates have been published, on both theoretical and practical sides. The high expressiveness of aggregates (eliminating aggregates often causes a quadratic blow-up in program size) requires suitable evaluation methods and optimization techniques for an efficient implementation. Nevertheless, in spite of the above-mentioned research developments, aggregates are treated in a quite straightforward way in most ASP systems. In this paper, we explore the exploitation of look-back techniques for an efficient implementation of aggregates. We define a reason calculus for backjumping in ASP programs with aggregates. Furthermore, we describe how these reasons can be used in order to guide look-back heuristics for programs with aggregates. We have implemented both the new reason calculus and the proposed heuristics in the DLV system, and have carried out an experimental analysis on publicly available benchmarks which shows significant performance benefits

4

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.

5

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.

6

Pruning Operators for Disjunctive Logic Programming Systems

Calimeri F., Faber W., Pfeifer G., Leone N.

Fundamenta Informaticae

|

2006

|

Vol. 71, nr 2,3

183-214

EN

Disjunctive Logic Programming (DLP) is an advanced formalism for knowledge representation and reasoning. The language of DLP is very expressive and supports the representation of problems of high computational complexity (specifically, all problems in the complexity class \SigmaP2 = \NP\NP). The DLP encoding of a large variety of problems is often very concise, simple, and elegant. In this paper, we explain the computational process commonly performed by DLP systems, with a focus on search space pruning, which is crucial for the efficiency of such systems. We present two suitable operators for pruning (Fitting's and Well-founded), discuss their peculiarities and differences with respect to efficiency and effectiveness. We design an intelligent strategy for combining the two operators, exploiting the advantages of both. We implement our approach in DLV - the state-of-the-art DLP system - and perform some experiments. These experiments show interesting results, and evidence how the choice of the pruning operator affects the performance of DLP systems.

7

Weaker Axioms, More Ranges

Koutras C.D., Peppas P.

Fundamenta Informaticae

|

2002

|

Vol. 51, nr 3

297-310

EN

In the family of many-valued modal languages proposed by M. Fitting in 1992, every modal language is based on an underlying Heyting algebra which provides the space of truth values. The lattice of truth values is explicitly represented in the language by a set of special constants and this allows for forming weak, generalized, many-valued analogs of all classical modal axioms. Weak axioms of this kind have been recently investigated from the canonicity, completeness and correspondence perspective. In this paper, we provide some results on the effect of adopting weak versions of the axioms D, T, 4, 5 and w5 in the family of many-valued modal non-monotonic logics, a` la McDermott and Doyle. For many-valued modal languages built on finite chains, we extend the results by proving two quite general range theorems. We then hint on the relation between the modal non-monotonic logics obtained: we prove that there exist ranges which selectively pick out some of the expansions produced by the many-valued autoepistemic logics, actually the ones with a confidence-bounded set of beliefs. However, an exact characterization of the relation between the various ranges created by the weak many-valued modal axioms still remains to be explored.

8

Changing and using beliefs under incomplete information

Jamroga W.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2001

|

Nr 928

31-36

EN

The concept being proposed here is to use prototype semantics to represent an agent's belief state. Prototype semantics is a linguistic theory that emerged in the 1980s - the key idea is to describe the meaning of an utterance, or a notion, by defining the prototype (the most typical example to which the notion refers) and the extension rules describing 'family resemblances' between various entities and, in consequence, allowing to derive less typical instances from more typical ones. The intuition behind this paper is that in situations of incomplete information such a representation of the agent's knowledge may be easier to deal with than a straightforward probabilistic representation - especially when belief changes are not necessarily monotonic, and informations being acquired by the agent may be vague themselves. Moreover, when an exhaustive search through all the possibilities is impossible the agent may benefit from analyzing the typical situations instead of random ones. This property was tested for a family of games with incomplete information on binary trees.

9

Complementary reasoning for geographic map image understanding

Stąpor K.

Archiwum Informatyki Teoretycznej i Stosowanej

|

2000

|

T. 12, z. 2

121-139

EN

This paper presents the logical foundations of the proposed non-monotonic reasoning method for geographic map image understanding, called complementary reasoning which is a part of the general reasoning framework for knowledge-based geographic map image analysis proposed in [19]. The logical framework of the complementary reasoning is based on the modified Poole's approach to nonmonotonic reasoning. Due to the process of active hypothesis generation based on a map (domain) model, the complementary reasoning can be initiated at any time based on the incomplete information thus far obtained, and the description of the map can be constructed even if some information is missing.

PL

W artykule przedstawiono logiczne podstawy wnioskowania niemonotonicznego, zwanego wnioskowaniem uzupełniającym, dla automatycznego rozumienia map geograficznych. Opracowana metoda wnioskowania uzupełniającego stanowi część zaproponowanego w [19], opartego o wiedzę środowiska dla automatycznej analizy map geograficznych, na które składają się: model mapy, metody detekcji obiektów geograficznych oraz schemat analizy obrazu, który z kolei składa sięz mechanizmu kontroli i metody wnioskowania. Logiczne podstawy wnioskowania uzupełniającego są oparte na zmodyfikowanej metodzie Poole'a. Główne modyfikacje polegają na wprowadzeniu zmiany w badaniu spójności oraz dynamicznej generacji faktów w trakcie procesu rozumowania. W metodzie wnioskowania uzupełniającego akumulowane są spójne zbiory obiektów oraz hipotez jako wyjaśnienia relacji między obiektami (relacje te stanowią ich logiczne konsekwencje).

10

Many-valued modal non-monotonic reasoning: sequential stable sets and logics with linear truth spaces

Koutras C.D., Koletsos G., Zachos S.

Fundamenta Informaticae

|

1999

|

Vol. 38, Nr 3

281-324

EN

A family of many-valued modal logics which correspond to possible-worlds models with many-valued accessibility relations, has been recently proposed by M. Fitting. Non-monotonic extensions of these logics are introduced with a fixpoint construction a la McDermott & Doyle and employ sequential belief sets as epistemic states. In this paper we take a logical investigation of many-valued modal non-monotonic reasoning in Fitting's formal framework. We examine the notion of MV-stable sets which emerges as a sequential many-valued analog of Stalnaker-Moore stable sets and prove that several attractive epistemic properties are essentially retained in the many-valued setting, esp. when focusing on a syntactically simple epistemic fragment of MV-stable sets. We show that MV-stable sets are always closed under S4 consequence and identify three sufficient conditions for capturing axioms of negative introspection. Also, the relation of MV-stable sets to many-valued analogs of classical S5 models and to many-valued extensions of universal models is discussed. Finally, we pay special attention to the subclass of logics built on linear Heyting algebras and show that inside this subclass, the situation is very similar - in many respects - to the machinery devised by W. Marek, G. Schwarz and M. Truszczyński. In particular, the normal fragments of the two important classical ranges of modal non-monotonic logics remain intact: many-valued autoepistemic logic is captured by any non-monotonic logic in K5-KD45 and many-valued reflexive autoepistemic logic corresponds to KTw5-Sw5.