کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
423393 685215 2008 17 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Modal Expressiveness of Graph Properties
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Modal Expressiveness of Graph Properties
چکیده انگلیسی

Graphs are among the most frequently used structures in Computer Science. In this work, we analyze how we can express some important graph properties such as connectivity, acyclicity and the Eulerian and Hamiltonian properties in a modal logic. First, we show that these graph properties are not definable in a basic modal language. Second, we discuss an extension of the basic modal language with fix-point operators, the modal μ-calculus. Unfortunately, even with all its expressive power, the μ-calculus fails to express these properties. This happens because μ-calculus formulas are invariant under bisimulations. Third, we show that it is possible to express some of the above properties in a basic hybrid logic. Fourth, we propose an extension of CTL* with nominals, that we call hybrid-CTL*, and then show that it can express the Hamiltonian property in a better way than the basic hybrid logic. Finally, we introduce a promising way of expressing properties related to edges and use it to express the Eulerian property.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Electronic Notes in Theoretical Computer Science - Volume 205, 6 April 2008, Pages 31-47