PhD Open Lecture Problems

Mikołaj Bojańczyk

posts

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

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.

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.
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}.$
Show an example of infinite oligomorphic atoms where the property (*) from the previous problem is false.
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}}}$
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,<)$ ?
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.
Let $\color{red} \atoms$ be infinite oligomorphic atoms. Show that deterministic orbit-finite automata recognise strictly more languages than orbit-finite monoids.
Let $\color{red} \atoms$ be infinite oligomorphic atoms. Show that universality is undecidable for nondeterministic orbit-finite automata.
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?

posts