Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: An Ehrenfeucht-Fraisse Game Approach to Collapse Results in Database
  Theory   We present a new Ehrenfeucht-Fraisse game approach to collapse results in
database theory and we show that, in principle, this approach suffices to prove
every natural generic collapse result. Following this approach we can deal with
certain infinite databases where previous, highly involved methods fail. We
prove the natural generic collapse for Z-embeddable databases over any linearly
ordered context structure with arbitrary monadic predicates, and for
N-embeddable databases over the context structure (R,<,+,Mon_Q,Groups). Here,
N, Z, R, denote the sets of natural numbers, integers, and real numbers,
respectively. Groups is the collection of all subgroups of (R,+) that contain
Z, and Mon_Q is the collection of all subsets of a particular infinite subset Q
of N. Restricting the complexity of the formulas that may be used to formulate
queries to Boolean combinations of purely existential first-order formulas, we
even obtain the collapse for N-embeddable databases over any linearly ordered
context structure with arbitrary predicates. Finally, we develop the notion of
N-representable databases, which is a natural generalization of the classical
notion of finitely representable databases. We show that natural generic
collapse results for N-embeddable databases can be lifted to the larger class
of N-representable databases. To obtain, in particular, the collapse result for
(N,<,+,Mon_Q), we explicitly construct a winning strategy for the duplicator in
the presence of the built-in addition relation +. This, as a side product, also
leads to an Ehrenfeucht-Fraisse game proof of the theorem of Ginsburg and
Spanier, stating that the spectra of FO(<,+)-sentences are semi-linear.

27
The categories of this paper are: comp-gas
12
The categories of this paper are: nucl-th
23
The categories of this paper are: solv-int
4
The categories of this paper are: cond-mat
34
The categories of this paper are: chem-ph
20
The categories of this paper are: acc-phys
17
The categories of this paper are: q-fin
14
The categories of this paper are: math-ph
7
The categories of this paper are: hep-th
19
The categories of this paper are: eess
26
The categories of this paper are: bayes-an
24
The categories of this paper are: dg-ga
25
The categories of this paper are: patt-sol
10
The categories of this paper are: q-bio
6
The categories of this paper are: astro-ph
28
The categories of this paper are: alg-geom