An Upper Bound for the Reachability Problem of Safe, Elementary Hornets

Issue title: Concurrency, Specification and Programming (CS&P)

Guest editors: Ludwik Czaja, Wojciech Penczek and Krzysztof Stencel

Article type: Research Article

Authors: Köhler-Bußmeier, Michael^{a; *} | Heitmann, Frank^b

Affiliations: [a] University of Applied Science Hamburg and University of Hamburg, Germany. michael.koehler-bussmeier@haw-hamburg.de, koehler@informatik.uni-hamburg.de | [b] University of Hamburg, Germany. heitmann@informatik.uni-hamburg.de

Correspondence: [*] Address for correspondence: University of Applied Science Hamburg, Department for Informatics, Berliner Tor 7, D-20099 Hamburg, Germany

Abstract: 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 previous work 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 contribution we 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.

Keywords: Hornets, nets-within-nets, object nets, reachability, safeness

DOI: 10.3233/FI-2016-1305

Journal: Fundamenta Informaticae, vol. 143, no. 1-2, pp. 89-100, 2016