Descriptive complexity of modularity problems on graphs
Haroldo G. Benatti, Ruy J. G. B. de Queiroz · 2005
The infinitary logic L∞ω extends first order logic by allowing infinitary conjunctions and disjunctions and requiring that the formulas must have only a finite number of variables. Here we study the expressive power of ∃L∞ω which is the existential negation-free fragment of L∞ω. One of the important features of L ω ∞ω and ∃L∞ω is that their expressive power can be characterized by semantic games. We use pebble games for ∃L∞ω to prove some problems about the modularity of the length of paths and circuits in directed graphs and in bipartite directed graphs are not definable in this logic. For that we show that those problems over bipartite directed graphs are NP-complete. Rather than seeking to classify classes of problems by the syntactical complexity of their description in some logical formalism, here we have worked in the other direction: we have shown lower bounds for the descriptive complexity of specific problems. This hints at a research programme which might be called “concrete” descriptive complexity, which may be useful in case studies of expressiveness of specific query languages, given that it may suggest a reverse