کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
439371 690540 2006 27 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Similarity between preferential models
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Similarity between preferential models
چکیده انگلیسی

The notion of bisimulation is an important concept in process algebra and modern modal logic. This paper explores the notion of B-similarity, which is a kind of bisimulation between preferential models. We characterize the equivalence of preferential models in terms of B-similarity. However, this result is applicable only for preferential models of finite depth. To overcome this defect, we introduce a weak notion of similarity called M-similarity, and obtain a result corresponding to Hennessy–Milner Theorem and Keisler–Shelah's Isomorphism Theorem in modal logic and first-order logic, respectively. As its application, we investigate the expressive power of Boolean combinations of conditional assertions (BCA, for short), and prove that BCAs are the fragments of first-order language preserved under M-similarity. Moreover, we obtain a characterization for elementary classes defined by BCAs. A notion of first-order translation originating from modal logic plays an important role in this paper. In order to illustrate that first-order translation is a powerful tool in the study of nonmonotonic logic, some model-theoretic results about preferential models are proved based on this translation.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 353, Issues 1–3, 14 March 2006, Pages 26-52