Least supports and non-interpretability

In this post, we give a proof that (\str Q,\le) does not interpret (without parameters) in the homogeneous poset P nor in the random graph R. The idea is to first show that every continuous action of \aut P  or \aut R on a set is faithful or trivial. We show this by using the fact that P and R have least supports. Since \aut P and \aut R have an automorphism of order two and \aut(\str Q,\le) does not, this proves that there is no nontrivial continuous action of \aut P nor \aut R on \str Q.

Continue reading

Automorphism groups of definable structures

We consider equality atoms \atoms, i.e., \atoms is a countable set with the equality relation. Recall that by definable set we mean a structure which can be defined (in a possibly nested fashion) from \atoms using finite unions, finite tuples, and set-builder expressions with first-order formulas ranging over \atoms, e.g. \set{(x,y):x,y\in\atoms, x\neq y}\cup\set{x:x\in\atoms, x\neq 5} is definable using the parameter 5. A definable relational structure is a relational structure (A,R_1,\ldots,R_n) where A and each relation R_i is a definable set. Up to isomorphism, definable structures are the same as structures which interpret in \atoms, using first-order interpretations (this correspondence preserves parameters), but sometimes using definable sets makes constructions easier.

The problem described in the previous post is to determine isomorphism between two definable structures. In this post, we describe this problem in terms of automorphism groups. This post is based on discussions with Manuel Bodirsky and Antoine Mottet.

Continue reading

Graph isomorphism

Fix an \omega-categorical structure \atoms. The simplest, and already interesting case is (\mathbb N,=), the pure countable set.

We consider the definable graph isomorphism problem for graphs which are definable (equivalently, interpret in) \atoms:

Problem: DefGraphIso

Input: Two definable graphs G,H

Output: Yes, if G and H are isomorphic, No otherwise.

Below we make some very basic observations concerning this problem.

Continue reading

System of equations over sets of integers

Consider system of equations of the form

    \[\begin{array}{c} X_1 = t_1 \\ \cdots \\ X_n = t_n \end{array}\]

where variables X_1, \dots, X_n are interpreted as sets of integers, and t_1, \dots, t_n are expressions built from variables X_1, \dots, X_n, constants sets \{-1\},\{0\},\{1\}, addition + (interpreted element-wise as A+B = \{ a + b \;|\; a \in A, b \in B)\}, union \cup,  and a restricted form of intersection. Namely, we allow expressions of the form t \cap K with t and expression and K a constant denoting a semilinear subset of \mathbb Z.

(The study of such systems of equations stems from the analysis of pushdown automata over timed atoms [1], where equations in the form above are used to represent the delays of the timestamps of stack symbols between the time of push and the time of the corresponding pop.)

A solution is an assignment of a subset of integers to each variable X_i. We are interested in the emptiness problem: is X_1 empty in the least solution of a given system of equations as above? For example, natural numbers are the least solution to X = \{0\} \cup (\{1\} + X) and even integers are the least solution to X = \{0\} \cup (\{2, -2\} + X). Finite sets of constants like \{2, -2\} can be succinctly expressed by small equations using their binary expansion.

Note that the use of intersection in t \cap K is severely restricted. If intersections of the form X \cap Y for two variables X, Y are allowed, then the emptiness problem is equivalent to the emptiness problem of conjunctive grammars, and the latter problem is undecidable  [2].

On the other hand, emptiness is in PTIME if no intersection is allowed: By interpreting the commutative + as the noncommutative language concatenation \cdot (which preserves emptiness in the absence of intersections), we reduce to a context-free grammar—whose emptiness problem is solvable in PTIME.

Not all decision problems need be computationally simple, even in the absence of intersections. The 0-membership problem, which asks whether 0 (i.e., a word with the same number of 1‘s and -1‘s in the noncommutative view) is in the least solution, is NP-complete. This is an interesting example where parsing is harder than emptiness—it is usually the other way around, e.g., for conjunctive grammars emptiness is undecidable, while parsing is decidable (even in PTIME [2]).

Emptiness for equations where only intersections t \cap K with K finite are allowed, is NP-complete too. This can be shown by a simple iterative algorithm computing coarser and coarser under-approximations of the least solution, using at each step an oracle for the 0-membership problem for intersection-less equations.

The general case of intersections t \cap K with K semilinear is open. The emptiness problem in this case is equivalent to the emptiness problem for the class of timed poshdown automata [1]. We conjecture that the problem decidable in this case, and that, moreover, the least solution is semilinear.


[1] L. Clemente and S. Lasota, “Timed Pushdown Automata”, LICS’15.

[2] A. Jez and A. Okhotin, “Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth,” Theory Comput. Syst., vol. 46, no. 1, pp. 27–58, 2010.

Can orbit-finite semigroups be straightened?

A straight set is an equivariant set which is equivariantly isomorphic to a disjiont union of sets of the form \atoms^{(n)}. A straight semigroup is an equivariant semigroup whose universe is a straight set. We raise the following:

Question 1: is every equivariant, orbit-finite semigroup an image of some orbit-finite, straight semigroup under an equivariant mapping?

We show some simple preliminary observations towards the above question.

Continue reading

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.