On the Relative Succinctness of Two Extensions by Definitions of Multimodal Logic

摘要

The growing number of logics has lead to the question: How do we compare two formalisms? A natural answer is: We can compare their expressive power and computational properties. There is, however, another way of comparing logics that has attracted attention recently, namely in terms of representational succinctness, i.e., we can ask whether one of the logics allows for a more "economical" encoding of information than the other. Using extended-syntax trees that correspond to game trees for the Addler-Immerman games, we prove that two well-known abbreviations in multimodal logic lead to an exponential increase in succinctness.