{"id":1499,"date":"2018-03-02T11:31:21","date_gmt":"2018-03-02T10:31:21","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1499"},"modified":"2023-02-14T17:29:27","modified_gmt":"2023-02-14T16:29:27","slug":"algebraic-language-theory","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20172018-2\/algebraic-language-theory","title":{"rendered":"Algebraic language theory (automaty a p\u00f3\u0142grupy)"},"content":{"rendered":"

This course is about an alternative approach to regular languages, where one uses monoids\u00a0(and more fancy algebraic structures) instead of automata.\u00a0 I use notes from this lecture<\/a>, but I hope to create a new version in pdf for this one (this has not materialised, I’m sorry).<\/p>\n

<\/p>\n

Lecture<\/strong>:\u00a0Fridays\u00a014:15-15:45 (room 4060)
\nExercises<\/strong>:\u00a0Fridays\u00a016:00-17:30 (room 4060)<\/p>\n

Exam
\n<\/strong><\/p>\n

The exam is oral. Here are the topic and some materials for them.<\/p>\n

    \n
  1. Monoids<\/a>\u00a0and Green’s relations\u00a0<\/a><\/li>\n
  2. Factorisation forests<\/a><\/li>\n
  3. First-order logic and LTL<\/a><\/li>\n
  4. Omega<\/a> and scattered words<\/a><\/li>\n
  5. Countable words<\/a><\/li>\n
  6. Monads<\/a><\/li>\n
  7. What is an algebra for graphs and Courcelle’s Theorem<\/a> (also sections 3 and 4\u00a0\u00a0here<\/a>)<\/li>\n
  8. Recognisability implies definability for bounded treewidth (these<\/a> and these<\/a> slides, also\u00a0this<\/a> paper if you reallly must)<\/li>\n<\/ol>\n

    Please email me to choose a time. \u00a0Choose any subset of the 8 topics in the list above, here is the exchange rate:
    \n\u2022\u00a03 topics: dostateczny
    \n\u2022 4 topics: dobry
    \n\u2022 6 topics: bardzo dobry<\/p>\n","protected":false},"excerpt":{"rendered":"

    This course is about an alternative approach to regular languages, where one uses monoids\u00a0(and more fancy algebraic structures) instead of automata.\u00a0 I use notes from this lecture, but I hope to create a new version in pdf for this one (this has not materialised, I’m sorry).<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1388,"menu_order":-1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1499","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1499"}],"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=1499"}],"version-history":[{"count":8,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1499\/revisions"}],"predecessor-version":[{"id":1877,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1499\/revisions\/1877"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1388"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1499"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}