Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: The Decidability of Verification under Promising 2.0   In PLDI'20, Lee et al. introduced the \emph{promising } semantics PS 2.0 of
the C++ concurrency that captures most of the common program transformations
while satisfying the DRF guarantee. The reachability problem for finite-state
programs under PS 2.0 with only release-acquire accesses is already known to be
undecidable. Therefore, we address, in this paper, the reachability problem for
programs running under PS 2.0 with relaxed accesses together with promises. We
show that this problem is undecidable even in the case where the input program
has finite state. Given this undecidability result, we consider the fragment of
PS 2.0 with only relaxed accesses allowing bounded number of promises. We show
that under this restriction, the reachability is decidable, albeit very
expensive: it is non-primitive recursive. Given this high complexity with
bounded number of promises and the undecidability result for the RA fragment of
PS 2.0, we consider a bounded version of the reachability problem. To this end,
we bound both the number of promises and the "view-switches", i.e, the number
of times the processes may switch their local views of the global memory. We
provide a code-to-code translation from an input program under PS 2.0, with
relaxed and release-acquire memory accesses along with promises, to a program
under SC. This leads to a reduction of the bounded reachability problem under
PS 2.0 to the bounded context-switching problem under SC. We have implemented a
prototype tool and tested it on a set of benchmarks, demonstrating that many
bugs in programs can be found using a small bound.

27
The categories of this paper are: comp-gas
4
The categories of this paper are: cond-mat
8
The categories of this paper are: hep-ex
13
The categories of this paper are: quant-ph
0
The categories of this paper are: hep-ph
34
The categories of this paper are: chem-ph
19
The categories of this paper are: eess
20
The categories of this paper are: acc-phys
30
The categories of this paper are: q-alg
24
The categories of this paper are: dg-ga
35
The categories of this paper are: mtrl-th
11
The categories of this paper are: hep-lat
22
The categories of this paper are: chao-dyn
10
The categories of this paper are: q-bio
14
The categories of this paper are: math-ph
3
The categories of this paper are: physics