{"id":2078,"date":"2026-03-17T17:59:02","date_gmt":"2026-03-17T16:59:02","guid":{"rendered":"https:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=2078"},"modified":"2026-06-15T16:34:48","modified_gmt":"2026-06-15T14:34:48","slug":"przeksztalcenia-automatowe-2026-transducers","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/2025-2026\/przeksztalcenia-automatowe-2026-transducers","title":{"rendered":"Przekszta\u0142cenia automatowe 2026 \u2022 Transducers"},"content":{"rendered":"<p>This is a course on transducers, whose previous edition is <a href=\"https:\/\/www.mimuw.edu.pl\/~bojan\/2023-2024\/przeksztalcenia-automatowe-transducers\">here<\/a>.<\/p>\n<p><strong>Grade.\u00a0<\/strong>Your grade is the weighted average 2\/3 * (grade from oral exam) \u00a0+ 1\/3 * (grade from homework). There will be 3 groups of homework problems.<\/p>\n<p><strong>Lecture notes.\u00a0<\/strong>Here are versions of the lecture notes:<\/p>\n<ul>\n<li><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/papers\/transducer-book\/transducer-book-2026-05-25.pdf\">version from May 25<\/a><\/li>\n<li><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/papers\/transducer-book\/may-18-26.pdf\">version from May 18<\/a><\/li>\n<li><a href=\"https:\/\/mimuw.edu.pl\/~bojan\/papers\/transducer-book\/march-17-26.pdf\">version from March 17<\/a><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<h2><strong>Exam<\/strong><\/h2>\n<p>There are 13 topics for the exam : 1 Mealy, 4 Rational, 6 Regular and 2 Polyregular. These are listed below, together with the section numbers in the notes.<\/p>\n<p><strong>Mealy machines<\/strong><\/p>\n<ol>\n<li>(A.1 and A.2) Definition of \u00a0Mealy machines and the Krohn-Rhodes theorem<\/li>\n<\/ol>\n<p><strong>Rational functions<\/strong><\/p>\n<ol>\n<li>(B.1) Definition of rational relations, and undecidability of their equivalence problem.<\/li>\n<li>(B.2) Rational functions, \u00a0their equivalence with bimachines, and the decomposition of rational functions into primes.<\/li>\n<li>(B.3) Equivalence is decidable for rational functions<\/li>\n<li>(B.4) Machine independent characterizations of Mealy machines, sequential functions, \u00a0subsequential functions and rational functions<\/li>\n<\/ol>\n<p><strong>Regular functions<\/strong><\/p>\n<ol>\n<li>(C.1) The prime regular functions and their continuity<\/li>\n<li>(C.2.1) Continuity of two-way transducers<\/li>\n<li>(C.2.2) Closure under composition for two-way transducers<\/li>\n<li>(C.2.3) Decomposition of two-way transducers into primes<\/li>\n<li>(C.3) SST&#8217;s and their equivalence two two-way transducers<\/li>\n<li>(C.4.3) Regular functions in terms of logic<\/li>\n<\/ol>\n<p><strong>Polyregular functions<\/strong><\/p>\n<ol>\n<li>(D.1) For-transducers and their equialence with prime polyregular functions<\/li>\n<li>(D.2) Pebble transducers and their equivalence to for-transducers<\/li>\n<\/ol>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This is a course on transducers, whose previous edition is here. Grade.\u00a0Your grade is the weighted average 2\/3 * (grade from oral exam) \u00a0+ 1\/3 * (grade from homework). There will be 3 groups of homework problems. Lecture notes.\u00a0Here are versions of the lecture notes: version from May 25 version from May 18 version from [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":2040,"menu_order":-1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-2078","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2078"}],"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=2078"}],"version-history":[{"count":7,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2078\/revisions"}],"predecessor-version":[{"id":2087,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2078\/revisions\/2087"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/2040"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=2078"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}