Mikołaj Bojańczyk

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.