{"id":1343,"date":"2017-05-15T10:30:53","date_gmt":"2017-05-15T08:30:53","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1343"},"modified":"2018-01-17T12:18:47","modified_gmt":"2018-01-17T11:18:47","slug":"1343-2","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/lipa\/lipa-summer-school\/1343-2","title":{"rendered":"What is a recognisable language?"},"content":{"rendered":"<p>This one of the courses at the\u00a0<a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/lipa-summer-school\">Lipa Summer School<\/a>.<\/p>\n<h4>Miko\u0142aj Boja\u0144czyk<\/h4>\n<h4><i>What is a recognisable language?<\/i><\/h4>\n<p>Videos:\u00a0<a href=\"https:\/\/www.youtube.com\/watch?v=338DbO4ndk4\">1<\/a>,\u00a0<a href=\"https:\/\/www.youtube.com\/watch?v=JAsHn3-Jb84\">2<\/a>,\u00a0<a href=\"https:\/\/www.youtube.com\/watch?v=auzujfwT4Jo\">3<\/a>,\u00a0<a href=\"https:\/\/www.youtube.com\/watch?v=4JA1pnK501E\">4<\/a><\/p>\n<p>This course is about the algebraic approach to regular languages, which uses algebras instead of automata. The emphasis is on the connection of recognisability and definability in monadic second-order logic MSO.<\/p>\n<p>Click the title links for slides.<\/p>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-school\/1%20polgrupy.html\">Part 1:\u00a0finite words<br \/>\n<\/a>Classical results from the algebraic approach to finite words, where the algebras are monoids. As one example\u00a0of the usefulness of monoids, I will present the Factorisation Forest Theorem of Imre Simon.<\/p>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-school\/2%20nieskonczonosc.html\">Part 2: infinite words<br \/>\n<\/a>Monoids for infinite words, such as countable labelled linear orders.<\/p>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-school\/3%20monady.html\">Part 3: monads<\/a><strong><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-school\/3%20monady.html\"><br \/>\n<\/a><\/strong>\u00a0A bit of abstract nonsense, trying to answer the question: what is an algebra in general? The answer is to use Eilenberg-Moore algebras over a suitably chosen monad.<\/p>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-school\/4.%20grafy.html\">Part 4: graphs<\/a><strong><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-school\/4.%20grafy.html\"><br \/>\n<\/a><\/strong>Graphs. I will give half of the proof of the following result: for a class of graphs of bounded treewidth, being recognisable is equivalent to being definable in monadic second-order logic.<\/p>\n<p>&nbsp;<\/p>\n<div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>This one of the courses at the\u00a0Lipa Summer School. Miko\u0142aj Boja\u0144czyk What is a recognisable language? Videos:\u00a01,\u00a02,\u00a03,\u00a04 This course is about the algebraic approach to regular languages, which uses algebras instead of automata. The emphasis is on the connection of recognisability and definability in monadic second-order logic MSO. Click the title links for slides. Part [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1283,"menu_order":2,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1343","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1343"}],"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=1343"}],"version-history":[{"count":8,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1343\/revisions"}],"predecessor-version":[{"id":1455,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1343\/revisions\/1455"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1283"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1343"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}