Global Realisations of Local Specifications

Add to your list(s) Download to your calendar using vCal

• Martin Otto, Technische Universität Darmstadt, Germany
• Friday 06 November 2015, 14:00-15:00
• FW26.

If you have a question about this talk, please contact Ohad Kammar.

The following situation is typical of several tasks of model construction that arise, e.g., in connection with finite model properties and finite controllability: Given a finite set of local templates, together with specifications of required and permitted pairwise overlaps between them, the task is to find finite global realisations.

We approach this finite realisation task via a generic construction of reduced products with suitable groupoids. Due to strong acyclicity properties, these groupoids can serve as structural backbones in the construction of finite realisations, similar to the use of free groups in standard constructions of infinite realisations. The construction is sufficiently generic as to be compatible with symmetries of the specification while also allowing us to avoid incidental cycles of overlaps up to any specified finite length. The resulting finite realisations can be forced

—to realise symmetries built into the specification, and —to admit local homomorphisms into any (finite or infinite)

realisation and in particular into the canonical free realisation. As one consequence we obtain a new proof of the finite-model-assertion in a theorem of Herwig and Lascar, which allows us to lift local symmetries of finite structures to global symmetries within classes defined by forbidden homomorphisms. This in turn proves, e.g., finite controllability for UCQ vs. guarded specifications.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge talks
• Computing and Mathematics
• Department of Computer Science and Technology talks and seminars
• FW26
• Interested Talks
• Logic and Semantics Seminar (Computer Laboratory)
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk373's list

Note that ex-directory lists are not shown.