Fundamenta Informaticae - Volume 53, issue 3-4

Authors: Aho, Isto

Article Type: Research Article

Abstract: We describe a special case of the interactive knapsack optimization problem (motivated by the load clipping problem) solvable in polynomial time. Given an instance parameterized by k, the solution can be found in polynomial time, where the polynomial has degree k. In the interactive knapsack problem, $k$ is connected to the length induced by an item. A similar construction solves a special case of the 0–1 multi-dimensional knapsack and the 0–1 linear integer programming problems in …polynomial time. In these problems the parameter determines the width of the restriction matrix, which is a band matrix. We extend the 0–1 multi-dimensional knapsack solution to 0–n multi-dimensional knapsack problems (and to 0–n IP problems). Our algorithms are based on the (resource bounded) shortest path search: we represent restrictions efficiently in a form of a graph such that each feasible solution has a path between given source and target vertices. Show more

Keywords: Knapsack-type problems, longest path, polynomial-time instances

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 199-228, 2002

Authors: Bai, Yun | Varadharajan, Vijay

Article Type: Research Article

Abstract: Authorization specification in object oriented databases is being increasingly investigated recently by many researchers [4,5,7,9,10]. However, most of the work todate suffers from a lack of formal logic semantics to characterize different types of inheritance properties of authorization policies among complex data objects. This paper is to address this issue from a formal logic point of view. In particular, we propose a logic language that has a clear and declarative semantics to specify the structural features …of object oriented databases and authorizations associated with complex data objects in databases. Our formalization characterizes the model-theoretic semantics of object oriented databases and authorizations associated with them. A direct advantage of this approach is that we can formally specify and reason about authorizations on data objects without loosing inheritance and abstraction features of object oriented databases. Show more

Keywords: Formal specification, security, database

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 229-250, 2002

Authors: Benferhat, Salem | Dubois, Didier | Lagrue, Sylvain | Papini, Odile

Article Type: Research Article

Abstract: This paper deals with iterated belief change and proposes a drastic revision rule that modifies a plausibility ordering of interpretations in such a way that any world where the input observation holds is more plausible that any world where it does not. This change rule makes sense in a dynamic context where observations are received, and the newer observations are considered more plausible than older ones. It is shown how to encode an epistemic state using …polynomials equipped with the lexicographic ordering. This encoding makes it very easy to implement and iterate the revision rule using simple operations on these polynomials. Moreover, polynomials allow to keep track of the sequence of observations. Lastly, it is shown how to efficiently compute the revision rule at the syntactical level, when the epistemic state is concisely represented by a prioritized belief base. Our revision rule is the most drastic one can think of, in accordance with Darwiche and Pearl's principles, and thus contrasts with the minimal change rule called natural belief revision. The paper also shows how to obtain the reversibility of Boutilier's natural belief revision and possibilistic revision using polynomials. Show more

Keywords: revision, iterated revision, reversibility, polynomials

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 251-280, 2002

Authors: Haar, Stefan

Article Type: Research Article

Abstract: This article introduces probabilistic cluster branching processes, a probabilistic unfolding semantics for untimed Petri nets with no structural or safety assumptions. The unfolding is constructed by local choices on each cluster (conflict closed subnet), while the authorization for cluster actions is governed by a stochastic trace, the policy. The probabilistic model for this semantics yields probability measures for concurrent runs. We introduce and characterize stopping times for this model, and prove a strong …Markov property. Particularly adequate probability measures for the choice of step in a cluster, as well as for the policy, are obtained by constructing Markov Fields from suitable marking-dependent Gibbs potentials. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 281-314, 2002

Authors: Honkala, Juha

Article Type: Research Article

Abstract: We introduce a new class of algebraic series with noncommuting variables having a decidable equivalence problem. As a tool we consider star roots of formal power series.

Keywords: Algebraic series, equivalence problem

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 315-320, 2002

Authors: Mani, A.

Article Type: Research Article

Abstract: In the initial section of this research paper rough equalities from partially ordered approximation spaces are investigated. Special types of rough equalities are characterized via convex and other types of sets. Extension of these to all types of rough equalities is also indicated. Two new theories of "Rough Difference Order" which are often more general and distinct from that of "Rough Orders" are also developed in the last section by the present author.

Keywords: approximation spaces, partially ordered approximation spaces, rough difference orders, difference posets, ρμ-equivalence relations, convex sets, strict intervals

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 321-333, 2002

Authors: Polkowski, Lech | Araszkiewicz, Bolesław

Article Type: Research Article

Abstract: A value of a game v is a function which to each coalition S assigns the value v(S) of this coalition, meaning the expected pay-off for players in that coalition. A classical approach of von Neumann and Morgenstern [6] had set some formal requirements on v which contemporary theories of value adhere to. A Shapley value of the game with a value v [14] is a functional Φ giving for each player p the value Φ_p(v) estimating …the expected pay–off of the player p in the game. Game as well as conflict theory have been given recently much attention on the part of rough and fuzzy set communities [11, 8, 1, 4, 7, 2]. In particular, problems of plausible strategies in conflicts as well as problems related to Shapley's value [3,2] have been addressed. We confront here the problem of estimating a value as well as Shapley's value of a game from a partial data about the game. We apply to this end the rough set ideas of approximations, defining the lower and the upper value of the game and, respectively, the lower and the upper Shapley value. We also define a notion of an exact coalition, on which both values coincide giving the true value of the game; we investigate the structure of the family of exact sets showing its closeness on complements, disjoint sums, and intersections of coalitions covering the set of players. This work sets open a new area of rough set applications in mining constructs from data. The constructs mined in this case are values as well as Shapley values of games. Show more

Keywords: rough sets, the lower and the upper value (Shapley value) of a game, coalition, exact coalition

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 335-343, 2002

Authors: Słowiński, Krzysztof | Stefanowski, Jerzy | Siwiński, Dariusz

Article Type: Research Article

Abstract: We discuss a process of analysing medical diagnostic data by means of the combined rule induction and rough set approach. The first step of this analysis includes the use of various techniques for discretization of numerical attributes. Rough sets theory is applied to determine attribute importance for the patients' classification. The novel contribution concerns considering two different algorithms inducing either minimum or satisfactory set of decision rules. Verification of classification abilities of these rule sets is …extended by an examination of sensitivity and specificity measures. Moreover, a comparative study of these composed approaches against other learning systems is discussed. The approach is illustrated on a medical problem concerning anterior cruciate ligament (ACL) rupture in a knee. The patients are described by attributes coming from anamnesis, MR examinations and verified by arthroscopy. The clinical impact of our research is indicating two attributes (PCL index, age) and their specific values that could support a physician in resigning from performing arthroscopy for some patients. Show more

Keywords: Discretization techniques, decision rules, attribute selection, classification performance, magnetic resonance, arthroscopy

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 345-363, 2002

Authors: Ślezak, Dominik

Article Type: Research Article

Abstract: We use information entropy measure to extend the rough set based notion of a reduct. We introduce the Approximate Entropy Reduction Principle (AERP). It states that any simplification (reduction of attributes) in the decision model, which approximately preserves its conditional entropy (the measure of inconsistency of defining decision by conditional attributes) should be performed to decrease its prior entropy (the measure of the model's complexity). We show NP-hardness of optimization tasks concerning application …of various modifications of AERP to data analysis. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 365-390, 2002

Authors: Terlikowski, Tomasz

Article Type: Research Article

Abstract: In this paper, continuing our research in [7], we introduce a logical notion of inner implication. This notion is aimed at a formalization of some concepts of control theory. The respective notion of control structure and the concept of risk will be discussed in the following parts of the work. The reader will find all relevant notions in [7].

Keywords:

Citation: Fundamenta Informaticae, vol. 53, no. 3-4, pp. 391-397, 2002