Logic Journal of the IGPL 17 (5):559-587 (2009)

Abstract
Graphs are among the most frequently used structures in Computer Science. Some of the properties that must be checked in many applications are connectivity, acyclicity and the Eulerian and Hamiltonian properties. In this work, we analyze how we can express these four properties with modal logics. This involves two issues: whether each of the modal languages under consideration has enough expressive power to describe these properties and how complex it is to use these logics to actually test whether a given graph has some desired property. First, we show that these properties are not definable in a basic modal logic or in any bisimulation-invariant extension of it, like the modal μ-calculus. We then show that it is possible to express some of the above properties in a basic hybrid logic. Unfortunately, the Hamiltonian and Eulerian properties still cannot be efficiently checked. In a second attempt, we propose an extension of CTL* with nominals and show that the Hamiltonian property can be more efficiently checked in this logic than in the previous one. In a third attempt, we extend the basic hybrid logic with the ↓ operator and show that we can check the Hamiltonian property with optimal complexity in this logic. Finally, we tackle the Eulerian property in two different ways. First, we develop a generic method to express edge-related properties in hybrid logics and use it to express the Eulerian property. Second, we express a necessary and sufficient condition for the Eulerian property to hold using a graded modal logic.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1093/jigpal/jzp021
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 68,975
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

In so Many Possible Worlds.Kit Fine - 1972 - Notre Dame Journal of Formal Logic 13 (4):516-520.
Model Checking Hybrid Logics.Massimo Franceschet & Maarten de Rijke - 2006 - Journal of Applied Logic 4 (3):279-304.

Add more references

Citations of this work BETA

A Logic for Diffusion in Social Networks.Zoé Christoff & Jens Ulrik Hansen - 2015 - Journal of Applied Logic 13 (1):48-77.

Add more citations

Similar books and articles

On the Beth Properties of Some Intuitionistic Modal Logics.C. Luppi - 2002 - Archive for Mathematical Logic 41 (5):443-454.
Bisimulation, Modal Logic and Model Checking Games.C. Stirling - 1999 - Logic Journal of the IGPL 7 (1):103-124.
Prefinitely Axiomatizable Modal and Intermediate Logics.Marcus Kracht - 1993 - Mathematical Logic Quarterly 39 (1):301-322.
Abstract Modal Logics.Ramon Jansana - 1995 - Studia Logica 55 (2):273 - 299.
Modal Hybrid Logic.Andrzej Indrzejczak - 2007 - Logic and Logical Philosophy 16 (2-3):147-257.
The Accidental Properties of Numbers and Properties.Harold Noonan & Mark Jago - 2012 - Thought: A Journal of Philosophy 1 (2):134-140.

Analytics

Added to PP index
2015-02-04

Total views
13 ( #765,592 of 2,498,244 )

Recent downloads (6 months)
1 ( #426,910 of 2,498,244 )

How can I increase my downloads?

Downloads

My notes