Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: On flat lossy channel machines   We show that reachability, repeated reachability, nontermination and
unboundedness are NP-complete for Lossy Channel Machines that are flat, i.e.,
with no nested cycles in the control graph. The upper complexity bound relies
on a fine analysis of iterations of lossy channel actions and uses compressed
word techniques for efficiently reasoning with paths of exponential lengths.
The lower bounds already apply to acyclic or single-path machines.

31
The categories of this paper are: ao-sci
8
The categories of this paper are: hep-ex
0
The categories of this paper are: hep-ph
26
The categories of this paper are: bayes-an
14
The categories of this paper are: math-ph
24
The categories of this paper are: dg-ga
29
The categories of this paper are: funct-an
16
The categories of this paper are: stat
21
The categories of this paper are: adap-org
12
The categories of this paper are: nucl-th
22
The categories of this paper are: chao-dyn
5
The categories of this paper are: gr-qc
10
The categories of this paper are: q-bio
11
The categories of this paper are: hep-lat
15
The categories of this paper are: nucl-ex
17
The categories of this paper are: q-fin