Fundamenta Informaticae - Volume 75, issue 1-4

Authors: Doherty, Patrick | Szałas, Andrzej

Article Type: Research Article

Abstract: This paper focuses on approximate reasoning based on the use of similarity spaces. Similarity spaces and the approximated relations induced by them are a generalization of the rough set-based approximations of Pawlak [17, 18]. Similarity spaces are used to define neighborhoods around individuals and these in turn are used to define approximate sets and relations. In any of the approaches, one would like to embed such relations in an appropriate logic which can be used as …a reasoning engine for specific applications with specific constraints. We propose a framework which permits a formal study of the relationship between approximate relations, similarity spaces and three-valued logics. Using ideas from correspondence theory for modal logics and constraints on an accessibility relation, we develop an analogous framework for three-valued logics and constraints on similarity relations. In this manner, we can provide a tool which helps in determining the proper three-valued logical reasoning engine to use for different classes of approximate relations generated via specific types of similarity spaces. Additionally, by choosing a three-valued logic first, the framework determines what constraints would be required on a similarity relation and the approximate relations induced by it. Such information would guide the generation of approximate relations for specific applications. Show more

Keywords: approximate reasoning, rough sets, similarity relation, three-valued logics

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 179-193, 2007

Authors: Dubois, Didier | de Saint-Cyr, Florence Dupin | Prade, Henri

Article Type: Research Article

Abstract: The paper starts from the standard relational view linking objects and properties in formal concept analysis, here augmented with four modal-style operators (known as sufficiency, dual sufficiency, necessity and possibility operators). Formal concept analysis is mainly based on the first operator, while the others come from qualitative data analysis and can be also related to rough set theory. A possibility-theoretic reading of formal concept analysis with these four operators is proposed. First, it is shown that …four and only four operators are indeed needed in order to describe the nine situations that can occur when comparing a statement (or its negation) with a state of information. The parallel between possibility theory and formal concept analysis suggests the introduction of new notions such as normalization and conditioning in the latter framework, also leading to point out some meaningful properties. Moreover, the graded setting of possibility theory allows us to suggest the extension of formal concept analysis to situations with incomplete or uncertain information. Show more

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 195-213, 2007

Authors: Düntsch, Ivo | Konikowska, Beata

Article Type: Research Article

Abstract: The paper explores two basic types of relations betwen objects of a Pawlak-style information system generated by the values of some attribute of those objects: disagreement (disjoint sets of values) and exhaustiveness (sets of values adding up to the whole universe of the attribute). Out of these two fundamental types of relations, most other types of relations on objects of an information system considered in the literature can be derived – as, for example, indiscernibility, similarity …and complementarity. The algebraic properties of disagreement and indiscernibility relations are explored, and a representation theorem for each of these two types of relations is proved. The notions of disagreement and exhaustiveness relations for a single attribute are extended to relations generated by arbitrary sets of attributes, yielding two families of relations parametrized by sets of attributes. They are used as accessibility relations to define a multi–modal logic with modalities corresponding to the lower and upper approximation of a set in Pawlak's rough set theory. Finally, a complete Rasiowa-Sikorski deduction system for that logic is developed. Show more

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 215-238, 2007

Authors: Dziubiński, Marcin | Verbrugge, Rineke | Dunin-K�plicz, Barbara

Article Type: Research Article

Abstract: Our previous research presents a methodology of cooperative problem solving for beliefdesire- intention (BDI) systems, based on a complete formal theory called TEAMLOG. This covers both a static part, defining individual, bilateral and collective agent attitudes, and a dynamic part, describing system reconfiguration in a dynamic, unpredictable environment. In this paper, we investigate the complexity of the satisfiability problem of the static part of TEAMLOG, focusing on individual and collective attitudes up to collective …intention. Our logics for teamwork are squarely multi-modal, in the sense that different operators are combined and may interfere. One might expect that such a combination is much more complex than the basic multi-agent logic with one operator, but in fact we show that it is not the case: the individual part of TEAMLOG is PSPACE-complete, just like the single modality case. The full system, modelling a subtle interplay between individual and group attitudes, turns out to be EXPTIME-complete, and remains so even when propositional dynamic logic is added to it. Additionally we make a first step towards restricting the language of TEAMLOG in order to reduce its computational complexity. We study formulas with bounded modal depth and show that in case of the individual part of our logics, we obtain a reduction of the complexity to NPTIME-completeness. We also show that for group attitudes in TEAMLOG the satisfiability problem remains in EXPTIMEhard, even when modal depth is bounded by 2. We also study the combination of reducing modal depth and the number of propositional atoms. We show that in both cases this allows for checking the satisfiability in linear time. Show more

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 239-262, 2007

Authors: Ehrenfeucht, A. | Rozenberg, G.

Article Type: Research Article

Abstract: Interactions between biochemical reactions lie at the heart of functioning of a living cell. In order to formalize these interactions we introduce reaction systems. We motivate them by explicitely stating a number of assumptions/axioms that (we believe) hold for a great number of biochemical reactions – we point out that these assumptions are very different from the ones underlying traditional models of computation. The paper provides the basic definitions, illustrates them by biology and computer science …oriented examples, relates reaction systems to some traditional models of computation, and proves some basic properties of reaction systems. Show more

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 263-280, 2007

Authors: Göhring, Daniel | Burkhard, Hans-Dieter

Article Type: Research Article

Abstract: In this paper we describe how a group of agents can commonly estimate the position of objects. Furthermore we will show how these modeled object positions can be used for an improved self localization. Modeling of moving objects is commonly done by a single agent and in a robocentric coordinate frame because this information is sufficient for most low level robot control and it is independent of the quality of the current robot localization. Especially when …many robots cooperate with each other in a partially observable environment they have to share and to communicate information. For multiple robots to cooperate and share information, though, they need to agree on a global, allocentric frame of reference. But when transforming the egocentric object model into a global one, it inherits the localization error of the robot in addition to the error associated with the egocentric model. We propose using the relation of objects detected in camera images to other objects in the same camera image as a basis for estimating the position of the object in a global coordinate system. The spacial relation of objects with respect to stationary objects (e.g., landmarks) offers several advantages: The information is independent of robot localization and odometry and it can easily be communicated. We present experimental evidence that shows how two robots are able to infer the position of an object within a global frame of reference, even though they are not localized themselves. We will also show, how to use this object information for self localization. A third aspect of this work will cope with the communication delay, therefore we will show how the Hidden Markov Model can be extended for distributed object tracking. Show more

Keywords: Markov Localization, Multi-Agent Systems

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 281-294, 2007

Authors: Janicki, Ryszard | Lê, Dai Tri Man

Article Type: Research Article

Abstract: A version of mereology (i.e. theory of parts and fusions) is presented. Some applications to model software structures are discussed.

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 295-314, 2007

Authors: Järvinen, Jouni

Article Type: Research Article

Abstract: In this paper we show that each Galois connection between two complete lattices determines an Armstrong system, that is, a closed set of dependencies. Especially, we study Galois connections and Armstrong systems determined by Pawlak's information systems.

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 315-330, 2007

Authors: Marcus, Solomon

Article Type: Other

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 331-334, 2007

Authors: Mazurkiewicz, Antoni

Article Type: Research Article

Abstract: In the paper a class of locally derivable graphs is defined and discussed. Well known particular cases of derivable graphs are (among others) trees, complete, and triangular graphs; in the paper a broader class of locally derivable graphs, called closed graphs, is defined. Nodes and edges of closed graphs can be partitioned into external and internal ones; the main property of such graphs their local reducibility: successive removing its external nodes leads eventually to a singleton, …and removing its external edges leads to an a spanning tree of the graph. The class of closed graphs is then a class enabling structural reducing. This property can be applied in processor networks to design some local procedures leading to global results. Show more

Keywords: Graphs, graph transformations, local computations

Citation: Fundamenta Informaticae, vol. 75, no. 1-4, pp. 335-355, 2007

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