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.

Deadline: June 30


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).


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

        \[\atoms^{k_1} + \cdots + \atoms^{k_n}\]

    for some k_1,\ldots,k_n \in \set{0,1,\ldots}. Find an example of oligomorphic atoms \atoms and a language over input alphabet \atoms 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 L \subseteq \Sigma^* is  recognised by (hereditarily orbit-finite) deterministic Turing machine, then the same is true for

        \[\set{w : aw \in L \text{ for some } a \in \Sigma}.\]

  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 X of finite graphs? (a) There is an equivariant nondeterministic orbit-finite automaton with input alphabet \atoms which recognises the language

        \[{\color{red}\set{a_1 \cdots a_n : \text{$n \in \Nat$ and the subgraph of $\atoms$ induced by $\set{a_1,\ldots,a_n}$ belongs to $X$}}}\]

     (b) there is some {\color{red} n \in \Nat} such that property X can be defined by a formula of first-order logic which has shape

        \[\exists x_1 \exists x_2 \cdots \exists x_n \forall y \underbrace{\varphi(x_1,x_2,\ldots,x_n,y)}_{\substack{\text{quantifier-free using} \\ \text{only the edge relation}}}\]

  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 (X,<) ?
  6. Let  \color{red} \atoms be oligomorphic atoms. Show that for every \color{red} a \in \atoms there can only be finitely many atoms \color{red} b \in \atoms such that the \color{red} a-orbit of \color{red} b is finite.
  7. Let \color{red} \atoms be infinite oligomorphic atoms. Show that deterministic orbit-finite automata recognise strictly more languages than orbit-finite monoids.
  8. Let \color{red} \atoms 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 \color{red} \mathcal L is closed under orbit-finite union if for every orbit-finite set \color{red} I and finitely supported function \color{red} f : I \to \mathcal L, the class also contains the union

        \[\color{red}  \bigcup_{i \in I} f(i).\]

    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 \color{red} L \cdot K and Kleene star \color{red} L^*.  Do regular expressions define the same languages as  nondeterministic-orbit finite automata?


Leave a Reply

Your email address will not be published.