Mikołaj Bojańczyk

## PhD Open Lecture Problems

May 31, 2019

You can get points by either finding mistakes in the atom book or by solving problems.

Grades:3=2 points, 4=2.5 points, 5=3 points.

### Mistakes

Each mistake in the atom book (not counting solutions to exercises) gets you 0.1 points. Mark the mistakes on this page with your name, if it does not work you can use this google docs.  Mistakes also include typos, bad grammar, and unclear parts (explain why), generally speaking anything that requires improvement. You don’t need to start to read the book from the beginning. The lecture corresponds to Chapters 3,4,7 and 10, but you are encouraged to find mistakes in other parts (later chapters have a higher expected mistake rate, so it might be profitable to look at them).

### Problems

Each of the problems (see below) gets you 1 point if it is solved by ≥3 people including you, 2 points otherwise.

1. Define a register automaton to be an equivariant automaton where the state space is of the form for some Find an example of oligomorphic atoms and a language over input alphabet which is recognised by a deterministic orbit-finite automaton, but is not recognised by any equivariant  deterministic register automaton.

2. Show an example of infinite oligomorphic atoms which satisfy the following property (*):  if a language is  recognised by (hereditarily orbit-finite) deterministic Turing machine, then the same is true for 3. Show an example of infinite oligomorphic atoms where the property (*) from the previous problem is false.
4. Assume that the atoms are the random undirected graph. Are the following two conditions  equivalent for a class of finite graphs? (a) There is an equivariant nondeterministic orbit-finite automaton with input alphabet which recognises the language (b) there is some such that property can be defined by a formula of first-order logic which has shape 5. Assume that the atoms are the universal tree, i.e. the limit of trees modelled as structures with a closest common ancestor function. Is there are set builder expression, without constants, which defines a dense total order ?
6. Let be oligomorphic atoms. Show that for every there can only be finitely many atoms such that the -orbit of is finite.
7. Let be infinite oligomorphic atoms. Show that deterministic orbit-finite automata recognise strictly more languages than orbit-finite monoids.
8. Let be infinite oligomorphic atoms. Show that universality is undecidable for nondeterministic orbit-finite automata.
9. Consider the equality atoms. We say that a class of languages is closed under orbit-finite union if for every orbit-finite set and finitely supported function , the class also contains the union Define the regular expressions to be the smallest class of languages (over orbit-finite alphabets) which: contains all  languages with finitely many words and  is closed under orbit-finite union, concatenation and Kleene star .  Do regular expressions define the same languages as  nondeterministic-orbit finite automata?