Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: Hornets

Sortuj według:

Ogranicz wyniki do:

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

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.

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

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.