An Fd upper bound for the reachability problem in vector addition systems with states (VASS) in fixed dimension is given, where Fd is the d-th level of the Grzegorczyk hierarchy of complexity classes. The new algorithm combines the idea of the linear path scheme characterization of the reachability in the 2-dimension VASSes with the general decomposition algorithm by Mayr, Kosaraju and Lambert. The result improves the Fd+4 upper bound due to Leroux and Schmitz (LICS 2019).
The qCCS model proposed by Feng et al. provides a powerful framework to describe and reason about quantum communication systems that could be entangled with the environment. However, they only studied weak bisimulation semantics. In this paper we propose a new branching bisimilarity for qCCS and show that it is a congruence. The new bisimilarity is based on the concept of ϵ-tree and preserves the branching structure of concurrent processes where both quantum and classical components are allowed. Furthermore, we present a polynomial time equivalence checking algorithm for the ground version of our branching bisimilarity.
The reachability problem for vector addition systems with states (VASS) is Ackermann-complete. For every k ≥ 3, a completeness result for the k-dimensional VASS reachability problem is not yet available. It is shown in this paper that the 3-dimensional VASS reachability problem is in Tower, improving upon the current best upper bound F7 established by Leroux and Schmidt in 2019.
This thesis first focuses on the vector addition system. Based on the discussion of the existing work, we propose some new understanding of the reachability problem, which will help future research. Next, we focus on the nondeterministic computation, we will carry out quantitative study of the complexity of nondeterminism. AS far as we know, this is the first of it kind. The main contributions of the thesis are the follows:
The structure of nondeterministic computations is extremely complicated. C-graphs are abstract representations of the branching structure of nondeterministic computations. The paper investigates the structure of finite state nondeterministic computations by showing that the complexity of the structure increases non-elementarily while the number of computation steps increases. This is achieved by establishing a recursive equation relating the number of C-graphs of a certain height to the number of C-graphs of smaller height.