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