{"id":2005,"date":"2024-10-17T05:29:20","date_gmt":"2024-10-17T03:29:20","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=2005"},"modified":"2024-10-17T06:20:22","modified_gmt":"2024-10-17T04:20:22","slug":"automata-and-logic-beijing-2024","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/2024-2025\/automata-and-logic-beijing-2024","title":{"rendered":"Automata and Logic in Beijing 2024"},"content":{"rendered":"

This is a mini-course on automata and logic, given at Peking University and ISCAS<\/a>. Many thanks to Zhilin Wu<\/a> for organising this!<\/p>\n

Lecture 1. Introduction to logic and automata<\/a>
\nWe start with four examples of structures that have decidable\/undecidable theories, and we show that decidability of one of them \u2013 natural numbers with addition \u2013 can be obtained using automata techniques.<\/p>\n

Lecture 2. Monadic second-order logic<\/a>
\nIn this lecture, we introduce monadic second-order logic (MSO), which can quantify over sets of elements, and only elements. We show that over finite words, this logic has the same expressive power as automata.<\/p>\n

Lecture 3. Infinite words (no slides in 2024, but you can look here<\/a>)
\nIn this lecture, we move to infinite words, where positions are indexed by \u03c9. One of the appropriate automata models is nondeterministic B\u00fcchi automata; we show that these are closed under complementation.<\/p>\n

Lecture 4. Determinization of \u03c9-automata<\/a>
\nB\u00fcchi automata do not determinize, as we saw in the previous lecture. However, if we extend the acceptance condition \u2013 to what is called the parity condition \u2013 <\/em>then they do determinism, as we show in this lecture.<\/p>\n

Lecture 5. Games<\/a>
\nIn this lecture, we discuss games of infinite duration, which will be used in the final part of our mini-course, about tree automata. We show that these games can be quite strange in general, but the special case of parity games \u2013 which is what we will need \u2013 is well behaved and has memoryless winning strategies.<\/p>\n

Lecture 6. The Rabin Theorem<\/a>
\nWe finish our mini-course with the Rabin Theorem, which shows that MSO has the same expressive power as automata on infinite trees. In the proof, we use two kinds of automata \u2013 nondeterministic and alternating \u2013 and the key result is that they are equivalent. The equivalence uses all of the theory developed in the previous lectures.<\/p>\n

 <\/p>\n","protected":false},"excerpt":{"rendered":"

This is a mini-course on automata and logic, given at Peking University and ISCAS. Many thanks to Zhilin Wu for organising this! Lecture 1. Introduction to logic and automata We start with four examples of structures that have decidable\/undecidable theories, and we show that decidability of one of them \u2013 natural numbers with addition \u2013 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1991,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-2005","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2005"}],"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=2005"}],"version-history":[{"count":6,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2005\/revisions"}],"predecessor-version":[{"id":2011,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2005\/revisions\/2011"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1991"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=2005"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}