Fundamenta Informaticae - Volume 53, issue 1

Authors: Demri, Stéphane | Sattler, Ulrike

Article Type: Research Article

Abstract: 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. Show more

Keywords: computational complexity, Büchi tree automaton, information logic, hybrid logic

Citation: Fundamenta Informaticae, vol. 53, no. 1, pp. 1-22, 2002

Authors: Georgescu, George | Popescu, Andrei

Article Type: Research Article

Abstract: A classical (crisp) concept is given by its extent (a set of objects) and its intent (a set of properties). In commutative fuzzy logic, the generalization comes naturally, considering fuzzy sets of objects and properties. In both cases (the first being actually a particular case of the second), the situation is perfectly symmetrical: a concept is given by a pair (A,B), where A is the largest set of objects sharing the attributes from B and B …is the largest set of attributes shared by the objects from A (with the necessary nuance when fuzziness is concerned). Because of this symmetry, working with objects is the same as working with properties, so there is no need to make any choice. In this paper, we define concepts in a "non-commutative fuzzy world", where conjunction of sentences is not necessarily commutative, which leads to the following non-symmetrical situation: a concept has one extent (because, at the end of the day, concepts are meant to embrace, using certain descriptions, diverse sets of objects), but two intents, given by the two residua (implications) of the non-commutative conjunction. Show more

Citation: Fundamenta Informaticae, vol. 53, no. 1, pp. 23-54, 2002

Authors: Middelburg, Kees A.

Article Type: Research Article

Abstract: The possibility of two or more actions to be performed consecutively at the same point in time is not excluded in the process algebras from the framework of process algebras with timing presented by Baeten and Middelburg [Handbook of Process Algebra, Elsevier, 2001, Chapter 10]. This possibility is useful in practice when describing and analyzing systems in which actions occur that are entirely independent. However, it is an abstraction of reality to assume that actions can …be performed consecutively at the same point in time. In this paper, we propose a process algebra with timing in which this possibility is excluded, but nonstandard non-negative real numbers are included in the time domain. It is shown that this new process algebra generalizes the process algebras with timing from the aforementioned framework in a smooth and natural way. Show more

Keywords: process algebra, timing, nonstandard timing, urgent actions

Citation: Fundamenta Informaticae, vol. 53, no. 1, pp. 55-77, 2002

Authors: Zhao, Xishun | Liberatore, Paolo

Article Type: Research Article

Abstract: In this paper we analyze the problem of checking whether a default theory has a single extension. This problem is important for at least three reasons. First, if a theory has a single extension, nonmonotonic inference can be reduced to entailment in propositional logic (which is computationally easier) using the set of consequences of the generating defaults. Second, a theory with many extensions is typically weak i.e., it has few consequences; this indicates that the theory …is of little use, and that new information has to be added to it, either as new formulae, or as preferences over defaults. Third, some applications require as few extensions as possible (e.g. diagnosis). We study the complexity of checking whether a default theory has a single extension. We consider the combination of several restrictions of default logics: seminormal, normal, disjunction-free, unary, ordered. Complexity varies from the first to the third level of the polynomial hierarchy. The problem of checking whether a theory has a given number of extensions is also discussed. Show more

Keywords: default logic, complexity, unique extension existence problem

Citation: Fundamenta Informaticae, vol. 53, no. 1, pp. 79-104, 2002