Star Exercises 2016

Mikołaj Bojańczyk

zajęcia / courses

Here are 5 difficult exercises. If an exercise is solved by $n$ people, then each solver gets $0.7/n$ points, which are added to the grade. Grades are rounded to the closest number from the set {2, 3, 3.5, 4, 4.5, 5}. For example, if in the oral exam you got a 4, and you were the only person to solve one exercise, then you get 4.7 points, which is rounded to 4.5. The deadline is January 20.

Deterministic Büchi. Is the following problem decidable?

• Input: a nondeterministic Büchi automaton.
• Question: is the recognised language definable by some deterministic Büchi automaton?

Games with partial information. Let $A,B,C,D$ be four alphabets, and let

$W \subseteq (A\times B \times C \times D)^\omega$

be an $\omega$ -regular language. Consider the following game, which is played in $\omega$ rounds numbered as $1,2,\ldots$ . In the $i$ -th round, player $0$ produces letters

$a_i \in A \qquad b_i \in B$

and player $1$ responds with letters

$c_i \in C \qquad d_i \in D$

There is, however a restriction on the information for player $1$ , namely that the letter $c_i$ can only depend on $a_1,\ldots,a_i$ , while the letter $d_i$ can only depend on $b_1,\ldots,b_i$ . Player $0$ has no such restriction, both $a_i$ and $b_i$ are allowed to depend on all of the information $c_1,d_1,\ldots,c_{i-1},d_{i-1}$ .

Is the following problem decidable?

• Input: alphabets $A,B,C,D$ and a Büchi automaton defining a subset $W \subseteq (A\times B \times C \times D)^\omega$ .
• Question: does player $1$ have a winning strategy in the game described above?

Distance automata with more counters. Consider the following extension of a distance automaton. Instead of having a set of costly transitions, we have two counters {1,2} and each transition is labelled by an instruction from the following toolkit:
• do nothing;
• increment counter 1;
• reset counter 1;
• reset counter 1 and increment counter 2;
• reset both counters.

The value of a run is the biggest value attained by any counter. Prove that limitedness is decidable for these automata, using the limitedness game.

Separation. Prove that the following problem is decidable:
• Input: Regular word languages $L,K \subseteq \Sigma^*$ , given say by deterministic automata.
• Question: Is there a language of star height 1 which contains $L$ but is disjoint with $K$ ? A language of star height 1 is a language which can be defined by a regular expression, without complement, where the Kleene star is allowed, but it cannot be nested.

As a hint, use the previous exercise.

Tree Angluin. Generalise the Angluin algorithm to deterministic bottom-up tree automata on trees over a finite ranked alphabet.