{"id":1575,"date":"2019-05-31T17:58:52","date_gmt":"2019-05-31T15:58:52","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?p=1575"},"modified":"2019-06-28T15:31:55","modified_gmt":"2019-06-28T13:31:55","slug":"phd-open-lecture-problems","status":"publish","type":"post","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/posts\/phd-open-lecture-problems","title":{"rendered":"PhD Open Lecture Problems"},"content":{"rendered":"

You can get points by either finding mistakes in the atom book<\/a>\u00a0or by solving problems.<\/p>\n

Grades:<\/strong>3=2 points, 4=2.5 points, 5=3 points.<\/p>\n

Deadline: <\/strong>June 30<\/p>\n

Mistakes<\/h3>\n

Each mistake in the atom book (not counting solutions to exercises) gets you 0.1 points. Mark the mistakes\u00a0on this page<\/a> with your name, if it does not work\u00a0you can use this google docs<\/a>. \u00a0Mistakes also include typos, bad grammar, and unclear parts (explain why), generally speaking anything that requires improvement. You don’t need to start to read the book from the beginning. The lecture corresponds to Chapters 3,4,7 and 10, but you are encouraged to find mistakes in other parts (later chapters have a higher expected mistake rate, so it might be profitable to look at them).<\/p>\n

Problems<\/h3>\n

Each of the problems (see below) gets you\u00a01 point if it is solved by \u22653 people including you, 2 points otherwise.<\/p>\n

    \n
  1. Define a register automaton<\/em> to be an equivariant automaton where the state space is of the form\n

      <\/span>   <\/span>\"\[\atoms^{k_1} + \cdots + \atoms^{k_n}\]\"<\/p>\n

    for some \"k_1,\ldots,k_n \in \set{0,1,\ldots}.\" Find an example of oligomorphic atoms \"\atoms\" and a language over input alphabet \"\atoms\" which is recognised by a deterministic orbit-finite automaton, but is not recognised by any equivariant \u00a0<\/span>deterministic register automaton.<\/li>\n

  2. Show an example of infinite oligomorphic atoms which satisfy the following property\u00a0(*): \u00a0if a language \"L \subseteq \Sigma^*\" is \u00a0recognised by (hereditarily orbit-finite) deterministic Turing machine, then the same is true for\n

      <\/span>   <\/span>\"\[\set{w : aw \in L \text{ for some } a \in \Sigma}.\]\"<\/p>\n<\/li>\n

  3. Show an example of infinite oligomorphic atoms where the property (*) from the previous problem\u00a0is false.<\/li>\n
  4. Assume that the atoms are the random undirected graph. Are the following two conditions \u00a0equivalent for a class \"X\" of finite graphs? (a) There is an equivariant nondeterministic orbit-finite automaton with input alphabet \"\atoms\" which recognises the language <\/span>
    \n<\/p>\n

      <\/span>   <\/span>\"\[{\color{red}\set{a_1 \cdots a_n : \text{$n \in \Nat$ and the subgraph of $\atoms$ induced by $\set{a_1,\ldots,a_n}$ belongs to $X$}}}\]\"<\/p>\n

    <\/span> \u00a0(b) there is some \"{\color{red} n \in \Nat}\" <\/span>such that property \"X\" can be defined by a formula of first-order logic which has shape <\/p>\n

      <\/span>   <\/span>\"\[\exists x_1 \exists x_2 \cdots \exists x_n \forall y \underbrace{\varphi(x_1,x_2,\ldots,x_n,y)}_{\substack{\text{quantifier-free using} \\ \text{only the edge relation}}}\]\"<\/p>\n

    <\/span><\/li>\n

  5. Assume that the atoms are the universal tree, i.e. the limit of trees modelled as structures with a closest common ancestor function. Is there are set builder expression, without constants, which defines a dense total order \"(X,<)\" ?<\/li>\n
  6. Let \u00a0\"\color{red} \atoms\" be oligomorphic atoms. Show that for every \"\color{red} a \in \atoms\" there can only be finitely many atoms \"\color{red} b \in \atoms\" such that the \"\color{red} a\"-orbit of \"\color{red} b\" is finite.<\/span><\/li>\n
  7. Let \"\color{red} \atoms\" be infinite oligomorphic atoms. Show that deterministic orbit-finite automata recognise strictly more languages than orbit-finite monoids.<\/span><\/li>\n
  8. Let \"\color{red} \atoms\" be infinite oligomorphic atoms. Show that universality is undecidable for nondeterministic orbit-finite automata.<\/span><\/li>\n
  9. Consider the equality atoms. We say that a class of languages \"\color{red} \mathcal L\" is closed under orbit-finite union<\/em>\u00a0if for every orbit-finite set \"\color{red} I\" and finitely supported function \"\color{red} f : I \to \mathcal L\", the class also contains the union\n

      <\/span>   <\/span>\"\[\color{red} \bigcup_{i \in I} f(i).\]\"<\/p>\n

    Define the regular expressions<\/em>\u00a0to be the smallest class of languages (over orbit-finite alphabets) which: contains all \u00a0languages with finitely many words and \u00a0is closed under orbit-finite union, concatenation \"\color{red} L \cdot K\" and Kleene star \"\color{red} L^*\". \u00a0Do regular expressions define the same languages as \u00a0nondeterministic-orbit finite automata?<\/span><\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"

    You can get points by either finding mistakes in the atom book\u00a0or by solving problems. Grades:3=2 points, 4=2.5 points, 5=3 points. Deadline: June 30 Mistakes Each mistake in the atom book (not counting solutions to exercises) gets you 0.1 points. Mark the mistakes\u00a0on this page with your name, if it does not work\u00a0you can use […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-1575","post","type-post","status-publish","format-standard","hentry","category-posts"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts\/1575"}],"collection":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/types\/post"}],"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=1575"}],"version-history":[{"count":21,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts\/1575\/revisions"}],"predecessor-version":[{"id":1599,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/posts\/1575\/revisions\/1599"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1575"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/categories?post=1575"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/tags?post=1575"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}