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: information logic

Sortuj według:

Ogranicz wyniki do:

Relative Nondeterministic Information Logic is EXPTIME-complete

Demri S., Orłowska E.

Fundamenta Informaticae

2007

Vol. 75, nr 1-4

163-178

We define a relative version of the logic NIL introduced by Or owska, Pawlak and Vakarelov and we show that its satisfiability is not only decidable but also EXPTIME-complete. Such a logic combines two ingredients that are seldom present simultaneously in information logics: frame conditions involving more than one information relation and relative frames. The EXPTIMEupper bound is obtained by designing a well-suited decision procedure based on the nonemptiness problem of Büchi automata on infinite trees. The paper provides evidence that Büchi automata on infinite trees are crucial language acceptors even for relative information logics with multiple types of relations.

Arrow Logic with Arbitrary Intersections: Applications to Pawlak's Information Systems

Balbiani P., Vakarelov D.

Fundamenta Informaticae

2007

Vol. 75, nr 1-4

1-25

We dedicate this paper to the memory of Zdislaw Pawlak, the founder of rough sets methodology in computer science. A great deal of our scientific work was motivated and influenced by Pawlak's ideas.

Automata-Theoretic Decision Procedures for Information Logics

Demri S., Sattler U.

Fundamenta Informaticae

2002

Vol. 53, nr 1

1-22

Automata-theoretic decision procedures for solving model-checking and satisfiability problems for temporal, dynamic, and description logics have flourished during the past decades. In the paper we define an EXPTIME decision procedure based on the emptiness problem of Büchi automata on infinite trees for the very expressive information logic SIM designed for reasoning about information systems. This logic involves modal parameters satisfying certain properties to capture the relevant nominals at the formula level, Boolean expressions and nominals at the modal level, an implicit intersection operation for relations, and a universal modality. The original combination of known techniques allows us to solve the open question related to the EXPTIME -completeness of SIM. Furthermore, we discuss how variants of SIM can be treated similarly although the decidability status of some of them is still unknown.