Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Nested Words for Order-2 Pushdown Systems   We study linear time model checking of collapsible higher-order pushdown
systems (CPDS) of order 2 (manipulating stack of stacks) against MSO and PDL
(propositional dynamic logic with converse and loop) enhanced with push/pop
matching relations. To capture these linear time behaviours with matchings, we
propose order-2 nested words. These graphs consist of a word structure
augmented with two binary matching relations, one for each order of stack,
which relate a push with matching pops (or collapse) on the respective stack.
Due to the matching relations, satisfiability and model checking are
undecidable. Hence we propose an under-approximation, bounding the number of
times an order-1 push can be popped. With this under-approximation, which still
allows unbounded stack height, we get decidability for satisfiability and model
checking of both MSO and PDL. The problems are ExpTime-Complete for PDL.

31
The categories of this paper are: ao-sci
12
The categories of this paper are: nucl-th
8
The categories of this paper are: hep-ex
35
The categories of this paper are: mtrl-th
17
The categories of this paper are: q-fin
28
The categories of this paper are: alg-geom
36
The categories of this paper are: cmp-lg
11
The categories of this paper are: hep-lat
18
The categories of this paper are: econ
23
The categories of this paper are: solv-int
9
The categories of this paper are: nlin
33
The categories of this paper are: plasm-ph
29
The categories of this paper are: funct-an
20
The categories of this paper are: acc-phys
27
The categories of this paper are: comp-gas
21
The categories of this paper are: adap-org