Homomorphism Preservation on Quasi-Wide Classes

Details Homomorphism Preservation on Quasi-Wide Classes Homomorphism Preservation on Quasi-Wide Classes

2008-11-27

arxiv.org/abs/0811.4497v2

Computer Science

Logic in Computer Science

13 pages

Scientific paper

A class of structures is said to have the homomorphism-preservation property just in case every first-order formula that is preserved by homomorphisms on this class is equivalent to an existential-positive formula. It is known by a result of Rossman that the class of finite structures has this property and by previous work of Atserias et al. that various of its subclasses do. We extend the latter results by introducing the notion of a quasi-wide class and showing that any quasi-wide class that is closed under taking substructures and disjoint unions has the homomorphism-preservation property. We show, in particular, that classes of structures of bounded expansion and that locally exclude minors are quasi-wide. We also construct an example of a class of finite structures which is closed under substructures and disjoint unions but does not admit the homomorphism-preservation property.

Affiliated with

Also associated with

No associations

Rating

Homomorphism Preservation on Quasi-Wide Classes 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 Homomorphism Preservation on Quasi-Wide Classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Homomorphism Preservation on Quasi-Wide Classes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-232489