Star exercises

Mikołaj Bojańczyk

zajęcia / courses

Square Büchi. Is the following problem decidable? (Deadline is closed.)

• Input: a nondeterministic Büchi automaton over alphabet $\set{0,1}$ .
• Question: does the automaton accept the word which has $1$ on exactly those positions that are squares?

Deterministic Büchi. Is the following problem decidable? (Deadline is closed.)

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

Boolean combinations of open languages. Is the following problem decidable? (Deadline is closed.)

• Input: a nondeterministic Büchi automaton.
• Question: is the recognised language a finite Boolean combination of open sets?

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?

Joker game. Solve this problem for Michał Skrzypczak. The problem is open.

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

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 undecidable:
• input: tree languages $L,K$ recognised by a deterministic bottom-up automaton;
• question: is there a deterministic tree-walking automaton that separates them, i.e. accepts all trees in $L$ and rejects all trees in $K$ .

As a hint, consider using:
• the trees with 0,1,2 ports in the proof that tree-walking automata do not determines
• undecidability of the problem: given two context-free languages, decide if there is a regular language which separates them.

Canonisation. (I don’t have a solution, so no guarantees that this can be done, and hence extra credit for a solution)

Find some total order on finite words (e.g. the lexicographic order), such that the following problem can be solved efficiently (e.g. linear or quadratic time in terms of $w$ ):

• input: a nondeterministic register transducer from words to words and a word $w$
• output: the least output on $w$ , according to the chosen order.

Double points: do this for trees.

Two-way versus alternation for register automata. Find a language of data words that is:
• recognised by some deterministic two-way register automaton;
• not recognised by an any alternating one-way register automaton without guessing.

An alternating automaton without guessing is one where the transitions can only load the registers with data values that were previously in the registers, or which are in the input letter.

Two-way versus alternation for register automata. Show that deterministic two-way register automata are contained in alternating one-way register automata with guessing.

zajęcia / courses

Star exercises

Star exercises

Leave a Reply