Wyniki wyszukiwania - Biblioteka Nauki

1

Liveness of Safe Object Nets

100%

Köhler-Bußmeier M. , Heitmann F.

|

2011

|

tom Vol. 112, nr 1

73-87

EN

In this paper we study the complexity of the liveness problem for safe Elementary Object Nets (EOS). Object nets are Petri nets which have Petri nets as tokens. They are called elementary if the net system has a two levelled structure. The concept of safeness bounds the number of tokens which may reside on a place. PSPACE-hardness of the liveness problemfor safe EOS directly follows fromthe related result for safe p/t nets. We then devise a polynomial space algorithmfor this problem and indeed for every property that can be expressed in the temporal logic CTL.

2

A Survey of Decidability Results for Elementary Object Systems

70%

Köhler-Bußmeier M.

Fundamenta Informaticae

|

2014

|

tom Vol. 130, nr 1

99--123

EN

This contribution presents recent results on Elementary Object Systems (EOS). Object nets are Petri nets which have Petri nets as tokens – an approach known as the nets-within-nets paradigm. In this work we study the relationship of EOS to existing Petri net formalisms. It turns out that EOS are equivalent to counter programs. But even for the restricted subclass of conservative EOS reachability and liveness are undecidable problems. On the other hand for other properties like boundedness are still decidable for conservative EOS. We also study the sub-class of generalised state machines, which is worth mentioning since it combines decidability of many theoretically interesting properties with a quite rich practical modelling expressiveness.

3

Detection of deadlocks and traps in Petri nets by means of Thelen's prime implicant method

70%

Węgrzyn A. , Karatkevich A. , Bieganowski J.

International Journal of Applied Mathematics and Computer Science

|

2004

|

tom 14

|

nr 1

113-121

EN

A new method of detecting deadlocks and traps in Petri nets is presented. Deadlocks and traps in Petri nets can be represented by the roots of special equations in CNF form. Such equations can be solved by using the search tree algorithm proposed by Thelen. In order to decrease the tree size and to accelerate the computations, some heuristics for Thelen's method are presented.

4

On Liveness and Reversibility of Equal-Conflict Petri Nets

60%

Hujsa T. , Delosme J.-M. , Munier-Kordon A.

Fundamenta Informaticae

|

2016

|

tom Vol. 146, nr 1

83--119

EN

Weighted Petri nets provide convenient models of many man-made systems. Real applications are often required to possess the fundamental Petri net properties of liveness and reversibility, as liveness preserves all the functionalities (fireability of all transitions) of the system and reversibility lets the system return to its initial state (marking) using only internal operations. Characterizations of both behavioral properties, liveness and reversibility, are known for wellformed weighted Choice-Free and ordinary Free-Choice Petri nets, which are special cases of Equal-Conflict Petri nets. However, reversibility is not well understood for this larger class, where choices must share equivalent preconditions, although characterizations of liveness are known. In this paper, we provide the first characterization of reversibility for all live Equal-Conflict Petri nets by extending, in a weaker form, a known condition that applies to the Choice-Free and Free-Choice subclasses. We deduce the monotonicity of reversibility in the live Equal-Conflict class. We also give counter-examples for other classes where the characterization does not hold. Finally, we focus on well-formed Equal-Conflict Petri nets, for which we offer the first polynomial sufficient conditions for liveness and reversibility, contrasting with the previous exponential time conditions.

5

On Promptness in Parity Games

60%

Mogavero F. , Murano A. , Sorrentino L.

Fundamenta Informaticae

|

2015

|

tom Vol. 139, nr 3

277--305

EN

Parity games are infinite-duration two-player turn-based games that provide powerful formal-method techniques for the automatic synthesis and verification of distributed and reactive systems. This kind of game emerges as a natural evaluation technique for the solution of the μ- calculus model-checking problem and is closely related to alternating ω-automata. Due to these strict connections, parity games are a well-established environment to describe liveness properties such as “every request that occurs infinitely often is eventually responded”. Unfortunately, the classical form of such a condition suffers from the strong drawback that there is no bound on the effective time that separates a request from its response, i.e., responses are not promptly provided. Recently, to overcome this limitation, several variants of parity game have been proposed, in which quantitative requirements are added to the classic qualitative ones. In this paper, we make a general study of the concept of promptness in parity games that allows to put under a unique theoretical framework several of the cited variants along with new ones. Also, we describe simple polynomial reductions from all these conditions to either Büchi or parity games, which simplify all previous known procedures. In particular, they allow to lower the complexity class of cost and bounded-cost parity games recently introduced. Indeed, we provide solution algorithms showing that determining the winner of these games is in UPTIME ∩ COUPTIME.

6

On topological hierarchies of temporal properties

60%

Baier C. , Kwiatkowska M.

|

2000

|

tom Vol. 41, Nr 3

259-294

EN

The classification of properties of concurrent programs into safety and liveness was first proposed by Lamport. Since then several characterizations of hierarchies of properties have been given, see e.g.; this includes syntactic characterizations (in terms classes of formulas of logics such as the linear temporal logic) as well as extensional (as sets of computations in some abstract domain). The latter often admits a topological characterization with respect to the natural topologies of the domain of computations. We introduce a general notion of a linear time model of computation which consists of partial and completed computations satisfying certain axioms. The model is endowed with a natural topology. We show that the usual topologies on strings, Mazurkiewicz traces and pomsets arise as special cases. We then introduce a hierarchy of properties including safety, liveness, guarantee, response and persistence properties, and show that our definition subsumes the hierarchies of: Alpern & Schneider ; Chang, Manna & Pnueli; and Kwiatkowska, Peled & Penczek. Syntactic characterizations of the properties in the hierarchy in terms of temporal logic are also studied.

7

Blackness as medium : body in contemporary theatre practice and theory

60%

Sajewska D. , Sosnowska D.

Theatralia: Revue současného myšlení o divadelní kultuře (Theatralia: The revue of contemporary thought on theatre culture)

|

2016

|

tom 19

|

nr 2

91-102

EN

Our text presents the theoretical approach to the problems of body and technology in stage performance. The starting point is the status of the categories such as presence, ephemerality, immediacy of the (theatre) performance, radically undermined in the texts of performance studies scholars such as Rebecca Schneider, Amelia Jones or Philip Auslander. Utilizing examples of performances from young Polish theatre: Krzysztof Garbaczewski (b. 1983) and Radosław Rychcik (b. 1981), we juxtapose two functioning models of the body-technology relation on stage. The first – represented by Garbaczewski – is based on an understanding of the body as always mediated. It multiplies (undermines) the body's presence by use of audio-visual means. The second – Rychcik's case – is to push the theatrical presence of the body to the absolute maximum. In this case, the audio-visual layer is used to build a strong opposition to the actor's stage presence. The two examples are used to propose a new theoretical approach. We show that such stage phenomena are not only a sign of a (technological) reality shift, but also, a very important theoretical input in the understanding of theatre. We state that every single body on stage (no matter if consciously, as in Garbaczewski's case, or unconsciously as in the Rychcik's case) is already mediated and the use of technological tools is a way to play with this specific character of theatre corporeality. This broader perspective also incorporates elements of the political dimension of annexing media-mediated and media-manipulated corporeality, for it will follow the apparently transparent and natural dimension of such actions, whereby once again it will turn, as postulated by Jacques Rancière, aesthetic considerations into political considerations.

8

IL VALORE DELL’INCONTRO. ALCUNE CONSIDERAZIONI SU THE ARTIST IS PRESENT DI MARINA ABRAMOVIĆ

51%

Woźniak K.

|

tom 54

|

nr 2(22): Literatura i Język

123-129

EN

The purpose of the article is to interpret Marina Abramović’s project – The Artist Is Present – within the theories of liveness and encounter. First of all, we define post-mediatic culture referring to Piotr Celiński’s proposals and the term ‘encounter’ according to Adam Węgrzecki. Finally, we propose some considerations on the encounter as a methodological approach to the phenomena whose main characteristic is liveness (Peggy Phelan and Philip Auslander). Finally, we pass to the analysis of the performance of Marina Abramović The Artist Is Present based on the considerations made previously.

9

Detection of deadlocks and traps in Petri nets by means of Thelen's prime implicant method

51%

Węgrzyn A. , Karatkevich A. , Bieganowski J.

International Journal of Applied Mathematics and Computer Science

|

2004

|

tom Vol. 14, no 1

113-121

EN

A new method of detecting deadlocks and traps in Petri nets is presented. Deadlocks and traps in Petri nets can be represented by the roots of special equations in CNF form. Such equations can be solved by using the search tree algorithm proposed by Thelen. In order to decrease the tree size and to accelerate the computations, some heuristics for Thelen's method are presented.

10

Synthesis of Live and Bounded Persistent Systems

51%

Best E. , Devillers R.

Fundamenta Informaticae

|

2015

|

tom Vol. 140, nr 1

39--59

EN

This paper presents a dedicated Petri net synthesis algorithm for the case that a transition system is finite, live, and persistent. In particular, the paper delineates exactly when and how a structurally persistent net may be constructed, by crystallising, out of a general region-theoretic approach, a minimised set of simplified systems of linear inequalities. This extends previous results where reversibility, instead of liveness, played an important role.

11

Properties and analysis of [alfa]-nets

41%

Karatkevich A.

Informatyka Teoretyczna i Stosowana

|

2005

|

tom R. 5, nr 8

53-64

EN

A restricted class of Petri nets equivalent to [alfa]-nets - the extended free choice nets with single-token initial marking - is considered, which corresponds to structnre of paralleI aotomata and parallel logical control algorithms. For nets of this class the dependence between such behavioural properties as liveness, safeness and reversibility is studied. It is shown that a net belonging to that class is live and sale if and only if it is reversible and the net graph is strongly connected. Sofie other results are proven on relation among reversibility and other net properties. Based on the obtained results, applying one of the reduced state space generation methods known as the stubborn set method to [alfa]-nets is considered. It is shown, that redoced reachability graph obtained by the method for such net allows to check whether the net is well-formed (live and sale); soch graph may be much smaller than the complete reachability graph of the net. Experimental results are presented.

PL

Dla podklasy sieci Petriego, ekwiwalentnej [alfa]-sieciom - rozszerzonym sieciom swobodnego wyboru z jednym znacznikiem w znakowaniu początkowym - bada się zależność między niektórymi istotnymi własnościami behawioralnymi. Pokazane, że sieć, należąca do tej klasy, jest żywą i bezpieczną wtedy i tylko wtedy, gdy jest ona powtarzalna i silnie spójna. Przedstawione są niektóre inne rezultaty, związane z zależnościami między powtarzalnością i innymi własnościami sieci. Na podstawie otrzymanych rezultatów rozważa się zastosowanie metody upartych zbiorów (stubborn set method) do [alfa]-sieci; pokazane, że zbudowany za pomocą tej metody częściowy graf osiągalności dla takiej sieci zawiera informacje, pozwalającą sprawdzić, czy sieć jest "dobrze zbudowana" (żywa i bezpieczna).

12

Completeness Results for Generalized Communication-free Petri Nets with Arbitrary Arc Multiplicities

41%

Mayr E. W. , Weihmann J.

|

tom Vol. 143, nr 3/4

355--391

EN

We investigate gcf-Petri nets, a generalization of communication-free Petri nets allowing arbitrary arc multiplicities, and characterized by the sole restriction that each transition has at most one incoming arc. We use canonical firing sequences with nice properties for gcf-PNs to show that the RecLFS, (zero-)reachability, covering, and boundedness problems of gcf-PNs are in PSPACE. By simulating PSPACE-Turing machines by gss-PNs, a subclass of gcf-PNs where additionally all transitions have at most one outgoing arc, we ultimately obtain PSPACE-completess for these problems in case of gss-PNs or gcf-PNs. Additionally, we prove PSPACE-completeness for the liveness problem of gcf-PNs. Last, we show PSPACE-hardness as well as a doubly exponential space upper bound for the containment and equivalence problems of gss-PNs or gcf-PNs.