Fundamenta Informaticae - Volume 43, issue 1-4

Authors: Lomazova, Irina A.

Article Type: Research Article

Abstract: Nested Petri nets is a formalism for modeling hierarchical multi-agent systems. Tokens in nested Petri nets are elements represented by nets themselves. Decidability of some crucial for verification problems shows that, in spite of their ”unflat” structure, nested Petri nets maintain significant properties of ordinary Petri nets. A comparison with some other Petri net models is given. The formalism allows generalization to a recursive case, when a nested Petri net may generate its own copy as its element. Two simple examples illustrate the approach.

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

DOI: 10.3233/FI-2000-43123410

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 195-214, 2000

Authors: Münch, Ines | Lindemann - v.Trzebiatowski, Gabriela

Article Type: Research Article

Abstract: Conceptual modeling is an important basis for developing general purpose systems for information and service management. In this paper, we present concepts for the analysis and design of a system of agents in which agents represent interests of individuals or groups. In particular, we develop a semantic model of agent domain knowledge by introducing analytical concepts for service scheduling which is the envisioned application of our prototypical system ChariTime.

Keywords: agent-oriented design, conceptual modeling, service scheduling

DOI: 10.3233/FI-2000-43123411

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 215-226, 2000

Authors: Nepomniaschaya, Anna S. | Dvoskina, Maria A.

Article Type: Research Article

Abstract: In this paper we propose a natural straight forward implementation of Dijkstra's shortest path algorithm on a model of associative parallel processors of the SIMD type with bit-serial (or vertical) processing (the STAR-machine). In addition, we show how to extend this implementation for restoring the shortest path from the source vertex to a given vertex. These algorithms of implementation are represented as the corresponding STAR procedures whose correctness is verified and time complexity is evaluated.

Keywords: Dijkstra's shortest path algorithm, the single-source shortest path problem, a directed weighted graph, associative parallel processing, time complexity

DOI: 10.3233/FI-2000-43123412

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 227-243, 2000

Authors: Penczek, Wojciech | Szreter, Maciej | Gerth, Rob | Kuiper, Ruurd

Article Type: Research Article

Abstract: The ”state explosion problem” can be alleviated by using partial order reduction techniques. These methods rely on expanding only a fragment of the full state space of a program, which is sufficient for verifying the formulas of temporal logics LTL−X or CTL−X* (i.e., LTL or CTL* without the next state operator). This is guaranteed by preserving either a stuttering maximal trace equivalence or a stuttering bisimulation between the full and the reduced state space. Since a stuttering bisimulation is much more restrictive than a stuttering maximal trace equivalence, resulting in less powerful reductions for CTL−X* , …we study here partial order reductions that preserve equivalences ”in-between”, in particular a stuttering simulation which is induced by the universal fragment of CTL:−X* , called ACTL−X* The reductions generated by our method preserve also branching simulation and weak simulation, but surprisingly, they do not appear to be included into the reductions obtained by Peled's method for verifying LTL−X properties. Therefore, in addition to ACTL−X* reduction method we suggest also an improvement of the LTL−X reduction method. Moreover, we prove that reduction for concurrency fair version of ACTL−X* is more efficient than for ACTL−X* . Show more

DOI: 10.3233/FI-2000-43123413

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 245-267, 2000

Authors: Peters, James F. | Skowron, Andrzej | Suraj, Zbigniew

Article Type: Research Article

Abstract: The paper deals with an automatic concurrent control design method derived from the specification of a discrete event control system represented in the form of a decision table. The main stages of our approach are: the control specification by decision tables, generation of rules from the specification of the system behavior, and converting rules set into a concurrent program represented in the form of a Petri net. Our approach is based on rough set theory [17].

DOI: 10.3233/FI-2000-43123414

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 269-290, 2000

Authors: Polkowski, Lech | Skowron, Andrzej

Article Type: Research Article

Abstract: Rough Mereology has been proposed as a paradigm for approximate reasoning in complex information systems. Its primitive notion is that of a predicate of rough inclusion which gives for any two entities of discourse the degree in which one of them is a part of the other. Rough Mereology may be regarded as an extension of Rough Set Theory as it proposes to argue in terms of similarity relations induced from a rough inclusion instead of reasoning in terms of more strict indiscernibility relations. Rough Mereology is also a generalization of Mereology i.e. a theory of reasoning based on the …notion of a part. Classical languages of mathematics are of two-fold kind: the language of set theory (naive or formal) expressing classes of objects as sets consisting of ”elements”, ”points” etc. suitable for objects perceived as built of ”atoms” and applied to structures perceived as discrete and the language of part relations suitable for e.g. continuous objects like solids, regions, etc. where two objects are related to each other by saying that one of them is a part of the other. Mereological theories for reasoning about complex structures are at the heart of Qualitative Spatial Reasoning. In this paper, we study basic aspects of Rough Mereology in Information Systems. Mereology makes the distinction between entities perceived as individuals (singletons), to which the part predicate may be applied, and entities perceived as distributive classes (sets, lists, general names etc.) of entities. This distinction is made formal and precise within Ontology i.e. Theory of Being based on the primitive notion of the copula is which is also a basic ingredient of theories for Spatial Reasoning. The practical aim of Ontology is to elaborate a system of concepts (notions, names, sets of entities) about which the reasoning is carried out. Therefore, we begin our study with an analysis of a simple rough set-based Ontology (the template ontology) in Information Systems and in this setting we present our approach to Mereology in Information Systems. In this framework we introduce Rough Mereology and we present some ways for defining rough inclusions. We demonstrate applications of Rough Mereology to approximate reasoning taking as the case subject Qualitative Spatial Reasoning. We address here some of its mereo-topological as well as mereo-geometrical aspects. Show more

Keywords: rough sets, information systems/tables, ontology, mereology, rough mereology, spatial reasoning, mereo-topology, mereo-geometry

DOI: 10.3233/FI-2000-43123415

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 291-320, 2000

Authors: Roch, Stephan

Article Type: Research Article

Abstract: Signal-event nets provide a modular modeling technique based on Petri nets. Actions of a module can be activated or can be prevented by another module through condition arcs. One-sided synchronization of modules is done by signal-events, which cause the execution of actions in steps. But due to condition arcs and signal-events simultaneous firing of steps may lead to markings, which are not reachable by conventional sequential interleaving. We give a criterion, in which situations simultaneous firing of steps can be safely omitted, without missing reachable markings.

Keywords: Discrete event systems, signal-event nets, reachability analysis

DOI: 10.3233/FI-2000-43123416

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 321-330, 2000

Authors: Schröter, Kay | Lindemann - v.Trzebiatowski, Gabriela | Fritsche, Lutz

Article Type: Research Article

Abstract: Fast and easy access to all relevant data is of most importance in medical diagnostics and therapy. Electronic patient records can fulfil these requirements much better than common paper-based records. This article describes the TBase2 system, an example of such an electronic patient record. It was developed in close cooperation with the Department of Nephrology at the university hospital Charité in Berlin. Due to its flexibility TBase2 can easily be adapted to the demands of other departments. Beside supporting the daily care for patients, TBase2 also gathers detailed data of high validity ideally suited for medical research.

Keywords: electronic patient record, web-based applications

DOI: 10.3233/FI-2000-43123417

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 343-353, 2000

Authors: Varpaaniemi, Kimmo

Article Type: Research Article

Abstract: The stubborn set method is one of the methods that try to relieve the state space explosion problem that occurs in state space generation. Spending some time in looking for “good” stubborn sets can pay off in the total time spent in generating a reduced state space. This article shows how the method can exploit tools that solve certain problems of logic programs. The restriction of a definition of stubbornness to a given state can be translated into a variable-free logic program. When a stubborn set satisfying additional constraints is wanted, the additional constraints should be translated, too. It is …easy to make the translation in such a way that each acceptable stubborn set of the state is represented by at least one stable model of the program, each stable model of the program represents at least one acceptable stubborn set of the state, and for each pair in the representation relation, the number of certain atoms in the stable model is equal to the number of enabled transitions of the represented stubborn set. So, in order to find a stubborn set which is good w.r.t. the number of enabled transitions, it suffices to find a stable model which is good w.r.t. the number of certain atoms. The article also presents a new NP-completeness result concerning stubborn sets. Show more

Keywords: reachability analysis, reduced state space generation, stubborn sets, variable-free logic programs, stable models, NP-completeness

DOI: 10.3233/FI-2000-43123418

Citation: Fundamenta Informaticae, vol. 43, no. 1-4, pp. 355-375, 2000