PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 11

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Levels of Persistency in Place/Transition Nets
Barylska K., Ochmański E.
Fundamenta Informaticae
|
2009
|
Vol. 93, nr 1-3
33-43
EN
The notion of persistency, based on the rule "no action can disable another one" is one of the classical notions in concurrency theory. We propose two ways of generalization of this notion: the first is "no action can kill another one" and the second "no action can kill another enabled one". We study the three notions in the context of place/transition nets, the fundamental class of Petri nets. We prove that the three classes of persistency form an increased strict hierarchy. The final section of the paper deals with decision problems about persistency. We show that the set reachability problem is decidable for rational convex sets, and using this result we prove that all kinds of persistency are decidable in the class place/transition nets.
2
Content available remote On Trace-Expressible Behaviour of Petri Nets
Jółkowska J., Ochmański E.
Fundamenta Informaticae
|
2008
|
Vol. 85, nr 1-4
281-295
EN
We propose a trace-based approach to description behaviours of concurrent systems. First, we define the independency relation induced by arbitrary transition system, forming this way an asynchronous transition system. Then we introduce the notion of traceability of transition systems and study some decision problems, related to computing independency and deciding traceability for basic classes of Petri nets. Main results: traceability is decidable for place/transition nets and undecidable in broader classes of nets - inhibitor, reset and transfer nets
3
Content available remote On Ethics of Mazurkiewicz Traces
Ochmański E., Pieckowska J.
Fundamenta Informaticae
|
2007
|
Vol. 80, nr 1-3
259-272
EN
We extend the well-known hierarchy ∞-fair ⊆0-fair ⊆ just for sequences (sequential computations) to that of traces (concurrent processes). The fairness hierarchy for traces is similar, but more involved than for sequences. We study this hierarchy, first in general, abstracting from concrete concurrent system, then for basic classes of Petri nets - elementary and place/transition nets. Finally, we define the fairness notions in a non-interleaving way and compare them with the former ones.
4
Content available remote Trace Nets and Conflict-free Computations
Ochmański E., Pieckowska J.
Fundamenta Informaticae
|
2006
|
Vol. 72, nr 1-3
311-321
EN
Trace nets are a generalization of elementary nets, proposed by Badouel and Darondeau. They admit phenomena, unknown in traditional nets. For instance, in trace nets does not hold the "diamond property". For this reason, we propose a more precise definition of conflict, applicable to trace nets, and study occurrences of conflicts and existence of conflict-free runs in such nets. Main result of the paper says that any just computation in a trace net, starting from a conflict state, contains a conflict step. This result allows to construct an algorithm, selecting only conflict-free just computations from among all computations of a given net. All results of the paper hold for elementary nets, as they are a subclass of trace nets.
5
Content available remote Star-free Star and Trace Languages
Ochmański E., Stawikowska K.
Fundamenta Informaticae
|
2006
|
Vol. 72, nr 1-3
323-331
EN
The paper deals with star-free languages in free monoids and trace monoids. We introduce the notion of star-free star, fundamental for this paper, and show that the classes of star-free languages and star-free star languages coincide. Then, using this result, we obtain a general characterization of star-free trace languages, containing a result of Guaiana/Restivo/Salemi (star-free = aperiodic in trace monoids), originally proved in a more involved, combinatorial way.
6
Content available remote On Star-Connected Flat Languages
Klunder B., Ochmański E., Stawikowska K.
Fundamenta Informaticae
|
2005
|
Vol. 67, nr 1-3
93--105
EN
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.
7
Content available remote Best Fairness Hierarchy in Elementary Nets
Ochmański E.
Fundamenta Informaticae
|
2004
|
Vol. 60, nr 1-4
237--250
EN
The fairness hierarchy and conspiracies, the notions introduced by Best, are studied in the context of elementary nets. Proving that sequential as well as persistent systems are conspiracy-free, we indicate two main roots of conspiracies: distributed memory and conflicts. Using the notion of marking-fairness, due to Merceron, we prove that T0-fairness + M0-fairness = T∞-fairness. This result gives a method of a local control ensuring globally fair executions. Next we show how to check, if a given elementary net is conspiracy-free, and prove the obtained criterion to be effectively decidable. Finally, we give a characterization of live concurrent systems, using the notion of ∞ -fairness.
8
On conflict-free executions of elementary nets
Ochmański E.
Systems Science
|
2001
|
Vol. 27, nr 2
89-105
EN
The paper deals with analysis of elementary Petri nets with respect to possibilities of avoiding conflicts during their executions. There are two main aims of the paper. The first is to find a method of checking if a net is conflict-avoidable (i.e., if it possesses a conflict-free fair run). The second is to find a method of rebuilding any net to a totally conflict-avoidable net (i.e., a net possessing a conflict-free fair run in every one process) with the same behaviour. The main results are the following: 1. The proof of decidability, for elementary nets, of the problem of existence of a conflict-avoidable fair process (and an algorithm producing all fair runs). 2. Construction, for an arbitrary given elementary net, of a totally conflict-avoidable net with the same behaviour. The net, completed this way, has the same behaviour as the original one. Moreover, it is totally conflict-avoidable, and its execution may be supervised (in order to ensure conflict-freeness) by the reduced case graph built by the algorithm of the former section.
9
Content available remote On conflict-free executions of elementary nets
Ochmański E.
Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
|
2000
|
nr 921
1-12
EN
The paper deals with analysis of elementary Petri nets with respect to possibilities of avoiding conflicts during their executions. In concurrent systems, unlike to the sequential ones, avoiding of potential conflicts is not impossible. The basic notion of the paper is the notion of fairness, in sequential (fair run) and concurrent (fair process) versions. Main results: 1. The proof of decidability, for elementary nets, of problem of existence of a conflict-avoidable fair process (and an algorithm producing all fair runs) and 2. Construction, for arbitrary given elementary net, a conflict-avoidable net with the same behaviour.
PL
Tematem pracy jest analiza elementarnych sieci Petriego pod katem mozliwości unikania sytuacji konfliktowych w trakcie ich działania. W systemach współbieżnych, w odróżnieniu od sekwencyjnych, unikanie potencjalnych konfliktów nie jest niemożliwe. Podstawowym pojęciem jest pojęcie uczciwości (fairness), zarówno w wersji sekwencyjnej (uczciwy przebieg liniowy), jak i współbieżnej (uczciwy proces). Najważniejsze wyniki pracy to: 1. Dowód rozstrzygalności problemu istnienia dla danej sieci elementarnej, bezkonfliktowego procesu uczciwego (wraz z algorytmem produkującym wszystkie uczciwe przebiegi) i 2. Konstrukcja dla dowolnej danej sieci elementarnej, sieci potencjalnie bezkonfliktowej o tym samym zachowaniu.
10
Content available remote Regular morphisms on semicommutations
Ochmański E.
Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
|
1998
|
nr 850
3-16
EN
Each semicommutation (A, q) determines the class REG (A) - the family of all q-closed and regular subsets of A*. Let (A, q) and B, g) be two semicommutations. A morphism f:A*->B* is said to be regular if and only if f (f(L)) REG (B) whenever L REG (A). A characterization of regular semicommutations (the case A=B and f=id) was given in [OW93]. In this paper we prove regularity of some special class of morphism - path-preserving morphisms. Using this result and the former characterization of regular semicommutations we obtain a criterion of regularity for the class of injective morphisms. Finally, we prove quite weak sufficient condition of regularity for arbitrary morphisms. We do not know, if the condition is also a necessary one.
PL
Każda półprzemienność (A, q) wyznacza klasę REG (A) - rodzinę wszystkich q-domkniętych i regularnych podzbiorów A*. Jeśli (A, q) i (B, g) są dwoma półprzemiennościami, to morfizm f:A*->B* nazywamy regularnym wtedy i tylko wtedy, gdy dla każdego L REG (A) domknięcie jego obrazu f (f(L)) należy do REG (B). Przypadek regularnych półprzemienności (A=B i f=id) został scharakteryzowany w [OW93]. W tej pracy pokazujemy regularność pewnej szczególnej klasy morfizmów, mianowicie morfizmów zachowujących ścieżki zależności. Wynik ten, w połączeniu ze wzmiankowaną wyżej charakteryzacją regularnych półprzemienności, pozwala sformułować i udowodnić kryterium regularności dla morfizmów różnowartościowych. Na zakończenie pokazujemy pewien warunek wystarczający dla regularności morfizmów. Pozostaje pytaniem otwartym, czy warunek ten jest również konieczny.
11
Content available remote Petri nets with weak conflicts : a proposal of classification
Ochmański E.
Prace Instytutu Podstaw Informatyki Polskiej Akademii Nauk
|
1998
|
nr 866
3-22
EN
The paper deals with theoretical aspects of some practical problems about Petri nets: how to avoid conflicts and when is it possible? We are studying the class of Petri nets, which can be implemented without an external conflict resolving supervisor. Such nets are named weakly conflicting, and conflicts appearing in them are said to be weak. We investigate properties of nets, with respect to conflicts, and propose a classification of them. Then we prove the proposed classes of nets form a partially ordered hierarchy.
PL
Praca zajmuje się teoretycznymi aspektami pewnych praktycznych problemów dotyczących sieci Petriego: jak unikać konfliktów i kiedy jest to możliwe? Badamy klasę sieci, które mogą być implementowane bez mechanizmu rozstrzygającego konflikty. Sieci takie nazywamy słabo konfliktowymi, a konflikty w nich występujące słabymi konfliktami. Badamy własności sieci względem konfliktów i proponujemy pewną ich klasyfikację. Dowodzimy, że zdefiniowane klasy sieci tworzą częściowo uporządkowaną hierarchię.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.