Wyniki wyszukiwania - BazTech

1

Causal reversibility in individual token interpretation of Petri Nets

Benamira Adel

Computer Science

|

2020

|

T. 21 (4)

489-511

EN

Causal reversibility in concurrent systems means that events that the origin of other events can only be undone after undoing its consequences. In opposition to backtracking, events that are independent of each other can be reversed in an arbitrary order; in other words, we have flexible reversibility with respect to a causality relationship. An implementation of individual token interpretation of Petri Nets (IPNs) has been proposed by Rob Van Glabbeek et al.; the present paper investigates a study of causal reversibility within IPNs. Given N as an IPN, by adding an intuitive firing rule to undo transitions according to the causality relationship, the coherence of N is assured; i.e., the set of all reachable states of N in the reversible version and that of the original one are identical. Furthermore, reversibility in N is flexible, and their initial state can be accessible in reverse from any state. In this paper, an approach for controlling causal-reversibility within IPNs is proposed.

2

Time-symmetry breaking in Hamiltonian mechanics. Part 2, A memoir for Berni Julian Alder [1925–2020],

Hoover Wm. G., Hoover C. G.

Computational Methods in Science and Technology

|

2020

|

Vol. 26, No. 4

101--110

EN

This memoir honors the late Berni Julian Alder, who inspired both of us with his pioneering development of molecular dynamics. Berni’s work with Tom Wainwright, described in the 1959 Scientific American [1], brought Bill to interview at Livermore in 1962. Hired by Berni, Bill enjoyed over 40 years’ research at the Laboratory. Berni, along with Edward Teller, founded UC’s Department of Applied Science in 1963. Their motivation was to attract bright students to use the laboratory’s unparalleled research facilities. In 1972 Carol was offered a joint LLNL employee-DAS student appointment at Livermore. Bill, thanks to Berni’s efforts, was already a Professor there. Berni’s influence was directly responsible for our physics collaboration and our marriage in 1989. The present work is devoted to two early interests of Berni’s, irreversibility and shockwaves. Berni and Tom studied the irreversibility of Boltzmann’s “H function” in the early 1950s [2]. Berni called shockwaves the “most irreversible” of hydrodynamic processes [3]. Just this past summer, in simulating shockwaves with time-reversible classical mechanics, we found that reversed Runge-Kutta shockwave simulations yielded nonsteady rarefaction waves, not shocks. Intrigued by this unexpected result we studied the exponential Lyapunov instabilities in both wave types. Besides the Runge-Kutta and Leapfrog algorithms, we developed a precisely-reversible manybody algorithm based on trajectory storing, just changing the velocities’ signs to generate the reversed trajectories. Both shocks and rarefactions were precisely reversed. Separate simulations, forward and reversed, provide interesting examples of the Lyapunov-unstable symmetry-breaking models supporting the Second Law of Thermodynamics. We describe promising research directions suggested by this work.

3

Compressible Baker Maps and Their Inverses : A Memoir for Francis Hayin Ree [1936–2020]

Hoover Wm. G.

Computational Methods in Science and Technology

|

2020

|

Vol. 26, No. 1

5--13

EN

This memoir is dedicated to the late Francis Hayin Ree, a formative influence shaping my work in statistical mechanics. Between 1963 and 1968 we collaborated on nine papers published in the Journal of Chemical Physics. Those dealt with the virial series, cell models, and computer simulation. All of them were directed toward understanding the statistical thermodynamics of simple model systems. Our last joint work is also the most cited, with over 1000 citations, “Melting Transition and Communal Entropy for Hard Spheres”, submitted 3 May 1968 and published that October. Here I summarize my own most recent work on compressible time-reversible two-dimensional maps. These simplest of model systems are amenable to computer simulation and are providing stimulating and surprising results.

4

Reversing Transitions in Bounded Petri Nets

Barylska K., Erofeev E., Koutny M., Mikulski Ł., Piątkowski M.

Fundamenta Informaticae

|

2018

|

Vol. 157, nr 4

341--357

EN

Reversible computation deals with mechanisms for undoing the effects of actions executed by a dynamic system. This paper is concerned with reversibility in the context of Petri nets which are a general formal model of concurrent systems. A key construction we investigate amounts to adding ‘reverse’ versions of selected net transitions. Such a static modification can severely impact on the behaviour of the system, e.g., the problem of establishing whether the modified net has the same states as the original one is undecidable. We therefore concentrate on nets with finite state spaces and show, in particular, that every transition in such nets can be reversed using a suitable set of new transitions.

5

On Deadlockability, Liveness and Reversibility in Subclasses of Weighted Petri Nets

Hujsa T., Devillers R.

Fundamenta Informaticae

|

2018

|

Vol. 161, nr 4

383--421

EN

Liveness, (non-)deadlockability and reversibility are behavioral properties of Petri nets that are fundamental for many real-world systems. Such properties are often required to be monotonic, meaning preserved upon any increase of the marking. However, their checking is intractable in general and their monotonicity is not always satisfied. To simplify the analysis of these features, structural approaches have been fruitfully exploited in particular subclasses of Petri nets, deriving the behavior from the underlying graph and the initial marking only, often in polynomial time. In this paper, we further develop these efficient structural methods to analyze deadlockability, liveness, reversibility and their monotonicity in weighted Petri nets. We focus on the join-free subclass, which forbids synchronizations, and on the homogeneous asymmetric-choice subclass, which allows conflicts and synchronizations in a restricted fashion. For the join-free nets, we provide several structural conditions for checking liveness, (non-)deadlockability, reversibility and their monotonicity. Some of these methods operate in polynomial time. Furthermore, in this class, we show that liveness, non-deadlockability and reversibility, taken together or separately, are not always monotonic, even under the assumptions of structural boundedness and structural liveness. These facts delineate more sharply the frontier between monotonicity and non-monotonicity of the behavior in weighted Petri nets, present already in the join-free subclass. In addition, we use part of this new material to correct a flaw in the proof of a previous characterization of monotonic liveness and boundedness for homogeneous asymmetric-choice nets, published in 2004 and left unnoticed.

6

The 2017 SNOOK PRIZES in Computational Statistical Mechanics

Hoover W. G., Hoover C. G.

Computational Methods in Science and Technology

|

2018

|

Vol. 24, No. 2

75--79

EN

The 2017 Snook Prize has been awarded to Kenichiro Aoki for his exploration of chaos in Hamiltonian 4 models. His work addresses symmetries, thermalization, and Lyapunov instabilities in few-particle dynamical systems. A companion paper by Timo Hofmann and Jochen Merker is devoted to the exploration of generalized Hénon-Heiles models and has been selected for Honorable Mention in the Snook-Prize competition.

7

On Liveness and Reversibility of Equal-Conflict Petri Nets

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

Fundamenta Informaticae

|

2016

|

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.

8

Time - Symmetry Breaking in Hamiltonian Mechanics

Hoover W. G., Hoover C. G.

Computational Methods in Science and Technology

|

2013

|

Vol. 19, No. 2

77--87

EN

Hamiltonian trajectories are strictly time-reversible. Any time series of Hamiltonian coordinates f q g satisfying Hamilton’s motion equations will likewise satisfy them when played “backwards”, with the corresponding momenta changing signs: {+p }→{-g}. Here we adopt Levesque and Verlet’s precisely bit-reversible motion algorithm to ensure that the trajectory reversibility is exact, with the forward and backward sets of coordinates identical. Nevertheless, the associated instantaneous Lyapunov instability, or “sensitive dependence on initial conditions” of “chaotic” (or “Lyapunov unstable”) bit-reversible coordinate trajectories can still exhibit an exponentially growing time-symmetry-breaking irreversibility ≃ eλt. Surprisingly, the positive and negative exponents, as well as the forward and backward Lyapunov spectra , {λforward(t) } and {λt backward(t) }, are usually not closely related, and so give four differing topological measures of “local” chaos. We have demonstrated this symmetry breaking for fluid shockwaves, for free expansions, and for chaotic molecular collisions. Here we illustrate and discuss this time-symmetry breaking for three statistical-mechanical systems, [i] a minimal (but still chaotic) one-body “cell model” with a four-dimensional phase space; [ii] relatively small colliding crystallites, for which the whole Lyapunov spectrum is accessible; [iii] a near-continuum inelastic collision of two larger 400-particle balls. In the last two of these pedagogical problems the two colliding bodies coalesce. The particles most prone to Lyapunov instability are dramatically different in the two time directions. Thus this Lyapunov-based symmetry breaking furnishes an interesting Arrow of Time.

9

Low-carbon power generation cycles : the feasibility of CO2 capture and opportunities for integration

Budzianowski W. M.

Journal of Power Technologies

|

2011

|

Vol. 91, nr 1

6-13

EN

Low-carbon power generation is receiving increasing interest due to climate warming concerns. The present article analyzes three low-carbon power cycles. The focus is on the feasibility of CO2 capture and opportunities for energy and mass integration. The first power cycle is a zero-carbon solid biomass fuelled multi-step gasification gas turbine power cycle involving multi-step solid biomass conversion, which is a more reversible process than one-step biomass combustion. The second zero-carbon coal-fired oxy-gasification steam chemical looping combustion gas turbine cycle benefits from: (i) improved cycle efficiency due to the increased reversibility of the chemical looping combustion process, (ii) cycle mass and energy integration due to the several recirculation loops involved, and (iii) extremely high CO2 capture rate due to the purity of the CO2/H2O mixture achieved at the outlet of a syngas reactor. The last power cycle - a biogas fuelled oxy-reforming fuel cell cycle - is superior in terms of the feasibility of CO2 capture, i.e. CO2 is captured from CO2-enriched streams, and due to the utilization of renewable biogas, negative net CO2 atmospheric emissions are achieved. It is concluded that high CO2 capture rates are feasible from pressurized CO2-enriched streams comprising either water or hydrogen, thus necessitating oxy-fuel power cycles. Opportunities for mass and energy integration are found to be greater in systems involving closed mass and energy recirculation loops. The discussions also emphasize that low-carbon power cycles could achieve minimized exergy losses by applying more reversible energy conversion processes.

10

Algorithm for queueing networks with multi-rate traffic

Iversen V. B., King-Tim K.

Advances in Electronics and Telecommunications

|

2011

|

Vol. 2, no. 3

3--7

EN

In this paper we present a new algorithm for evaluating queueing networks with multi-rate traffic. The detailed state space of a node is evaluated by explicit formulæ. We consider reversible nodes with multi-rate traffic and find the state probabilities by taking advantage of local balance. Theory of queueing networks in general, presumes that we have product form between the nodes. Otherwise, we have the state space explosion. Even so, the detailed state space of each node may become very large because there is no product form between chains inside a node. A prerequisite for product form is reversibility which implies that the arrival process and departure process are identical processes, for example state-dependent Poisson processes. This property is equivalent to reversibility. Due to product form, an open network with multi-rate traffic is easy to evaluate by convolution algorithms because the nodes behave as independent nodes. For closed queueing networks with multiple servers in every node and multi-rate services we may apply multidimensional convolution algorithm to aggregate the nodes so that we end up with two nodes, the aggregated node and a single node, for which we can calculate the detailed performance measures.

11

Problems in descriptions of hysteresis

Chwastek K.

Przegląd Elektrotechniczny

|

2010

|

R. 86, nr 4

24-27

EN

The idea of product model of hysteresis is presented. Some problems related to the description of reversible magnetization processes are discussed.

PL

Przedstawiono ideę modelu histerezy, w którym podatność różniczkowa jest iloczynem funkcji zależnej od magnetyzacji i sumy dwóch składników. Omówiono problemy związane z opisem procesów odwracalnych magnesowania.

12

Cryptosystem Based on Reversible Two-dimensional Cellular Automata

Wiśniewski A.

Studia Informatica : systems and information technology

|

2009

|

Vol. 2(13)

97--105

EN

Cellular Automata have been successfully applied to several scientific problems such as among others image processing or data encryption. One could find reversibility of dynamics is a fundamental feature of nature. While the most CA are not reversible in nature, one can find some CA with simple behavior could be reversible. Reversible cellular automata (RCA) as efficient encryption and decryption devices was originally conceived by Kari. In this introduction paper, we analyze and develop reversible cellular automata (RCA) based on Kari’s idea and some Clarridge’s concepts.

13

Properties and analysis of [alfa]-nets

Karatkevich A

Informatyka Teoretyczna i Stosowana

|

2005

|

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).

14

Information Dynamics of Cellular Automata I -An Algebraic Study

Nishio H., Saito T.

Fundamenta Informaticae

|

2003

|

Vol. 58, nr 3,4

399--420

EN

Information dynamics of cellular automata(CA) is studied using polynomials over finite fields. The information about the uncertainty of cell states is expressed by an indeterminate X called information variable and its dynamics is investigated by extending CA to CA[X] whose cell states are polynomials in X. For the global configuration of extended CA[X], new notions of completeness and degeneracy are defined and their dynamical properties are investigated. A theorem is proved that completeness equals non-degeneracy. With respect to the reversibility, we prove that a CA is reversible, if and only if its extension CA[X] preserves the set of complete configurations. Information dynamics of finite CAs and linear CAs are treated in the separate sections. Decision problems are also referred.

15

Making Revision Reversible: an Approach Based on Polynomials

Benferhat S., Dubois D., Lagrue S., Papini O.

Fundamenta Informaticae

|

2002

|

Vol. 53, nr 3,4

251-280

EN

This paper deals with iterated belief change and proposes a drastic revision rule that modifies a plausibility ordering of interpretations in such a way that any world where the input observation holds is more plausible that any world where it does not. This change rule makes sense in a dynamic context where observations are received, and the newer observations are considered more plausible than older ones. It is shown how to encode an epistemic state using polynomials equipped with the lexicographic ordering. This encoding makes it very easy to implement and iterate the revision rule using simple operations on these polynomials. Moreover, polynomials allow to keep track of the sequence of observations. Lastly, it is shown how to efficiently compute the revision rule at the syntactical level, when the epistemic state is concisely represented by a prioritized belief base. Our revision rule is the most drastic one can think of, in accordance with Darwiche and Pearl's principles, and thus contrasts with the minimal change rule called natural belief revision. The paper also shows how to obtain the reversibility of Boutilier's natural belief revision and possibilistic revision using polynomials.