On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra

Details On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra

2010-02-23

arxiv.org/abs/1002.4334v2

Computer Science

Logic in Computer Science

26 pages, no figures, submitted to LICS 2010 (decision pending); just added a reference to a related work in this version

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Semantic Generalizations of the Bernays-Schönfinkel-Ramsey Class with Finite or Co-finite Spectra will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-170376