Wyniki wyszukiwania - BazTech

Ograniczanie wyników

3 Fundamenta Informaticae

Znaleziono wyników: 3

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: multimodal logic

Sortuj według:

Ogranicz wyniki do:

A Multimodal Logic Approach to Order of Magnitude Qualitative Reasoning with Comparability and Negligibility Relations

Burrieza A., Ojeda-Aciego M.

Fundamenta Informaticae

2005

Vol. 68, nr 1/2

21--46

Non-classical logics have proven to be an adequate framework to formalize knowledge representation. In this paper we focus on a multimodal approach to formalize order-of-magnitude qualitative reasoning, extending the recently introduced system MQ, by means of a certain notion of negligibility relation which satisfies a number of intuitively plausible properties, as well as a minimal axiom system allowing for interaction among the different qualitative relations. The main aim is to show the completeness of the formal system introduced. Moreover, we consider some definability results and discuss possible directions for further research.

The nondeterministic information logic NIL is PSPACE-complete

Demri S.

Fundamenta Informaticae

2000

Vol. 42, nr 3,4

211-234

The nondeterministic information logic NIL has been introduced by Or owska and Pawlak in 1984 as a logic for reasoning about total information systems with the similarity, the forward inclusion and the backward inclusion relations. In 1987, Vakarelov provides the first first-order characterization of structures derived from information systems and this has been done with the semantical structures of NIL. Since then, various extensions of NIL have been introduced and many issues for information logics about decidability and Hilbert-style proof systems have been solved. However, computational complexity issues have been seldom attacked in the literature mainly because the information logics are propositional polymodal logics with interdependent modal connectives. We show that NIL satisfiability is a PSPACE-complete problem. PSPACE-hardness is shown to be an easy consequence of PSPACE-hardness of the well-known modal logic S4. The main difficulty is to show that NIL satisfiability is in PSPACE. To do so we present an original construction that extends various previous works by Ladner (1977), Halpern and Moses (1992) and Spaan (1993).

Computational complexity of multimodal logics based on rough sets

Demri S., Stepaniuk J.

Fundamenta Informaticae

2000

Vol. 44, Nr 4

373-396

We characterize the computational complexity of a family of approximation multimodal logics in which interdependent modal connectives are part of the language. Those logics have been designed to reason in presence of incomplete information in the sense of rough set theory. More precisely, we show that all the logics have a PSPACE-complete satisfiability problem and we define a family of tolerance approximation multimodal logics whose satisfiability is EXPTIME-complete. This illustrates that the PSPACE upper bound for this kind of multimodal logics is a very special feature of such logics. The PSPACE upper bounds are established by adequately designing Ladner-style tableaux-based procedures whereas the EXPTIME lower bound is established by reduction from the global satisfiability problem for the standard modal logic B.