32
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      On Semantic Generalizations of the Bernays-Sch\"onfinkel-Ramsey Class with Finite or Co-finite Spectra

      Preprint
      ,

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Motivated by model-theoretic properties of the BSR class, we present a family of semantic classes of FO formulae with finite or co-finite spectra over a relational vocabulary \Sigma. A class in this family is denoted EBS_\Sigma(\sigma), where \sigma is a subset of \Sigma. Formulae in EBS_\Sigma(\sigma) are preserved under substructures modulo a bounded core and modulo re-interpretation of predicates outside \sigma. We study properties of the family EBS_\Sigma = {EBS_\Sigma(\sigma) | \sigma \subseteq \Sigma}, e.g. classes in EBS_\Sigma are spectrally indistinguishable, EBS_\Sigma(\Sigma) is semantically equivalent to BSR over \Sigma, and EBS_\Sigma(\emptyset) is the set of all FO formulae over \Sigma with finite or co-finite spectra. Furthermore, (EBS_\Sigma, \subseteq) forms a lattice isomorphic to the powerset lattice (\wp({\Sigma}), \subseteq). This gives a natural semantic generalization of BSR as ascending chains in (EBS_\Sigma, \subseteq). Many well-known FO classes are semantically subsumed by EBS_\Sigma(\Sigma) or EBS_\Sigma(\emptyset). Our study provides alternative proofs of interesting results like the Lo\'s-Tarski Theorem and the semantic subsumption of the L\"owenheim class with equality by BSR. We also present a syntactic sub-class of EBS_\Sigma(\sigma) called EDP_\Sigma(\sigma) and give an expression for the size of the bounded cores of models of EDP_\Sigma(\sigma) formulae. We show that the EDP_\Sigma(\sigma) classes also form a lattice structure. Finally, we study some closure properties and applications of the classes presented.

          Related collections

          Author and article information

          Journal
          2010-02-23
          2010-03-04
          Article
          1002.4334
          3b6529f8-d62f-42ef-958a-eb0950465f44

          http://arxiv.org/licenses/nonexclusive-distrib/1.0/

          History
          Custom metadata
          26 pages, no figures, submitted to LICS 2010 (decision pending); just added a reference to a related work in this version
          cs.LO

          Theoretical computer science
          Theoretical computer science

          Comments

          Comment on this article