Fundamenta Informaticae - Volume 75, issue 1-4

Authors: Moshkov, Mikhail Ju. | Piliszczuk, Marcin | Zielosko, Beata

Article Type: Research Article

Abstract: In the paper for the most part of binary decision tables upper and lower bounds on the cardinality of partial reducts and length of irreducible partial decision rules are obtained. The number of partial reducts and the number of irreducible partial decision rules are evaluated. Complexity of algorithms for construction of all partial reducts and all irreducible partial decision rules is studied on the basis of obtained bounds.

Keywords: partial reducts, irreducible partial decision rules, algorithms for construction, complexity

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 357-374, 2007

Authors: Novotný, Miroslav

Article Type: Research Article

Abstract: Construction of retracts of a general algebra is described by using retracts of mono-unary algebras. Inspirational influence of the theory of Pawlak machines is mentioned.

Keywords: algebra, homomorphism, endomorphism, retraction endomorphism, retract, prepared algebra, mono-unary algebra

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 375-384, 2007

Authors: Ohsuga, Setsuo

Article Type: Research Article

Abstract: Information becomes more and more sophisticated with its ever-increasing use. Information sophistication relates closely to human intelligence. In order to ensure the common form of information, a symbolic language has been developed. It gradually progressed so that the representation of information of higher-level sophistication becomes possible. However, there is still a lot of information that cannot be captured by a language and has to be represented at very low level. A great effort is necessary for …representing such information in a symbolic language because there is a large gap between non-symbolic and symbolic representations. This paper discusses two problems concerning bridging this gap, one from symbolic processing side and the other from nonsymbolic processing side. The former is the language aspect of activity called discovery. The latter concerns an evolutional process of language creation. Both are very important topics for explaining the process of sophisticating information. Show more

Keywords: Language Acquirement, Knowledge Discovery, Symbolic and Non-Symbolic Processing

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 385-406, 2007

Authors: Peters, James F.

Article Type: Research Article

Abstract: The problem considered in this paper is how to approximate sets of objects that are qualitatively but not necessarily spatially near each other. The term qualitatively near is used here to mean closeness of descriptions or distinctive characteristics of objects. The solution to this problem is inspired by the work of Zdzisław Pawlak during the early 1980s on the classification of objects by means of their attributes. This article introduces a special theory of the nearness …of objects that are either static (do not change) or dynamic (change over time). The basic approach is to consider a link relation, which is defined relative to measurements associated with features shared by objects independent of their spatial relations. One of the outcomes of this work is the introduction of new forms of approximations of objects and sets of objects. The nearness of objects can be approximated using rough set methods. The proposed approach to approximation of objects is a straightforward extension of the rough set approach to approximating objects, where approximation can be considered in the context of information granules (neighborhoods). In addition, the usual rough set approach to concept approximation has been enriched by an increase in the number of granules (neighborhoods) associated with the classification of a concept as near to its approximation. A byproduct of the proposed approximation method is what we call a near set. It should also be observed that what is presented in this paper is considered a special (not a general) theory about nearness of objects. The contribution of this article is an approach to nearness as a vague concept which can be approximated from the state of objects and domain knowledge. Show more

Keywords: Approximation, feature, link relation, near set, part, pattern recognition, rough sets, structured objects, vagueness

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 407-433, 2007

Authors: Polkowski, Lech

Article Type: Research Article

Abstract: This article is conceived as a homage to the life and work of Professor Zdzisław Pawlak. Intended as a mark to His 80th birthday, it turns out to be a homage to His memory. On such occasions, one is drawn into a whirl of memories, in this case reaching back to about 92', when the author met Zdzisław because of being interested in rough sets. That theory was created in 1982 by Zdzisław Pawlak as a vehicle to carry out …Concept Approximation and a fortiori, Decision Making, Data Mining, Knowledge Discovery and other activities. The creation of rough set theory, in my opinion then and now, was a single act, ignited and facilitated by Zdzisław's deep knowledge of ideas going back to Frege, Russell, Łukasiewicz, Popper, and others. This attitude to the tradition, was certainly a strong factor that attracted to Him creative folks. Rough sets owe this attitude the intrinsic clarity of ideas, elegant simplicity (not to be confused with easy triviality), and a fortiori a wide spectrum of applications. This essay is intended as a panoramic view also on those applications. Any creation of a theory that gains recognition, many followers, and enters the standard repertoire of researchers is, in itself, an event worthy of analysis. Such analysis is not the subject of this essay; we are satisfied with presenting some views on the nature of Concept Approximation, and with outlining against this background the main features of rough sets and their extensions. In words of Cyprian Kamil Norwid: "� a few ideas that are not new �." This essay owes much to a lecture presented by the author at the Lateran University in Rome in January 2005 at the Conference Series: Scienza e Fede sull;Interpretazione del Reale; in that lecture main ideas exposed in this essay were presented. In the present exposition, some metaphysical ideas discussed in the original lecture were omitted. Nevertheless, the author takes liberty of the essay form in order to encapsulate in this text some more refined ideas than those usually inserted in technical works. The author is grateful to Professors Giandomenico Boffi and Alberto Pettorossi for invitation to Rome. On this occasion the author wishes also to invoke with personal gratitude the memory of the late Professor Helena Rasiowa who, in addition to many deep results, created much of the logical theory of rough sets. Show more

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 435-451, 2007

Authors: Ramanna, Sheela | Peters, James F. | Skowron, Andrzej

Article Type: Research Article

Abstract: Conflict analysis and conflict resolution play an important role in negotiation during contract-management situations in many organizations. The issue here is how to model a combination of complex situations among agents where there are disagreements leading to a conflict situation, and there is a need for an acceptable set of agreements. Conflict situations also result due to different sets of view points about issues under negotiation. The solution to this problem stems from pioneering work on …this subject by Zdzisław Pawlak, which provides a basis for a complex conflict model encapsulating a decision system with complex decisions. Several approaches to the analysis of conflicts situations are presented in this paper, namely, conflict graphs, approximation spaces and risk patterns. An illustrative example of a requirements scope negotiation for an automated lighting system is presented. The contribution of this paper is a rough set-based requirements scope determination model and assessment mechanisms using a complex conflict model. Show more

Keywords: Approximation space, conflict, conflict graph, conflict resolution, negotiation, rough sets, requirements engineering

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 453-468, 2007

Authors: Salomaa, Arto

Article Type: Research Article

Abstract: We investigate binary words and languages having a balanced structure of (scattered) subwords. We introduce a "difference function" D for binary words. For D=0, the resulting language is properly context-sensitive. Parikh matrices constitute a useful technical tool in the study, we investigate also the independence of their entries. The investigation is extended to concern ω-words and periodicity. For the Fibonacci word, the D-values are in many ways connected with the Fibonacci numbers.

Keywords: subword, scattered subword, counting subwords, Parikh matrix, periodicity, Fibonacci word

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 469-482, 2007

Authors: Sen, Debashis | Pal, Sankar K.

Article Type: Research Article

Abstract: This paper presents a novel histogram thresholding technique based on the beam theory of solid mechanics and the minimization of ambiguity in information. First, a beam theory based histogram modification process is carried out. This beam theory based process considers a distance measure in order to modify the shape of the histogram. The ambiguity in the overall information given by the modified histogram is then minimized to obtain the threshold value. The ambiguity minimization is carried …out using the theories of fuzzy and rough sets, where a new definition of rough entropy is presented. The applications of the proposed scheme in performing object and edge extraction in images are reported and compared with those of a few existing classical and ambiguity minimization based schemes for thresholding. Experimental results are given to demonstrate the effectiveness of the proposed method in terms of both qualitative and quantitative measures. Show more

Keywords: Histogram thresholding, histogram modification, ambiguity minimization, fuzzy sets, rough sets, beam theory, object extraction, edge extraction

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 483-504, 2007

Authors: Skarbek, Władysław

Article Type: Research Article

Abstract: In context of Pawlak's machine a general iterative meta scheme for generating of combinatorial objects is introduced and applied to proof the correctness of ASR (Arm Switching and Rotation) algorithm generating all binary trees on k nodes. The average time complexity of the ASR algorithm and B* are analyzed and compared to the B algorithm discussed by Knuth. The analyzed algorithms are all obtained by various natural correspondences from author's DCP (Degrade and Compress Path) algorithm …for generating all ordered trees on k+1 nodes. Show more

Keywords: Pawlak' machine, binary tree, ordered tree, generating trees

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 505-536, 2007

Authors: Winkowski, Józef

Article Type: Research Article

Abstract: The paper is concerned with algebras whose elements can be used to represent runs of a system, called processes. These algebras, called behaviour algebras, are categories with respect to a partial binary operation called sequential composition, and they are partial monoids with respect to a partial binary operation called parallel composition. They are characterized by axioms such that their elements and operations can be represented by labelled posets and operations on such posets. The respective representation …is obtained without assuming a discrete nature of represented elements. In particular, it remains true for behaviour algebras with infinitely divisible elements, and thus also with elements which can represent continuous and partially continuous processes. An important consequence of the representation of elements of behaviour algebras by labelled posets is that elements of some subalgebras of behaviour algebras can be endowed in a consistent way with structures such as a graph structure etc. Show more

Keywords: Processes, states, sequential composition, parallel composition, category, partial monoid, structure

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 537-560, 2007