{"id":1099,"date":"2016-09-30T16:25:04","date_gmt":"2016-09-30T14:25:04","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=1099"},"modified":"2017-01-29T05:46:53","modified_gmt":"2017-01-29T04:46:53","slug":"infinite-alphabets","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20162017-2\/infinite-alphabets","title":{"rendered":"Infinite alphabets"},"content":{"rendered":"<p>This is a lecture on automata (and later other devices) that operate on infinite alphabets. The lecture is on Wednesdays at 12:15 in room 4060. The exercises are on Mondays at 14:15 in room 5050. The lecture and exercises are shared by Miko\u0142aj Boja\u0144czyk and <a href=\"http:\/\/www.mimuw.edu.pl\/~sl\/\">S\u0142awomir Lasota<\/a>.<\/p>\n<p><a href=\"http:\/\/www.mimuw.edu.pl\/~bojan\/20162017-2\/infinite-alphabets\/lecture-notes\">Lecture notes<\/a><\/p>\n<p><a href=\"http:\/\/www.mimuw.edu.pl\/~bojan\/20162017-2\/infinite-alphabets\/homework\">Homework assignments<\/a><\/p>\n<p><a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/20162017-2\/infinite-alphabets\/exam\">Exam<\/a><\/p>\n<hr \/>\n<p>&nbsp;<\/p>\n<p>Here is an overview of the course<\/p>\n<p><strong>Data words and their automata<\/strong><\/p>\n<p>In the first half of the lecture, we discuss some concrete models, typically involving registers. The emptiness problem for\u00a0most powerful of the models, data automata, will as hard as the famous reachability problem for vector addition systems, and the lecture will contain a description of the latter.<\/p>\n<ol>\n<li>Introduction to automata with registers<\/li>\n<li>Alternating automata with registers<\/li>\n<li>Data automata<\/li>\n<li>Logic on data words<\/li>\n<li>Reachability for vector addition systems<\/li>\n<\/ol>\n<p><b>Sets with atoms<\/b><\/p>\n<p>In the second part of the lecture, we move to a more general setting, which describes some of the previous constructions in a cleaner mathematical model. This mathematical model will lead us to discover new questions.<\/p>\n<ol>\n<li>Sets with atoms and orbit-finiteness<\/li>\n<li>Automata in sets with atoms<\/li>\n<li>Atoms with structure other than equality<\/li>\n<li>Oligomorphism<\/li>\n<li>What is a computable function?<\/li>\n<li>Turing machines with atoms<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>This is a lecture on automata (and later other devices) that operate on infinite alphabets. The lecture is on Wednesdays at 12:15 in room 4060. The exercises are on Mondays at 14:15 in room 5050. The lecture and exercises are shared by Miko\u0142aj Boja\u0144czyk and S\u0142awomir Lasota. Lecture notes Homework assignments Exam &nbsp; Here is [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":1095,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-1099","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1099"}],"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=1099"}],"version-history":[{"count":6,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1099\/revisions"}],"predecessor-version":[{"id":1253,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1099\/revisions\/1253"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/1095"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=1099"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}