{"id":1475,"date":"2018-01-17T12:57:09","date_gmt":"2018-01-17T11:57:09","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1475"},"modified":"2018-06-29T11:26:55","modified_gmt":"2018-06-29T09:26:55","slug":"recognisable-languages-of-graphs","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/lipa\/lipa-summer-school-2018-june-25-29\/recognisable-languages-of-graphs","title":{"rendered":"Recognisable languages of graphs"},"content":{"rendered":"<p>This one of the courses at the\u00a0<a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/lipa\/lipa-summer-school-2018-june-25-29\">Lipa Summer School<\/a>.<\/p>\n<h4><a href=\"http:\/\/mimuw.edu.pl\/~bojan\">Miko\u0142aj Boja\u0144czyk<\/a><\/h4>\n<h4>Recognisable languages of graphs<\/h4>\n<p>Slides:<\/p>\n<ul>\n<li><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-graphs\/introduction.html\">introduction<\/a>,<\/li>\n<li>recognisability implies mso for bounded treewidth\u00a0<a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-graphs\/courcelle2.html\">part 1<\/a>,\u00a0<a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/slides\/lipa-graphs\/courcelle3.html\">part 2<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>A recognisable language of words is one that can be recognised by a monoid or a finite automaton.\u00a0Similar statements hold for trees, and various infinite extensions of words and trees. What about graphs? I will\u00a0discuss this\u00a0in my talk, which is based mainly on ideas\u00a0of Courcelle. There are at least two algebras for graphs (corresponding to graph parameters like treewidth or cliquewidth). I will also discuss the connections to monadic second-order logic, i.e. Courcelle&#8217;s conjecture.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This one of the courses at the\u00a0Lipa Summer School. Miko\u0142aj Boja\u0144czyk Recognisable languages of graphs Slides: introduction, recognisability implies mso for bounded treewidth\u00a0part 1,\u00a0part 2 &nbsp; A recognisable language of words is one that can be recognised by a monoid or a finite automaton.\u00a0Similar statements hold for trees, and various infinite extensions of words and [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1441,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1475","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1475"}],"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=1475"}],"version-history":[{"count":4,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1475\/revisions"}],"predecessor-version":[{"id":1538,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1475\/revisions\/1538"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1441"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1475"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}