Fundamenta Informaticae - Volume 67, issue 1-3

Authors: Latkowski, Rafał

Article Type: Research Article

Abstract: The indiscernibility relation is a fundamental concept of the rough set theory. The original definition of the indiscernibility relation does not capture the situation where some of the attribute values are missing. This paper tries to enhance former works by proposing an individual treatment of missing values at the attribute or value level. The main assumption of the theses presented in this paper considers that not all missing values are semantically equal. We propose two different …approaches to create an individual indiscernibility relation for a particular information system. The first relation assumes variable, but fixed semantics of missing attribute values in different columns. The second relation assumes different semantics of missing attribute values, although this variability is limited with expressive power of formulas utilizing descriptors. We provide also a comparison of flexible indiscernibility relations and missing value imputation methods. Finally we present a simple algorithm for inducing sub-optimal relations from data. Show more

Keywords: Rough Sets, Missing Attribute Values, Incomplete Information Systems

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 131-147, 2005

Authors: Popova-Zeugmann, Louchka | Heiner, Monika | Koch, Ina

Article Type: Research Article

Abstract: Biochemical networks are modelled at different abstraction levels. Basically, qualitative and quantitative models can be distinguished, which are typically treated as separate ones. In this paper, we bridge the gap between qualitative and quantitative models and apply time Petri nets for modelling and analysis of molecular biological systems. We demonstrate how to develop quantitative models of biochemical networks in a systematic manner, starting from the underlying qualitative ones. For this purpose we exploit the …well-established structural Petri net analysis technique of transition invariants, which may be interpreted as a characterisation of the systems steady state behaviour. For the analysis of the derived quantitative model, given as time Petri net, we present structural techniques to decide the time-dependent realisability of a transition sequence and to calculate its shortest and longest time length. All steps of the demonstrated approach consider systems of integer linear inequalities. The crucial point is the total avoidance of any state space construction. Therefore, the presented technology may be applied also to infinite systems, i.e. unbounded Petri nets. Show more

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 149-162, 2005

Authors: Popova-Zeugmann, Louchka | Werner, Matthias

Article Type: Research Article

Abstract: In this paper, a method to determine best-case and worst-case times between two arbitrary markings in a bounded TPN is presented. The method uses a discrete subset of the state space of the net and achieves the results, which are integers, in polynomial time. As an application of the method the solution of a scheduling problem is shown.

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 163-174, 2005

Authors: Redziejowski, Roman R.

Article Type: Research Article

Abstract: The notion of associative infinite product is applied to traces, resulting in an alternative approach to introducing infinite traces. Four different versions of product are explored, two of them identical to known definitions of infinite trace.

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 175-185, 2005

Authors: Schröter, Kay | Urbig, Diemo | Hans, Nora

Article Type: Research Article

Abstract: A mechanism is presented that allows agents in multiagent systems with private knowledge about resource endowments to establish negotiation groups with commonly known negotiation spaces. This is done by exchanging information. Specific agents that are provided by the system mediate the communication and take over some very complex calculations. The negotiating agents reveal only information to the mediators that they consider relevant for their own objectives or for the current negotiation. A broadcast of all the …agents' private knowledge is not required. We label this interactive mechanism social formation of negotiation spaces and groups. Furthermore we drop the often-made assumption of isolated negotiations. Our agents remember other agents that have contributed to reach a beneficial agreement. These agents are assumed to have credits. In later negotiations our agents will be more generous towards agents with credits. The applied credit mechanism does not require that all agents participate nor does it require that other agents are aware of this mechanism. We conclude this report with hypotheses that will be evaluated by simulations. Show more

Keywords: negotiating agents, negotiation space and group formation, multilateral non-isolated negotiations, credits

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 187-201, 2005

Authors: Stepaniuk, Jarosław | Bazan, Jan G. | Skowron, Andrzej

Article Type: Research Article

Abstract: We outline an approach to hierarchical modelling of complex patterns that is based on operations of sums with constraints on information systems. We show that such operations can be treated as a universal tool in hierarchical modelling of complex patterns.

Keywords: complex patterns, rough sets, approximation spaces, information systems, infomorphisms

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 203-217, 2005

Authors: Suraj, Zbigniew | Peters, James F. | Grochowalski, Piotr

Article Type: Research Article

Abstract: The Khepera robot belongs to the family of miniature mobile robots of the K-Team firm. It is used in a number of places for scientific and educational purposes. Considering its advantages (such as small size, precision of movement, ease of control), it is applied to testing different approaches in the domain of artificial intelligence. This paper describes the methodology of a control system design for the Khepera robot based on a rough set approach. The proposed approach entails …a study of robot behaviour insofar as its movements are influenced by measurements fromits sensors and the choice of actions that make it possible for the robot to achieve its system goals. The constructed controller concerns the realization of some tasks such as avoiding the obstacles, reaching a target, following an obstacle, finding the way out of a labyrinth. The proposed controller has been tested on both a robot simulator and on a real robot. Our experimental results show that the proposed rough set methodology can be applied to the design of a controller for the Khepera robot. Show more

Keywords: Artificial intelligence, rough sets, fuzzy systems, machine learning, Khepera robot, control design, expert system

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 219-231, 2005

Authors: Suraj, Zbigniew | Pancerz, Krzysztof

Article Type: Research Article

Abstract: Abstract. Design of concurrent systems under various constraints is an important problem in reallife applications in many domains (for example, automatics, robotics, software engineering) and has earlier been discussed in the literature using different formalisms. In this paper some approaches to the concurrent system design based on restrictions will be considered. In our approaches, we will use the rough set formalism. The coloured Petri nets (CP-nets) will be used to model designed concurrent systems.

Keywords: concurrent systems, restrictions, information systems, coloured Petri nets

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 233-247, 2005

Authors: Synak, Piotr | Bazan, Jan G. | Skowron, Andrzej | Peters, James F.

Article Type: Research Article

Abstract: We discuss the problems of spatio-temporal reasoning in the context of hierarchical information maps and approximate reasoning networks (AR networks). Hierarchical information maps are used for representations of domain knowledge about objects, their parts, and their dynamical changes. AR networks are patterns constructed over sensory measurements and they are discovered from hierarchical information maps and experimental data. They make it possible to approximate domain knowledge, i.e., complex spatio-temporal concepts and reasonings represented …in hierarchical information maps. Experiments with classifiers based on AR schemes using a road traffic simulator are also briefly presented. Show more

Keywords: complex objects, concept approximation, spatio-temporal reasoning, information maps, pattern, sensor measurement, AR schemes, AR networks

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 249-269, 2005

Authors: Urbig, Diemo

Article Type: Research Article

Abstract: Conflict resolution, e.g. negotiation, is frequently about an interactive process that forces agents to make concessions in order to resolve the conflict. In multilateral negotiations, concessions might be directed to one or another partner. In isolated negotiations such directed concessions might be less useful, but may become important for interdependent negotiations. We present weight-based negotiation mechanisms that easily implement the concept of directed concessions. As an example we implement and simulate the …weighted sum approach. We show that the presented class of negotiation mechanisms results in Pareto-optimal agreements. Not all weight-based mechanisms, especially the weighted sum approach, can generate all Pareto-optimal solutions, but for every discrete negotiation space there is a weight-based mechanism based on a continuous balancing function that can generate all Pareto-optimal solutions. Show more

Keywords: negotiating agents, balanced personal utilities

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 271-285, 2005

Authors: Wróblewski, Dobiesław

Article Type: Research Article

Abstract: We consider finite connected undirected graphs as a model for anonymous computer networks. In this framework we show a general purpose distributed election protocol, which uses forward links over the standard communication channels between processors. The forward links are represented in the form of structured labels, so the algorithm is in fact a graph relabelling system. However, its transformations are not local in the classical sense. For this particular algorithm we define a new notion of …semi-locality. We claim that semi-local computations are as powerful as global ones, while still conforming to the intuitive meaning of the locality term. Show more

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 287-301, 2005

Authors: Zbrzezny, Andrzej

Article Type: Research Article

Abstract: This paper deals with the problemof checking reachability for timed automata with diagonal constraints. Such automata are needed in many applications e.g. to model scheduling problems. We introduce a new discretization for timed automata which enables SAT based reachability analysis for timed automata for which comparisons between two clocks are allowed. In our earlier papers SAT based reachability analysis was restricted to the so called diagonal-free timed automata, where only comparisons between clocks and …constants are allowed. Show more

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 303-322, 2005