Fundamenta Informaticae - Volume 47, issue 3-4

Authors: Burkhard, Hans-Dieter | Starke, Peter | Czaja, Ludwik

Article Type: Other

Keywords:

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. i-i, 2001

Authors: Barbuti, Roberto | De Francesco, Nicoletta | Tesei, Luca

Article Type: Research Article

Abstract: In this paper we propose a model, timed automata with non-instantaneous actions, which allows representing in a suitable way real-time systems. Timed automata with non-instantaneous actions extend the timed automata model by dropping the assumption that actions are instantaneous: in our model an action can take some time to be completed. We investigate the expressiveness of the new model, comparing it with classical timed automata. In particular, we study the set of timed languages which can …be accepted by timed automata with non-instantaneous actions. We prove that timed automata with non-instantaneous actions are more expressive than timed automata and less expressive than timed automata with ϵ edges. Moreover we define the parallel composition of timed automata with non-instantaneous actions. We point out how the specification by means of a parallel timed automaton with non-instantaneous actions is, in some cases, more convenient to represent reality. Show more

Keywords: real-time systems, timed automata, timed languages

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 189-200, 2001

Authors: Burkhard, Hans-Dieter

Article Type: Research Article

Abstract: Notions of similarity and distance play an important role in informatics. Different disciplines have developed their own treatment of related measures. We consider this problem under the viewpoint of Case Based Reasoning. While distance and similarity can be considered to be formally equivalent, there exist some differences concerning their intuitive use which have impact to the composition of global measures from local ones.

Keywords: similarity, distance, case based reasoning, retrieval

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 201-215, 2001

Authors: Czaja, Ludwik | Kudlek, Manfred

Article Type: Research Article

Abstract: The definition of process admitted here follows the line developed for elementary (1-safe) Petri nets and published in [Cza 99], [Cza 2000a], [Cza-Kud 2000]. It pertains not to any particular net, thus allows for collecting processes into arbitrary sets, i.e. process languages, and for asking questions like: for a given process language decide if there exists a Place/Transition net and if yes, contruct it (synthesis). The collection of all process languages is a semantic domain for …Place/Transition nets. ω-process languages contain both finite and infinite processes. The main problems pursued are analysis, synthesis and iteration lemmata for ω-process languages. Surprisingly, the problems enjoy much simpler solutions for processes generated by P/T nets than generated by elementary nets. Show more

Keywords: Place/Transition Petri net, process, ω-process language, analysis, synthesis, iteration lemmata

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 217-229, 2001

Authors: Esparza, Javier | Schröter, Claus

Article Type: Research Article

Abstract: We study four solutions to the reachability problem for 1-safe Petri nets, all of them based on the unfolding technique. We define the problem as follows: given a set of places of the net, determine if some reachable marking puts a token in all of them. Three of the solutions to the problem are taken from the literature [McM92,Mel98,Hel99], while the fourth one is first introduced here. The new solution shows that the problem can be solved in time …O(n^k), where $n$ is the size of the prefix of the unfolding containing all reachable states, and $k$ is the number of places which should hold a token. We compare all four solutions on a set of examples, and extract a recommendation on which algorithms should be used and which ones not. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 231-245, 2001

Authors: Farwer, Bernd

Article Type: Research Article

Abstract: In recent years many authors have come up with definitions of object Petri nets. They can be divided into two main classes: those that try to model object-orientation within a framework of Petri nets, and those modelling the token objects of an environment net by Petri nets but do not follow the paradigm of object-orientation. We compare some aspects of the latter kind with the foundations of Linear Logic and Linear Logic Petri nets, establishing some …simulations between the formalisms. Show more

Keywords:

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 247-258, 2001

Authors: Haar, Stefan

Article Type: Research Article

Abstract: We study independence of events in the unfoldings of Petri nets, in particular indirect influences between concurrent events: Confusion in the sense of Smith [11] and weak interference. The role of structural (conflict) clusters is investigated, and a new unfolding semantics based on clusters motivated and introduced.

Keywords: Concurrency, occurrence nets, unfoldings, confusion, conflict clusters

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 259-270, 2001

Authors: Lanotte, Ruggero | Maggiolo-Schettini, Andrea | Tini, Simone | Peron, Adriano

Article Type: Research Article

Abstract: The paper pursues the investigation of Timed Cooperating Automata (TCAs) by studying transformations which are suggested as means for stepwise TCA construction.

Keywords: Timed automata, cooperating automata, stepwise development, retiming

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 271-282, 2001

Authors: Lomazova, Irina A.

Article Type: Research Article

Abstract: Nested Petri nets (NP-nets) is a formalism for modeling hierarchical multi-agent systems. Tokens in nested Petri nets are elements represented by nets themselves. The paper continues investigating semantic properties of NP-nets, started in [10], where two-level NP-nets were studied. Here we consider multi-level and recursive NP-nets, for which decidability of termination and some other properties are proved. A comparison of NP-nets with other Petri net models is given.

Keywords: hierarchical multi-agent systems, nested Petri nets, well-structured transition systems, decidability

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 283-293, 2001

Authors: Neuendorf, Klaus-Peter | Lee, Dong-Ho | Kiritsis, Dimitris | Xirouchakis, Paul

Article Type: Research Article

Abstract: This paper considers the application of Petri nets with timestamps to the problem of disassembly scheduling with parts commonality, which is the problem of determining time and quantity of ordering the used product to fulfill the demands of individual disassembled parts. Unlike the simple case, parts commonality creates dependencies of components and makes them difficult to solve. A comparison of methods using an example problem from a previous research shows that the method suggested in this …paper is much simpler and more extendable than the previous one. Also, we show that the solutions obtained from the previous algorithm are not optimal in general. Show more

Keywords: Disassembly, scheduling, time Petri nets

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 295-306, 2001

Authors: Peters, James F. | Ramanna, S. | Borkowski, M. | Skowron, Andrzej | Suraj, Zbigniew

Article Type: Research Article

Abstract: This paper considers models of sensors, filters, and sensor fusion with Petri nets defined in the context of rough sets. Sensors and filters are fundamental computational units in the design of systems. The intent of this work is to construct Petri nets to simulate conditional computation in approximate reasoning systems, which are dependent on filtered input from selected sensors considered relevant in problem solving. In this paper, coloured Petri nets provide a computational framework for the …definition of a family of Petri nets based on rough set theory. Sensors are modeled with what are known as receptor processes in rough Petri nets. Filters are modeled as Łukasiewicz guards on some transitions in rough Petri nets. A Łukasiewicz guard is defined in the context of multivalued logic. Łukasiewicz guards are useful in culling from a collection of active sensors those sensors with the greatest relevance in a problem-solving effort such as classification of a "perceived" phenomenon in the environment of an agent. The relevance of a sensor is computed using a discrete rough integral. The form of sensor fusion considered in this paper consists in selecting only those sensors considered relevant in solving a problem. The contribution of this paper is the modeling of sensors, filters, and fusion in the context of receptor processes, Łukasiewicz guards, and rough integration, respectively. Show more

Keywords: approximation, enabling, filter, fusion, guard, multivalued logic, Petri net, rough measure, rough integral, rough sets, sensor

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 307-323, 2001

Authors: Schmidt, Karsten

Article Type: Research Article

Abstract: Given a (possibly partially defined) state, all count vectors of transition sequences reaching that state are solutions to a corresponding Petri net state equation. We propose a search strategy where sequences corresponding to a minimal solution of the state equation are explored first. Then step by step the search space is relaxed to arbitrary count vectors. This heuristics relies on the observation that in many (though provably not in all) cases, minimal solutions of the state …equation can be realized as a firing sequence. If no target state is reachable, either the state equation does not have solutions, or our search method would yield the full state space. We study the impact of the state equation on reachability, present an algorithm that exploits information from the state equation and discuss its application in stateless search as well as its combination with stubborn set reduction. Show more

Keywords: computer aided verification, Petri nets, reachability analysis, state equation

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 325-335, 2001

Authors: Skowron, Andrzej | Stepaniuk, Jaroslaw

Article Type: Research Article

Abstract: Information sources provide us with granules of information that must be transformed, analyzed and built into structures that support problem solving. One of the main goals of information granule calculi is to develop algorithmic methods for construction of complex information granules from elementary ones by means of available operations and inclusion (closeness) measures. These constructed complex granules represent a form of information fusion. Such granules should satisfy some constraints like quality criteria …or/and degrees of granule inclusion in (closeness to) a given information granule. Information granule decomposition methods are important components of those methods. We discuss some information granule decomposition methods. Show more

Keywords: rough set theory, information granulation, granular computing, information fusion, decomposition, pattern, schemes of approximate reasoning

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 337-350, 2001

Authors: Wróblewski, Jakub

Article Type: Research Article

Abstract: The problem of improving rough set based expert systems by modifying a notion of reduct is discussed. The notion of approximate reduct is introduced, as well as some proposals of quality measure for such a reduct. The complete classifying system based on approximate reducts is presented and discussed. It is proved that the problem of finding optimal set of classifying agents based on approximate reducts is NP-hard; the genetic algorithm is applied to find the suboptimal …set. Experimental results show that the classifying system is effective and relatively fast. Show more

Keywords: Rough sets, approximate reduct, voting

Citation: Fundamenta Informaticae, vol. 47, no. 3-4, pp. 351-360, 2001