There are several decision problems for certain computation models with atoms that are decidable when atoms admit certain well quasi order (WQO), and undecidable otherwise. We recall the problems and formulate few questions related to WQOs.

Continue reading

# Cohomology groups of the torus

Čech cohomology is a way of defining cohomology groups (a topological invariant with algebraic structure) on a topological space. We give a rough description of the construction, in a very special case of a torus, and relate it to the construction of the nonstandard alphabets. Continue reading

# Uniform bound on the size of support of a witness

Let be an equivariant relation. We show that under a certain assumption on , for every , if there exists a witness such that holds, then there also exists one with small support. We show an application to extending homomorphisms.

# Orbit finiteness vs. number of supported elements

A set is orbit finite if and only if the number of its elements supported by atoms grows polynomially with .

# Color-preserving automorphisms in Fraisse classes (new version)

Again, a question closely related to a characterization of *standard atoms* (not to be confused with standard alphabets:). The question is a refinement of a question posted in Automorphisms vs color-preserving automorphisms in Fraisse classes, which has been answered negatively (see the recent post The colored open question closed).

# The colored open question closed

A question in my recent post Automorphisms vs color-preserving automorphisms in Fraisse classes has been answered negatively by Mikołaj. The counterexample Fraisse class is the age of the structure , the rational numbers with the ternary ‘cyclic order’ relation defined by:

I am about to reformulate the question slightly, in order to make refutation harder;)

# A stronger Kleene theorem

This post continues the discussion on the Kleene theorem from here. The previous post gave a notion of regular expressions that had the same expressive power as nondeterministic automata. The idea was that a star corresponds to a graph where the set of vertices had one orbit, and where the edges where labelled by simpler regular expressions. In the case without atoms, such a graph is necessarily a self loop, which corresponds to the standard Kleene star. This post is about a stronger requirement: instead of saying that the graph has one orbit of vertices, we say that it has one orbit of edges.

# Automorphisms vs color-preserving automorphisms in Fraisse classes

Here is a question closely related to a characterization of *standard atoms* (not to be confused with standard alphabets:). It asks whether a bound on the number of automorphisms is equivalent to a bound on the numer of color-preserving automorphisms, in every Fraisse class of finite relational structures.

# 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 – this is due to Skolemization, i.e. the fact that can be turned into . 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?

# The Rum Conjecture is refuted

A conjecture I posted a while ago, concerning reachability of states in automata with atoms after a Brzozowski phase, has been refuted by Mikołaj Bojańczyk.