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

Znaleziono wyników: 10

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 An Upper Bound for the Reachability Problem of Safe, Elementary Hornets
Köhler-Bußmeier M., Heitmann F.
Fundamenta Informaticae
|
2016
|
Vol. 143, nr 1/2
89--100
EN
In this paper we study the complexity of the reachability problem HORNETS, an algebraic extension of object nets. Here we consider the restricted class of safe, elementary HORNETS. In previouswork we established the lower bound, i.e. reachability requires at least exponential space. In another work we have shown we can simulate elementary HORNETS with elementary object nets EOS, where reachability is known to be PSpace-complete. Since this simulation leads to a double exponential increase in the size of the simulating EOS, we obtain that for HORNETS the reachability problem is solvable in double exponential space. In this contributionwe show that this kind of simulation is rather bad, since we show that exponential space is sufficient. Together with the known lower bound this shows that the upper is tight.
2
Content available remote Structural and Dynamic Restrictions of Elementary Object Systems
Heitmann F., Köhler-Bußmeier M.
Fundamenta Informaticae
|
2014
|
Vol. 135, nr 4
387--401
EN
Elementary object systems (EOS for short) are Petri nets in which tokens may be Petri nets again. Originally proposed by Valk for a two levelled structure, the formalism was later generalised for arbitrary nesting structures. However, even if restricted to a nesting depth of two, EOS are Turing-complete and thus many problems like reachability and liveness are undecidable for them. Nonetheless, since they are useful to model many practical applications a natural question is how to restrict the formalism in such a way, that the resulting restricted formalism is still helpful in a modelling context, but so that important verification problems like reachability become quickly decidable. In the last years several structural and dynamic restrictions for EOS have therefore been investigated. These investigations have been central to the first author’s recent PhD thesis and have been published in past editions of this journal and on conferences. In this paper we add several new results and present them together with the old in a unified fashion highlighting the central message of these investigations.
3
Content available remote On the Complexity of the Reachability Problem for Safe : Elementary Hornets
Köhler-Bußmeier M.
Fundamenta Informaticae
|
2014
|
Vol. 129, nr 1/2
101--115
EN
In this paper we study the complexity of HORNETS, an algebraic extension of object nets. We define a restricted class: safe, elementary HORNETS, to guarantee finite state spaces. It will turn out, that the reachability problem for this class requires exponential space, which is a major increase when compared to safe, elementary object nets, which require polynomial space.
4
Content available remote A Survey of Decidability Results for Elementary Object Systems
Köhler-Bußmeier M.
Fundamenta Informaticae
|
2014
|
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.
5
Content available remote Defining Multi-Party Compromises using Unfoldings of Workflow Nets
Köhler-Bußmeier M.
Fundamenta Informaticae
|
2013
|
Vol. 128, nr 1-2
97--111
EN
In this paper we develop a negotiation and contracting framework for inter-organisational workflows. The overall aim is to compute a group-plan from a given set of individual plans, where plans are formulated in the context of a given inter-organisational workflow between the agents. A general problem is that the individual plans are not consistent, i.e. the intersection of all individual plans does not contain a complete process, which leads from the initial state of the workflow to its final state. Therefore, negotiation is needed to obtain a compromise. In this paper we develop a generic negotiation protocol and use branching processes as the elementary data structure. The generic protocol is adapted within the specifics of our SONAR-framework. SONAR is a specification framework that defines the organisational structure of multi-agent systems. SONAR has a formal notion of teams and team-formation which is used here to instantiate the strategy parameters.
6
Content available remote Conservative Elementary Object Systems
Köhler-Bußmeier M., Heitmann F.
Fundamenta Informaticae
|
2012
|
Vol. 120, nr 3/4
325-339
EN
This contribution presents decidability results for the formalism of 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 paper we study the relationship of the reachability and the liveness problem. We prove that both problems are undecidable for EOS (even for the subclass of conservative EOS) while it is well known that both are decidable for classical p/t nets. Despite these undecidability results, boundedness can be decided for conservative EOS using a monotonicity argument similar to that for p/t nets.
7
Content available remote Liveness of Safe Object Nets
Köhler-Bußmeier M., Heitmann F.
Fundamenta Informaticae
|
2011
|
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.
8
Content available remote Safeness for Object Nets
Köhler-Bußmeier M., Heitmann F.
Fundamenta Informaticae
|
2010
|
Vol. 101, nr 1/2
29-43
EN
In this paper we discuss the concept of safeness for Elementary Object Nets (EOS). Object nets are Petri nets which have Petri nets as tokens – an approach known as the nets-within-nets paradigm. Object nets are called elementary if the net system has a two levelled structure. The well known p/t nets can be considered as a special case of EOS. For p/t nets the concept of safeness means that there is at most one token on each place. Since object nets have nested markings there are different possibilities to generalise this idea for EOS. In this paper we define different variants of EOS safeness, discuss their relationships, show that they all coincide for p/t-like EOS, and address the complexity of well known Petri net problems like reachability and liveness for this new class of object nets.
9
Content available remote On the Expressiveness of Communication Channels for Object Nets
Köhler-Bußmeier M., Heitmann F.
Fundamenta Informaticae
|
2009
|
Vol. 93, nr 1-3
205-219
EN
In this work we present object net systems, i.e. Petri nets with nets as token objects, which are equipped with channels that allow to transfer net-tokens in the vertical dimension of the nested marking. These channels are a modelling element powerful enough to describe a direct simulation of counter programs which shows that typical net problems like boundedness, coverability, and reachability are undecidable.
10
Content available remote Linear Properties of Zero-Safe Nets with Debit Tokens
Köhler-Bußmeier M., Kudlek M.
Fundamenta Informaticae
|
2008
|
Vol. 85, nr 1-4
329-342
EN
In this contribution we study an extension of zero-safe nets that allows to model cooperation scenarios. Since zero-safe nets cannot be represented as finite nets in general, we study an extension of the firing rule having a close connection to blind counter automatons and the theory of semi-flows. As a main result we obtain, that a representation can always be given as a finite P/T net - although our firing rule is an extension of the original one - i.e. it preserves all the events that have been allowed before.
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ć.