Fundamenta Informaticae - Volume 67, issue 1-3

Authors: Burkhard, Hans-Dieter | Czaja, Ludwik | Lindemann, Gabriela | Suraj, Zbigniew

Article Type: Other

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

Authors: Barbuti, Roberto | Cataudella, Stefano

Article Type: Research Article

Abstract: In this paper we present a use of abstract interpretation techniques for reducing synchronization overhead in an object calculus. First we present the new raconcς calculus, an extension of an already existing calculus for supporting reentrant locks. Then we use an abstract form of this calculus to check when synchronization operations may be safely eliminated from statements. Thus our approach may be used to improve performance in object oriented languages by eliminating locks, without the risks …caused by "manual" optimizations performed by programmers. Show more

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

Authors: Barbuti, Roberto | Cataudella, Stefano | Maggiolo-Schettini, Andrea | Milazzo, Paolo | Troina, Angelo

Article Type: Research Article

Abstract: We introduce a model for molecular reactions based on probabilistic rewriting rules. We give a probabilistic algorithm for rule applications as a semantics for the model, and we show how a probabilistic transition system can be derived from it. We use the algorithm in the development of an interpreter for the model, which we use to simulate the evolution of molecular systems. In particular, we show the results of the simulation of a real example of …enzymatic activity. Moreover, we apply the probabilistic model checker PRISM to the transition system derived by the model of this example, and we show the results of model checking of some illustrative properties. Show more

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 13-27, 2005

Authors: Bellia, Marco | Occhiuto, M. Eugenia

Article Type: Research Article

Abstract: Higher order programming is considered a good methodology for program design and specification, furthermore it is fundamental for rapid prototyping. The paper is devoted to higher order programming in Java and, more in general, in the OO programming paradigm. We discuss introspection to write higher order programs and compare this technique with other different, interesting approaches, including function emulation and function integration. Finally, we address the problem of embedding, in the OO paradigm, the …mechanisms for method passing and method extraction that are basic to the higher order programming methodology. Show more

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 29-44, 2005

Authors: Czaja, Ludwik

Article Type: Research Article

Abstract: A method of constructing net (cause-effect structure and Petri net) from a specification given as an axiomatic system and proving behaviour of the net to conform to the specification is presented and illustrated by two examples.

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 45-64, 2005

Authors: Farwer, Berndt | Köhler, Michael

Article Type: Research Article

Abstract: Composition of modules to larger units is a technique frequently used during the software development life cycle. It is mostly used in a "bottom up" fashion, suggested by the principles of object orientation, where the composition of simple objects to a complex one plays a central role. Composition in Petri nets has been studied in the form of place and transition fusion. Zero-Safe Nets represent a special approach, which allows the use of more …complex synchronisation structures, so-called transactions. The definition of transactions is based on interleaving semantics, i.e. on firing-sequences. Problems arise, since the definition is not closed with respect to the permutation of actions. This paper presents a partial order concurrency semantics for zero-safe nets based on Petri net processes. Using these semantics, a characterisation of such transactions closed with respect to permutation of concurrent actions becomes possible. Show more

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 65-75, 2005

Authors: Gomolińska, Anna

Article Type: Research Article

Abstract: In this paper, we study general notions of satisfiability and meaning of formulas and sets of formulas in approximation spaces. Rather than proposing one particular form of rough satisfiability and meaning, we present a number of alternative approaches. Approximate satisfiability and meaning are important, among others, for modelling of complex systems like systems of adaptive social agents. Finally, we also touch upon derivative concepts of meaning and applicability of rules.

Keywords: information granule, Pawlak information system, approximation space, rough satisfiability/meaning of formulas, rough applicability of a rule

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 77-92, 2005

Authors: Klunder, Barbara | Ochmański, Edward | Stawikowska, Krystyna

Article Type: Research Article

Abstract: Up to now, star-connected rational expressions were considered only as expressions defining trace languages. In this paper we study the class of flat languages defined by this kind of rational expressions. We consider regular languages inducing recognizable trace languages and its subclasses: languages of finite ranks and star-connected languages. Main results are the following: rank of any star-connected language is finite; any star-connected language has an automaton with connected simple cycles; two pumping lemmas for …star-connected languages. Moreover, we show that none of the investigated classes is closed under complement and that the class of languages of finite ranks is not closed under intersection. Finally, we briefly mention some decision problems and formulate several open questions. Show more

Keywords: trace language, star-connected rational expressions, finite automata

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 93-105, 2005

Authors: Kryvyy, Sergiy | Matvyeyeva, Lyudmila | Lopatina, Mariya

Article Type: Research Article

Abstract: Formal Methods are a set of methods and tools based on mathematical modeling and formal logic that are used to specify and verify requirements and architecture of hardware or software systems. They can also include means of automatic proving of key properties of designed software or hardware systems. In this paper automatic system is presented which specifies formally and verify designed software or hardware system specified in MSC language. Automatic system is represented as technological process …that applies the formal modeling technique of Petri nets and is based on linear algebra methods of analysis, namely, solving the systems of linear equations over the set of natural numbers, in order to research the properties of a system under design. The system is first modeled as a Petri net, and then this model is analyzed. The understanding of the system which results from the analysis will lead to a hopefully errorless system. Show more

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 107-120, 2005

Authors: Kudlek, Manfred

Article Type: Research Article

Abstract: It is demonstrated that the introduction of probability into Petri nets increases their power, in particular for their reachability sets. To achieve this the definition of accepted languages by probabilistic finite automata or probabilistic Turing machines with complexity restriction has to be modified.

Citation: Fundamenta Informaticae, vol. 67, no. 1-3, pp. 121-130, 2005

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