Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Parameterized complexity results for 1-safe Petri nets   We associate a graph with a 1-safe Petri net and study the parameterized
complexity of various problems with parameters derived from the graph. With
treewidth as the parameter, we give W[1]-hardness results for many problems
about 1-safe Petri nets. As a corollary, this proves a conjecture of Downey et.
al. about the hardness of some graph pebbling problems. We consider the
parameter benefit depth (that is known to be helpful in getting better
algorithms for general Petri nets) and again give W[1]-hardness results for
various problems on 1-safe Petri nets. We also consider the stronger parameter
vertex cover number. Combining the well known automata-theoretic method and a
powerful fixed parameter tractability (FPT) result about Integer Linear
Programming, we give a FPT algorithm for model checking Monadic Second Order
(MSO) formulas on 1-safe Petri nets, with parameters vertex cover number and
the size of the formula.

4
The categories of this paper are: cond-mat
24
The categories of this paper are: dg-ga
5
The categories of this paper are: gr-qc
15
The categories of this paper are: nucl-ex
7
The categories of this paper are: hep-th
26
The categories of this paper are: bayes-an
0
The categories of this paper are: hep-ph
19
The categories of this paper are: eess
20
The categories of this paper are: acc-phys
16
The categories of this paper are: stat
12
The categories of this paper are: nucl-th
8
The categories of this paper are: hep-ex
22
The categories of this paper are: chao-dyn
29
The categories of this paper are: funct-an
21
The categories of this paper are: adap-org
23
The categories of this paper are: solv-int