A study on multi-dimensional products of graphs and hybrid logics

作者：Benevides Mario R F; Menasche Schechter L

来源：Theoretical Computer Science, 2011, 412(37): 4946-4966.

DOI：10.1016/j.tcs.2011.05.011

• Products of graphs
• Intransitivity
• Hybrid languages
• Model-checking
• Products of modal logics
• Axiomatic systems

In this work, we address some issues related to products of graphs and products of modal logics. Our main contribution is the presentation of a necessary and sufficient condition for a countable and connected graph to be a product, using a property called intransitivity. We then proceed to describe this property in a logical language. First, we show that intransitivity is not modally definable and also that no necessary and sufficient condition for a graph to be a product can be modally definable. Then, we exhibit a formula in a hybrid language that describes intransitivity. With this, we get a logical characterization of products of graphs of arbitrary dimensions. We then use this characterization to obtain two other interesting results. First, we determine that it is possible to test in polynomial time, using a model-checking algorithm, whether a finite connected graph is a product. This test has cubic complexity in the size of the graph and quadratic complexity in its number of dimensions. Finally, we use this characterization of countable connected products to provide sound and complete axiomatic systems for a large class of products of modal logics. This class contains the logics defined by product frames obtained from Kripke frames that satisfy connectivity, transitivity and symmetry plus any additional property that can be defined by a pure hybrid formula. Most sound and complete axiomatic systems presented in the literature are for products of a pair of modal logics, while we are able, using hybrid logics, to provide sound and complete axiomatizations for many products of arbitrary dimensions.

• 出版日期2011-8-26