These are some short notes concerning model-complete cores, based on an exposition of Manuel Bodirsky. In particular, he proved that every 
-categorical structure has a unique (up to isomorphism) model-complete core. We pose the question whether the model-complete core of a definable structure (say, over the equality atoms) is again definable.
Tag Archives: CSP
Classification of standard alphabets
The master thesis of Łukasz Wołochowski continues the study of standard alphabets and classifies all alphabets of dimension up to 8, with regard to their standardness. Here is the thesis and here is its abstract:
This thesis concerns Turing machines with atoms. There exist alphabets with atoms over which Turing machines do not determinize and a method of alphabet classification is known. In this thesis we show and implement an improved version of this algorithm. The improvement is made by using advanced algorithms from the theory of Constraint Satisfaction Problems, as well as algebraic methods to reduce the size of a problem. As a result, we obtain a classification of all alphabets of dimension 8.
Orbit-finite systems of linear equations
Consider the following decision problem, over the equality symmetry.
Input: an orbit-finite system of linear equations 
over 
Decide: does have a solution (not necessarily finitely-supported)?
Inspired by Eryk’s beautiful solution of this problem, we present another solution, using an amazing theorem from topological dynamics.
Characterization of Standard Alphabets
In this paper (accepted to LICS 14) we characterize those alphabets for which Turing machines with atoms determinize.
Continue reading