All posts by szymtor

Orbit-finite CSPs

Consider the following decision problem (for classical Turing machines). Let \Sigma be a fixed, finite signature.

Input: Two orbit-finite relational structures \str A,\str B, over \Sigma.

Decide: is there a homomorphism from \str A to \str B?

Question 1. Is the above problem decidable?

Observe that we are not asking for the existence of an equivariant homomorphism. If this were the case, the problem would be clearly decidable, since there are only finitely many equivariant homomorphisms between orbit-finite sets, and they can be effectively scanned. In this problem, the homomorphisms do not even have to be finitely supported! Below is an example where a homomorphism exists, but no finitely supported homomorphism exists.

Example. Consider the equality atoms. Let \str A be the graph whose vertices are pairs of distinct atoms, and in which edges join a pair with its inverse. Let \str B be the 2-clique. Then \str A maps to \str B, but no finitely supported homomorphism exists.

Following the idea of this post, in order to solve this problem, it might be useful to move to the totally ordered atoms (\str Q,\le).

Question 2. In the totally ordered atoms, if there is a homomorphism between orbit-finite structures \str A, \str B, is there one which is equivariant?

A positive answer to Question 2 would imply a positive answer to Question 1.

Edit. After reading Bartek’s comment below, I noticed that Question 2 has an even more negative answer. Consider the structures \str A=(\str Q,<) and \str B=(\str Q,>) (orders reversed). There is a homomorphism from \str A to \str B, namely the mapping x\mapsto -x, but there is none which is finitely supported.


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.

Join of two elements

Let a,b be two elements with atoms. The pair (a,b) satisfies the following universal property: (a,b) supports both a and b, and if y is another element with this property, then y supports (a,b).

We demonstrate the existence of an element denoted a\land b, with a dual property: a\land b is supported both by a and by b, and if y is another element with this property, then y is supported by a\land b.  The construction does not require any assumptions on the symmetry.

Continue reading

Bipartite graphs without bipartite partition

In the equality symmetry, there is a single-orbit graph G=(V,E) with the property that G is bipartite in the classical sense (equivalently, has no odd-length cycle) but has no partition into two parts which are finitely supported and not inter-connected. In other words, the graph G maps to the single-edge graph via a infinitely-supported homomorphism, but not via a finitely-supported one. And here’s the graph: its nodes are pairs of distinct atoms, and there is an edge from (a,b) to (b,a), whenever a,b are distinct atoms. That’s it.

Normalization of pp-formulas

Classicaly,  primitive positive formulas form the smallest fragment of first-order logic which is closed under conjunction and existential quantification. Pp-formulas can be turned in to a normal form \exists^\ast \bigwedge_i \phi_i – this is due to Skolemization, i.e. the fact that \bigwedge_i \exists x \phi_i can be turned into \exists x_1,\ldots,x_n \bigwedge \phi_i. In this case, Skolemization is a consequence of the axiom of finite choice.

We show that in the world with atoms,  not every orbit-finite pp-formula can be converted into an equivalent one in prenex form. This is another demonstration of the failure of the axiom of choice.

This raises the question: what is the appropriate notion of a pp-formula, which does have normal forms?

Continue reading