Author name cluster

Ursula Goltz

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

2 author rows

I&C Journal 2022 Journal Article

Abstract processes in the absence of conflicts in general place/transition systems

Rob van Glabbeek
Ursula Goltz
Jens-Wolfhard Schicke-Uffmann

Goltz and Reisig generalised Petri's concept of processes of one-safe Petri nets to general nets where places carry multiple tokens. BD-processes are equivalence classes of Goltz-Reisig processes connected through the swapping transformation of Best and Devillers; they can be considered as an alternative representation of runs of nets. Here we present an order respecting bijection between the BD-processes and the FS-processes of a countable net, the latter being defined—in an analogous way—as equivalence classes of firing sequences. Using this, we show that a countable net without binary conflicts has a (unique) largest BD-process.

Details DOI

I&C Journal 2021 Journal Article

Abstract processes and conflicts in place/transition systems

Rob van Glabbeek
Ursula Goltz
Jens-Wolfhard Schicke-Uffmann

For one-safe Petri nets or condition/event-systems, a process as defined by Carl Adam Petri provides a notion of a run of a system where causal dependencies are reflected in terms of a partial order. Goltz and Reisig have generalised this concept for nets where places carry multiple tokens, by distinguishing tokens according to their causal history. However, this so-called individual token interpretation is often considered too detailed. Here we identify a subclass of Petri nets, called structural conflict nets, where no interplay between conflict and concurrency due to token multiplicity occurs. For this subclass, we define abstract processes as equivalence classes of Goltz-Reisig processes. We justify this approach by showing that there is a largest abstract process if and only if the underlying net is conflict-free with respect to a canonical notion of conflict.

Details DOI

MFCS Conference 2008 Invited Paper

On Synchronous and Asynchronous Interaction in Distributed Systems

Rob J. van Glabbeek
Ursula Goltz
Jens-Wolfhard Schicke

Abstract When considering distributed systems, it is a central issue how to deal with interactions between components. In this paper, we investigate the paradigms of synchronous and asynchronous interaction in the context of distributed systems. We investigate to what extent or under which conditions synchronous interaction is a valid concept for specification and implementation of such systems. We choose Petri nets as our system model and consider different notions of distribution by associating locations to elements of nets. First, we investigate the concept of simultaneity which is inherent in the semantics of Petri nets when transitions have multiple input places. We assume that tokens may only be taken instantaneously by transitions on the same location. We exhibit a hierarchy of ‘asynchronous’ Petri net classes by different assumptions on possible distributions. Alternatively, we assume that the synchronisations specified in a Petri net are crucial system properties. Hence transitions and their preplaces may no longer placed on separate locations. We then answer the question which systems may be implemented in a distributed way without restricting concurrency, assuming that locations are inherently sequential. It turns out that in both settings we find semi-structural properties of Petri nets describing exactly the problematic situations for interactions in distributed systems.

Details

TCS Journal 2004 Journal Article

Well-behaved flow event structures for parallel composition and action refinement

Rob van Glabbeek
Ursula Goltz

Flow event structures were introduced as a model for giving semantics to process algebras. However, it turned out that certain restrictions have to be made to make them suitable for this purpose. In this paper, we investigate subclasses of flow event structures which are both suited for the process algebraic composition operators, and for action refinement as a means of regarding processes on different levels of abstraction. First, suitable subclasses are characterised. Then two specific subclasses are proposed. The larger class generalises the one from Castellani and Zhang (Theoret. Comput. Sci. 179 (1997) 203–215), which is not suitable for action refinement. The smaller one is still sufficiently expressive for dealing with all standard process algebras and action refinement.

Details DOI

MFCS Conference 1996 Conference Paper

Causal Testing

Ursula Goltz
Heike Wehrheim

Abstract We suggest an equivalence notion for event structures as a semantic model of concurrent systems. It combines the notion of testing (or failure) equivalence with respect to the timing of choices between different executions with a precise account of causalities between action occurrences as in causal semantics. This fills an open gap in the lattice of equivalences considered in comparative concurrency semantics. We show that our notion coincides with a “canonical” equivalence obtained as the usual testing performed on causal trees. Furthermore, we show that it is invariant under action refinement, thus fulfilling a standard criterion for non-interleaving equivalences.

Details

I&C Journal 1996 Journal Article

Comparing Syntactic and Semantic Action Refinement

Ursula Goltz
Roberto Gorrieri
Arend Rensink

The semantic definition of action refinement on labelled configuration structures is compared with the notion ofsyntactic substitution, which can be used as another notion of action refinement in a process algebraic setting. The comparison is done by studying a process algebra equipped with sequential composition, parallel composition with an explicit synchronisation set, and an operator for action refinement. On the one hand, the language (including the refinement operator) is given a configuration structure semantics. On the other hand, a reduction procedure transforms a process termPinto aflatterm (i. e. , with the refinement operator not occurring in it)red(P) by means of syntactic substitution, defined in a structural inductive way. The main aim of the paper is to investigate general conditions under which the termsPandred(P) have the same semantics. The results we present are essentially dependent on the question whether the refined action can be synchronised or not. In the latter case, Pandred(P) give rise to isomorphic configuration structures under mild assumptions. The former case is considerably more difficult, since then refinement cannot be expected to distribute over parallel composition. We give necessary and sufficientsemanticconditions under which distribution still holds up to semantic equivalence. Subsequently, we also give sufficient (but not necessary)syntacticconditions for reducible terms. Finally, we generalise these results to a language with recursion.

Details DOI

TCS Journal 1994 Journal Article

Finite Petri nets as models for recursive causal behaviour

Ursula Goltz
Arend Rensink

Goltz (1988) discussed whether or not there exist finite Petri nets (with unbounded capacities) modelling the causal behaviour of certain recursive CCS terms. As a representative example, the following term is considered: B=(a. nil∣b. B)+c. nil. We will show that the answer depends on the chosen notion of behaviour. It was already known that the interleaving behaviour and the branching structure of terms as B can be modelled as long as causality is not taken into account. We now show that also the causal behaviour of B can be modelled as long as the branching structure is not taken into account. However, it is not possible to represent both causal dependencies and the behaviour with respect to choices between alternatives in a finite net. We prove that there exists no finite Petri net modelling B with respect to both pomset trace equivalence and failure equivalence.

Details DOI

MFCS Conference 1989 Conference Paper

Equivalence Notions for Concurrent Systems and Refinement of Actions (Extended Abstract)

Rob J. van Glabbeek
Ursula Goltz

Abstract We investigate equivalence notions for concurrent systems. We consider ”linear time” approaches where the system behaviour is characterised as the set of possible runs as well as ”branching time” approaches where the conflict structure of systems is taken into account. We show that the usual interleaving equivalences, and also the equivalences based on steps (multisets of concurrently executed actions) are not preserved by refinement of atomic actions. We prove that ”linear time” partial order semantics, where causality in runs is explicit, is invariant under refinement. Finally, we consider various bisimulation equivalences based on partial orders and show that the strongest one of them is preserved by refinement whereas the others are not.

Details

MFCS Conference 1988 Conference Paper

On Representing CCS Programs by Finite Petri Nets

Ursula Goltz

Abstract A non-interleaving semantics for a subset of CCS using finite place/transition-systems is presented. Straightforward constructions on nets for CCS operations are given. When restricting the language appropriately (no restriction and relabelling, only guarded choice ), these operations yield a net semantics with a clear distinction of concurrency and nondeterminism. It is shown that the usual interleaving semantics is retrievable from the net semantics. Partial order semantics and equivalence notions for labelled P/T-systems are discussed. This shows how the intuitive causal dependencies in a CCS program are represented via the net semantics.

Details