Martin Otto
Abstract
We construct finite groups whose Cayley graphs have large girth even with respect to a discounted distance measure that contracts arbitrarily long sequences of edges from the same color class (subgroup), and only counts transitions between color classes (cosets). These groups are shown to be useful in the construction of finite bisimilar hypergraph covers that avoid any small cyclic configurations. We present two applications to the finite model theory of the guarded fragment: a strengthening of the known finite model property for GF and the characterization of GF as the guarded bisimulation invariant fragment of first-order logic in the sense of finite model theory.
- Alon, N. 1995. Tools from higher algebra. In Handbook of Combinatorics, R. Graham, M. Grötschel, and Lovász, Eds., Vol. II., North-Holland, 1749--1783. Google Scholar
Digital Library
- Andréka, H., van Benthem, J., and Németi, I. 1998. Modal languages and bounded fragments of predicate logic. J. Philosophical Logic 27, 217--274.Google ScholarCross Ref
- Baader, F., Calvanese, D., McGuinness, D., Nardi, D., and Patel-Schneider, P., Eds. 2003. The Description Logic Handbook. Cambridge University Press. Google ScholarDigital Library
- Bárány, V., Gottlob, G., and Otto, M. 2010. Querying the guarded fragment. In Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LICS'10). 2--11. Google ScholarDigital Library
- Beeri, C., Fagin, R., Maier, D., and Yannakakis, M. 1983. On the desirability of acyclic database schemes. J. ACM 30, 497--513. Google ScholarDigital Library
- Berge, C. 1973. Graphs and Hypergraphs. North-Holland. Google ScholarDigital Library
- Courcelle, B. 1990. Graph rewriting: An algebraic and logic approach. In Handbook of Theoretical Computer Science, J. van Leeuwen, Ed., Vol. B., Elsevier, 193--242. Google ScholarDigital Library
- Dawar, A. and Otto, M. 2009. Modal characterisation theorems over special classes of frames. Ann. Pure Appl. Logic 161, 1--42. (Journal version of LICS'05 paper). Google ScholarDigital Library
- Flum, J., Frick, M., and Grohe, M. 2002. Query evaluation via tree-decomposition. J. ACM 49, 716--752. Google ScholarDigital Library
- Fox, R. 1957. Covering spaces with singularities. In A Symposium in Honor of S. Lefschetz, Princeton University Press, 243--257.Google ScholarCross Ref
- Frick, M. and Grohe, M. 2001. Deciding first-order properties of locally tree-decomposable structures. J. ACM 48, 1184--1206. Google ScholarDigital Library
- Gottlob, G., Leone, N., and Scarcello, F. 2001. The complexity of acyclic conjunctive queries. J. ACM 43, 431--498. Google ScholarDigital Library
- Grädel, E. 1999. On the restraining power of guards. J. Symb. Log. 64, 1719--1742.Google ScholarCross Ref
- Grädel, E., Hirsch, C., and Otto, M. 2002. Back and forth between guarded and modal logics. ACM Trans. Computat. Log. 3, 418--463. Google ScholarDigital Library
- Grohe, M. 2008. Logic, graphs, and algorithms. In Logic and Automata, History and Perspectives, J. Flum, E. Grädel, and T. Wilke, Eds., Amsterdam University Press, 357--422.Google Scholar
- Hodkinson, I. and Otto, M. 2003. Finite conformal hypergraph covers and Gaifman cliques in finite structures. Bull. Symb. Logic 9, 387--405.Google ScholarCross Ref
- Otto, M. 2004. Modal and guarded characterisation theorems over finite transition systems. Ann. Pure Appl. Logic 130, 173--205. (Journal version of LICS'02 paper). Google ScholarDigital Library
- Otto, M. 2006. Bisimulation invariance and finite models. In Colloquium Logicum 2002, Lecture Notes in Logic, ASL, 276--298.Google Scholar
- Otto, M. 2009. Avoiding incidental homomorphisms into guarded covers. Tech. rep. no. 2600, TU Darmstadt.Google Scholar
- Otto, M. 2010. Highly acyclic groups, hypergraph covers and the guarded fragment. In Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LICS'10). 12--21. Google ScholarDigital Library
- Otto, M. 2011. Model theoretic methods for fragments of FO and special classes of (finite) structures. In Finite and Algorithmic Model Theory. J. Esparza, C. Michaux, and C. Steinhorn, Eds., LMS Lecture Note Series Series, vol. 379, Cambridge University Press, 271--341.Google Scholar
- Rosen, E. 1997. Modal logic over finite structures. J. Logic, Lang. Inf. 6, 427--439. Google ScholarDigital Library
- van Benthem, J. 1983. Modal Logic and Classical Logic. Bibliopolis, Napoli.Google Scholar
Index Terms
- Highly acyclic groups, hypergraph covers, and the guarded fragment
Recommendations
Highly Acyclic Groups, Hypergraph Covers and the Guarded Fragment
LICS '10: Proceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer ScienceWe construct finite groups whose Cayley graphs have large girth even w.r.t. a discounted distance measure that contracts arbitrarily long sequences of edges from the same colour class, and only counts transitions between colour classes. These groups are ...
Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants
We consider extensions of the two-variable guarded fragment, GF2, where distinguished binary predicates that occur only in guards are required to be interpreted in a special way (as transitive relations, equivalence relations, preorders, or partial ...
Querying the Guarded Fragment
LICS '10: Proceedings of the 2010 25th Annual IEEE Symposium on Logic in Computer ScienceEvaluating a boolean conjunctive query q over a guarded first-order theory T is equivalent to checking whether (T \& not q) is unsatisfiable. This problem is relevant to the areas of database theory and description logic. Since q may not be guarded, ...
Comments