Wyniki wyszukiwania - BazTech

1

Generation of synchronizing state machines from a transition system: A region-based approach

Teren Viktor, Cortadella Jordi, Villa Tiziano

International Journal of Applied Mathematics and Computer Science

|

2023

|

Vol. 33, no. 1

133--149

EN

Transition systems (TSs) and Petri nets (PNs) are important models of computation ubiquitous in formal methods for modeling systems. A crucial problem is how to extract, from a given TS, a PN whose reachability graph is equivalent (with a suitable notion of equivalence) to the original TS. This paper addresses the decomposition of transition systems into synchronizing state machines (SMs), which are a class of Petri nets where each transition has one incoming and one outgoing arc. Furthermore, all reachable markings (non-negative vectors representing the number of tokens for each place) of an SM have only one marked place with only one token. This is a significant case of the general problem of extracting a PN from a TS. The decomposition is based on the theory of regions, and it is shown that a property of regions called excitation-closure is a sufficient condition to guarantee the equivalence between the original TS and a decomposition into SMs. An efficient algorithm is provided which solves the problem by reducing its critical steps to the maximal independent set problem (to compute a minimal set of irredundant SMs) or to satisfiability (to merge the SMs). We report experimental results that show a good trade-off between quality of results vs. computation time.

2

Reaction Systems and Enabling Equivalence

Kleijn Jetty, Koutny Maciej, Mikulski Łukasz

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

261--277

EN

Reaction systems were introduced in order to provide an abstract model for the study of the biochemical processes that take place in the living cell. Processes of this kind are the result of the interactions between reactions and may be influenced by the environment. Thus, reaction systems can be considered as a model of (interactive) computation. In previous works, various equivalences defined directly on reaction systems and processes had been proposed and compared. These equivalences were all based on functional equivalence that compares a system’s behaviour at every stage of its execution. In this paper, in contrast, we investigate enabling equivalence which focuses on the system behaviour only in specific stages of its evolution, namely those where all of its reactions are active. We discuss the effect of such an approach and, in particular, its relationship to a transition system representation of the system’s behaviour.

3

Slime mould games based on rough set theory

Pancerz K., Schumann A.

International Journal of Applied Mathematics and Computer Science

|

2018

|

Vol. 28, no. 3

531--544

EN

We define games on the medium of plasmodia of slime mould, unicellular organisms that look like giant amoebae. The plasmodia try to occupy all the food pieces they can detect. Thus, two different plasmodia can compete with each other. In particular, we consider game-theoretically how plasmodia of Physarum polycephalum and Badhamia utricularis fight for food. Placing food pieces at different locations determines the behavior of plasmodia. In this way, we can program the plasmodia of Physarum polycephalum and Badhamia utricularis by placing food, and we can examine their motion as a Physarum machine—an abstract machine where states are represented as food pieces and transitions among states are represented as movements of plasmodia from one piece to another. Hence, this machine is treated as a natural transition system. The behavior of the Physarum machine in the form of a transition system can be interpreted in terms of rough set theory that enables modeling some ambiguities in motions of plasmodia. The problem is that there is always an ambiguity which direction of plasmodium propagation is currently chosen: one or several concurrent ones, i.e., whether we deal with a sequential, concurrent or massively parallel motion. We propose to manage this ambiguity using rough set theory. Firstly, we define the region of plasmodium interest as a rough set; secondly, we consider concurrent transitions determined by these regions as a context-based game; thirdly, we define strategies in this game as a rough set; fourthly, we show how these results can be interpreted as a Go game.

4

A note on coherent arthomodular posets

Borzyszkowski A.

Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk

|

2004

|

Nr 981

1-14

EN

The paper studies the properties of orthomodular posets. The interest comes from the fact, that the set of all regions of a 2-structure (a transi-tion system) is a coherent orthomodular poset. This algebraic structure is gaining the importance in the area of distributed systems. In fact, there is a conjucture about the duality between the category of orthomodular posets and the category of 2-structures. We show in the paper how to close to coherence an arbitrary orthomodular poset and prove the universality of such a closure.

PL

Praca poświęcona jest badaniu zbiorów uporządkowanych spełniających warunek ortomodularności. Zainteresowanie takimi zbiorami wynika z faktu, że zbiór regionów 2-struktury (systemu tranzycji) jest takim właśnie zbiorem, spełniającym dodatkowo warunek koherencji. Powyższa struktura algebraiczna występuje w ostatnich badaniach systemów rozproszonych. Istnieje hipoteza o dualności pomiędzy kategorią porządków ortomodularnych a kategorią 2-struktur. W niniejszej pracy pokazujemy istnienie domknięcia dowolnego porządku orthomodularnego do koherentnego oraz dowodzimy uniwersalności takiej konstrukcji.