For each exercise, there is 1 point which will be distributed across the solvers. Points are added to the grade starting with 2, e.g. 1 point gives 3 (which means that the course has been passed) and 3 points give the maximal grade 5.

In these exercises, all models are assumed to be with guessing (unless otherwise stated) and to have -transitions.

Exercise 1 (deadline November 4). We say a transition relation has stack discipline if the registers can be numbered so that each transition which modifies a register also simultaneously erases all strictly larger registers. Show that, over inputs where all data values are distinct, a two-way nondeterministic register with stack discipline can only check a regular property of the labels.

Exercise 2 (deadline November 4). Show that one-way alternating register automata are at least as powerful as two-way nondeterministic automata.

Exercises A, B, C (deadline November 4). Show languages which witness the A, B and C in the picture below. One can use unproved conjectures from complexity theory, e.g. P=NP (with both equality and inequality being legitimate conjectures).

Exercise 3 (deadline November 20). Show that every language recognised by a nondeterministic register automaton is also recognised by a data automaton.