Algorithmic Model Theory

Acyclicity in Hypergraphs and Relational Structures

Acyclicity criteria have long been recognised as a natural condition that guarantees tractability, for instance for query evaluation (see [BFMY83] for a seminal paper). Since a hypergraph is acyclic if, and only if, it is tree-decomposable, there is also an obvious connection with tree representations through model-theoretic interpretations in trees. Bounded treewidth and various generalisations have been extensively explored as criteria for tractability in model checking.

From a hypergraph theoretic point of view, the natural notion of hypergraph bisimulation poses the problem which degree of hypergraph acyclicity can be achieved in finite bisimilar coverings of finite hypergraphs – just as in the graph case, outright acyclicity can usually only be achieved in infinite coverings. But while finite graphs always admit even polynomially bounded finite bisimilar covers that are locally acyclic [O04], local acyclicity is not in general achievable in finite hypergraphs coverings. The new cover construction in [O10] provides finite hypergraph covers in which evry small induced sub-hypergraph is acyclic. That construction is based on a new idea for the construction of Cayley groups that avoid not just short cycles in the usual sense but even cycles that – irrespective of their length – make only few nontrivial transitions between distinct subsets of generators.

Model constructions involving these groups were applied to the finite model theory of the guarded fragment in [O10]. Earlier hypergraph coverings constructed in [HO03] had achieved conformality in finite covers, while [O09] provided another, weaker degree of size-bounded acyclicity in the sense that any small cyclic configurations in the cover would be tree-decomposable in projection to the base. This latter notion of coverings has been perfected in a new construction of feasible complexity in [BGO10], with important applications to the algorithmic model theory of guarded logics (see here).

The structure theory of the resulting classes of hypergraphs and relational structures of controlled acyclicity is an interesting field for further study – interesting both from the point of view of discrete mathematics and algorithmic model theory. Further research questions concern the possibly of more uniform variants of the construction in [O10] (holding a promise of new model-theoretic applications in the spirit of those explored in [HO03]) as well as the application of the existing construction to the algorithmic and finite model theory of various candidate logics in the vicinity of modal and guarded logics.

Bibliography

[BFMY83] Catriel Beeri, Ronald Fagin, David Maier, Mihalis Yannakakis: On the Desirability of Acyclic Database Schemes J. ACM 30(3): 479-513 (1983)

[O04] M. Otto, Modal and Guarded Characterisation Theorems over Finite Transition Systems,
Annals of Pure and Applied Logic, volume 130, 2004, pp.~173-205. Abstract
BibTeX entry

[O10]M. Otto.Highly acyclic groups, hypergraph covers and the guarded fragment, preprint, 2010, 42 pages. Journal version of LICS 2010 paper, invited for JACM, December 2010. Abstract

[HO03] I. Hodkinson and M. Otto, Finite Conformal Hypergraph Covers and Gaifman Cliques in Finite Structures,

Bulletin of Symbolic Logic, volume 9, 2003, pp. 387-405.
Abstract BibTeX entry

[O09] M. Otto, Avoiding incidental homomorphisms into guarded covers, Technical Report no. 2600, TU Darmstadt, 2009

[BGO10] V. Barany, G. Gottlob and M. Otto. Querying the Guarded Fragment, Proceedings of Logic in Computer Science, LICS 2010
Abstract BibTeX entry

 
A A A | Print Print | Impressum Legal note | Contact Contact
    zum Seitenanfangzum Seitenanfang