{"id":1214,"date":"2016-12-28T16:48:20","date_gmt":"2016-12-28T15:48:20","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1214"},"modified":"2016-12-28T16:48:20","modified_gmt":"2016-12-28T15:48:20","slug":"star-exercises-2016","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20162017-2\/advanced-topics-in-automata-20162017-jezyki-automaty-i-obliczenia-2\/star-exercises-2016","title":{"rendered":"Star Exercises 2016"},"content":{"rendered":"

Here are 5 difficult exercises. If an exercise is solved by \"n\" people, then each solver gets \"0.7/n\" 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.<\/p>\n

\n

 <\/p>\n

Deterministic B\u00fcchi.\u00a0<\/strong>Is the following problem decidable?<\/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

\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

\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 two counters {1,2} and each transition is labelled by an instruction from the following toolkit:
\n\u2022 do nothing;
\n\u2022 increment counter 1;
\n\u2022 reset counter 1;
\n\u2022 reset counter 1 and increment counter 2;
\n\u2022 reset both counters.<\/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

\n

Separation<\/strong>. Prove that the following problem is decidable:
\n\u2022 Input<\/strong>: Regular word languages \"L,K \subseteq \Sigma^*\", given say by deterministic automata.
\n\u2022 Question<\/strong>: Is there a language of star height 1 which contains \"L\" but is disjoint with \"K\"? 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.<\/p>\n

As a hint, use the previous exercise.<\/p>\n

\n

Tree Angluin<\/strong>. \u00a0Generalise the Angluin algorithm to deterministic bottom-up tree automata on trees over a finite ranked alphabet.<\/p>\n","protected":false},"excerpt":{"rendered":"

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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1097,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1214","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1214"}],"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=1214"}],"version-history":[{"count":3,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1214\/revisions"}],"predecessor-version":[{"id":1269,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1214\/revisions\/1269"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1097"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1214"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}