LO5: Random structures under logical transformations

A classical approach for modelling uncertainty is based on random structures, with appropriate probability distributions. Logical formulae (specifications, queries, etc.) are then evaluated not on single mathematical structures, but on probability spaces of structures. In many applications, structures are subject to various forms of logical transformations, such as interpretations, views, addition, deletion and updates of records, changes of vocabularies, identifications via congruences, and so on. These may change the underlying probability spaces in a dramatic way, and it is not really understood to what extent the methods from logic and combinatorics for computing limits, convergence rates, probabilistic equivalences etc., are compatible with such transformations.

This dissertation project will study probability spaces of structures under logical transformations, with the aim of sharpening the logical methods for dealing with random structures under dynamic changes. The main objectives of this project are as follows:

  • Compute explicit representations of probability spaces obtained by logical transformations. Develop algorithmic methods for computing the probability changes in such spaces.
  • Many known limit laws are based on extension axioms. For structures that are subject to logical transformations, stronger extension properties, are needed to provide limit laws. The theories based on stronger extension axioms are not yet adequately studied and need to be developed further.
  • Under many relevant probability distributions, random structures are almost surely rigid, i.e., have no non-trivial symmetries, and methods show that this is preserved under certain logical transformations. The plan is to extend this approach to compute symmetries of random structures under logical transformations.