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