Mikołaj Bojańczyk

## Star Exercises 2016

Here are 5 difficult exercises. If an exercise is solved by people, then each solver gets 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 be four alphabets, and let

be an -regular language. Consider the following game, which is played in rounds numbered as . In the -th round, player produces letters

and player responds with letters

There is, however a restriction on the information for player , namely that the letter can only depend on , while the letter can only depend on . Player has no such restriction, both and are allowed to depend on all of the information .

Is the following problem decidable?

• Input: alphabets and a Büchi automaton defining a subset .
• Question: does player 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 , given say by deterministic automata.
Question: Is there a language of star height 1 which contains but is disjoint with ? 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.