کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430151 687814 2010 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Homomorphism preservation on quasi-wide classes
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Homomorphism preservation on quasi-wide classes
چکیده انگلیسی

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 classes 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 76, Issue 5, August 2010, Pages 324-332