{"id":686,"date":"2015-10-23T17:39:23","date_gmt":"2015-10-23T15:39:23","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=686"},"modified":"2016-01-19T10:32:14","modified_gmt":"2016-01-19T09:32:14","slug":"star-exercises","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/star-exercises","title":{"rendered":"Star exercises"},"content":{"rendered":"

Square B\u00fcchi.\u00a0<\/strong>Is the following problem decidable? (Deadline is closed.)<\/p>\n

\u2022 Input:<\/strong>\u00a0a nondeterministic B\u00fcchi automaton over alphabet \"\set{0,1}\".
\n\u2022 Question:\u00a0<\/strong>\u00a0does the automaton accept the word which has \"1\" on exactly those positions that are squares?<\/p>\n

 <\/p>\n

\n

 <\/p>\n

Deterministic B\u00fcchi.\u00a0<\/strong>Is the following problem decidable?\u00a0(Deadline is closed.)<\/p>\n

\u2022\u00a0Input:\u00a0<\/strong>a nondeterministic B\u00fcchi automaton.
\n\u2022\u00a0Question:\u00a0<\/strong>is the recognised language\u00a0definable by some\u00a0deterministic\u00a0<\/em>B\u00fcchi automaton?<\/p>\n

 <\/p>\n

\n

 <\/p>\n

Boolean combinations of open languages.\u00a0<\/strong>Is the following problem decidable?\u00a0(Deadline is closed.)<\/p>\n

\u2022\u00a0Input:\u00a0<\/strong>a nondeterministic B\u00fcchi automaton.
\n\u2022\u00a0Question:\u00a0<\/strong>is\u00a0the recognised language\u00a0a finite Boolean combination of open sets?<\/p>\n

 <\/p>\n

\n

 <\/p>\n

Games with partial information.<\/strong>\u00a0\u00a0Let \"A,B,C,D\" be four alphabets, and let <\/p>\n

  <\/span>   <\/span>\"\[W \subseteq (A\times B \times C \times D)^\omega\]\"<\/p>\n

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 <\/p>\n

  <\/span>   <\/span>\"\[a_i \in A \qquad b_i \in B\]\"<\/p>\n

and player \"1\" responds with letters <\/p>\n

  <\/span>   <\/span>\"\[c_i \in C \qquad d_i \in D\]\"<\/p>\n

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}\".<\/p>\n

Is the following problem decidable?<\/p>\n

\u2022\u00a0Input:\u00a0<\/strong>alphabets \"A,B,C,D\" and a B\u00fcchi automaton defining a subset\u00a0\"W \subseteq (A\times B \times C \times D)^\omega\".
\n\u2022\u00a0Question:\u00a0<\/b>does player \"1\" have a winning strategy in the game described above?<\/p>\n

 <\/p>\n

 <\/p>\n

\n

 <\/p>\n

Joker game.\u00a0<\/strong>Solve this problem<\/a>\u00a0for Micha\u0142 Skrzypczak<\/a>. The problem is open.<\/span><\/p>\n

 <\/p>\n

\n

 <\/p>\n

 <\/p>\n

Distance automata with more counters<\/strong>. Consider the following extension of a distance automaton<\/a>. Instead of having a set of costly transitions, we have a set of counters \"\set{1,\ldots,n}\", and\u00a0each transition is labelled by an instruction from the following toolkit:
\n\u2022 do nothing;
\n\u2022 increment counter \"i\" and simultaneously\u00a0reset counters \"1,\ldots,i-1\";
\n\u2022 reset counters \"1,\ldots,i\".<\/p>\n

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.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

 <\/p>\n

Separation<\/strong>. Prove that the following problem is undecidable:
\n\u2022 input: tree languages \"L,K\" recognised by a deterministic bottom-up automaton;
\n\u2022 question: is there a deterministic tree-walking automaton that separates them, i.e. accepts all trees in \"L\" and rejects all trees in \"K\".<\/p>\n

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

 <\/p>\n

\n

 <\/p>\n

 <\/p>\n

Canonisation<\/strong>. (I don’t have a solution, so no guarantees that this can be done, and hence extra credit for a solution)<\/span><\/p>\n

Find some total order on finite words \u00a0(e.g. the lexicographic order), such that the following problem can be solved efficiently (e.g. linear or quadratic time in terms of \"w\"):<\/p>\n

\u2022 input: a nondeterministic register transducer from words to words and a word \"w\"
\n\u2022 output: the least output on \"w\", according to the chosen order.<\/p>\n

Double points: do this for trees.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

 <\/p>\n

Two-way versus alternation for register automata<\/strong>. Find a language of data words that is:
\n\u2022 recognised by some deterministic two-way register automaton;
\n\u2022 not recognised by an any alternating one-way register automaton without guessing.<\/p>\n

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.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

 <\/p>\n

Two-way versus alternation for register automata<\/strong>. Show that deterministic two-way register automata are contained in alternating one-way register automata with guessing.<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

Square B\u00fcchi.\u00a0Is the following problem decidable? (Deadline is closed.) \u2022 Input:\u00a0a nondeterministic B\u00fcchi automaton over alphabet . \u2022 Question:\u00a0\u00a0does the automaton accept the word which has on exactly those positions that are squares?     Deterministic B\u00fcchi.\u00a0Is the following problem decidable?\u00a0(Deadline is closed.) \u2022\u00a0Input:\u00a0a nondeterministic B\u00fcchi automaton. \u2022\u00a0Question:\u00a0is the recognised language\u00a0definable by some\u00a0deterministic\u00a0B\u00fcchi automaton?   […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":535,"menu_order":100,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-686","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/686"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/comments?post=686"}],"version-history":[{"count":9,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/686\/revisions"}],"predecessor-version":[{"id":962,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/686\/revisions\/962"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/535"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=686"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}