![\"\epsilon\"](\"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-content\/ql-cache\/quicklatex.com-092c5053fced592accc10801fcb1e701_l3.png\" "\\"Rendered")
-transitions.<\/p>\nFor 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.<\/p>\n
In these exercises, all models are assumed to be with guessing (unless otherwise stated) and to have -transitions.<\/p>\n
Exercise 1 (deadline November 4). <\/strong>We say a transition relation has\u00a0stack discipline\u00a0<\/em>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.<\/p>\n Exercise 2 (deadline November 4).\u00a0<\/strong>Show that one-way alternating register automata are at least as powerful as two-way nondeterministic automata.<\/p>\n Exercises A, B, C\u00a0(deadline November 4)<\/strong>.\u00a0<\/strong>Show languages which witness the\u00a0A, 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\u00a0(deadline November 20).\u00a0<\/strong><\/strong>Show that every language recognised by a nondeterministic register automaton is also recognised by a data automaton.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" 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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1099,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1115","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1115"}],"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=1115"}],"version-history":[{"count":8,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1115\/revisions"}],"predecessor-version":[{"id":1135,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1115\/revisions\/1135"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1099"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1115"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"gwiazdkowe\"](\"http:\/\/www.mimuw.edu.pl\/~bojan\/upload\/gwiazdkowe1.svg\")
<\/a><\/p>\n