Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Model Checking Existential Logic on Partially Ordered Sets   We study the problem of checking whether an existential sentence (that is, a
first-order sentence in prefix form built using existential quantifiers and all
Boolean connectives) is true in a finite partially ordered set (in short, a
poset). A poset is a reflexive, antisymmetric, and transitive digraph. The
problem encompasses the fundamental embedding problem of finding an isomorphic
copy of a poset as an induced substructure of another poset.
  Model checking existential logic is already NP-hard on a fixed poset; thus we
investigate structural properties of posets yielding conditions for
fixed-parameter tractability when the problem is parameterized by the sentence.
We identify width as a central structural property (the width of a poset is the
maximum size of a subset of pairwise incomparable elements); our main
algorithmic result is that model checking existential logic on classes of
finite posets of bounded width is fixed-parameter tractable. We observe a
similar phenomenon in classical complexity, where we prove that the isomorphism
problem is polynomial-time tractable on classes of posets of bounded width;
this settles an open problem in order theory.
  We surround our main algorithmic result with complexity results on less
restricted, natural neighboring classes of finite posets, establishing its
tightness in this sense. We also relate our work with (and demonstrate its
independence of) fundamental fixed-parameter tractability results for model
checking on digraphs of bounded degree and bounded clique-width.

9
The categories of this paper are: nlin
26
The categories of this paper are: bayes-an
8
The categories of this paper are: hep-ex
17
The categories of this paper are: q-fin
20
The categories of this paper are: acc-phys
6
The categories of this paper are: astro-ph
29
The categories of this paper are: funct-an
24
The categories of this paper are: dg-ga
16
The categories of this paper are: stat
19
The categories of this paper are: eess
14
The categories of this paper are: math-ph
27
The categories of this paper are: comp-gas
3
The categories of this paper are: physics
31
The categories of this paper are: ao-sci
35
The categories of this paper are: mtrl-th
21
The categories of this paper are: adap-org