Fundamenta Informaticae - Volume 42, issue 1

Authors: MacCaull, Wendy

Article Type: Research Article

Abstract: Using a relational approach, we investigate the implication problem for dependencies for information relations, focusing on functional dependencies, association rules and multivalued dependencies. We develop a Rasiowa/Sikorski-style relational calculus and show that the associated tableaux style of reasoning gives a decidable procedure for each of the three kinds of inference problems under consideration. This work has applications to classical database theory and to Rough Set Theory. The techniques may be generalized to the many other data dependencies which have formulations via binary relations and they can be applied to other information relations which arise in the study of incomplete information.

Keywords: information systems, dependencies, relational semantics, relational proof system

DOI: 10.3233/FI-2000-42101

Citation: Fundamenta Informaticae, vol. 42, no. 1, pp. 1-27, 2000

Authors: Nguyen, Linh Anh

Article Type: Research Article

Abstract: We give algorithms to construct the least L-model for a given positive modal logic program P, where L can be one of the modal logics KD, T, KDB, B, KD4, S4, KD5, KD45, and S5. If L ∈ {KD5,KD45,S5}, or L ∈ {KD,T,KDB,B} and the modal depth of P is finitely bounded, then the least L-model of P can be constructed in PTIME and coded in polynomial space. We also show that if P has no flat models then it has the least models in KB, K5, K45, and KB5. As a consequence, the problem of checking the satisfiability of …a set of modal Horn formulae with finitely bounded modal depth in KD, T, KB, KDB, or B is decidable in PTIME. The known result that the problem of checking the satisfiability of a set of Horn formulae in K5, KD5, K45, KD45, KB5, or S5 is decidable in PTIME is also studied in this work via a different method. Show more

DOI: 10.3233/FI-2000-42102

Citation: Fundamenta Informaticae, vol. 42, no. 1, pp. 29-60, 2000

Authors: Wang, Yongge | Desmedt, Yvo | Burmester, Mike

Article Type: Research Article

Abstract: We consider the problem of dependable computation with multiple inputs. The goal is to study when redundancy can help to achieve survivability and when it cannot. We use AND/OR graphs to model fault tolerant computations with multiple inputs. While there is a polynomial time algorithm for finding vertex disjoint paths in networks, we will show that the equivalent problem in computation systems with multiple inputs is NP-hard. Our main results are as follows. (1) We present a general model for fault tolerant computation systems with multiple inputs: AND/OR graphs. (2) We show that it is NP-hard to find two vertex …disjoint solution graphs in an AND/OR graph. It follows that in the general case redundancy cannot help to achieve survivability, assuming P≠NP. Show more

Keywords: Dependable computation, complexity theory, NP-hardness

DOI: 10.3233/FI-2000-42103

Citation: Fundamenta Informaticae, vol. 42, no. 1, pp. 61-73, 2000

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: An algebra of processes is proposed in which processes are modelled in terms of data rather than events. Structures representing processes are similar to the labelled event structures of Winskel (1982), but they denote flows of data. For processes represented in such a way operations similar to those of CCS (the Calculus of Communicating Systems as developed by Milner (1980)) are defined and their fundamental properties are stated.

Keywords: Reactive system, process, history, prefix order, flow of data, approximation order, sum, composition, prefixing, restricting communication, applying a substitution, fixed-point, equivalence

DOI: 10.3233/FI-2000-42104

Citation: Fundamenta Informaticae, vol. 42, no. 1, pp. 75-104, 2000