{"id":634,"date":"2015-10-17T13:39:29","date_gmt":"2015-10-17T11:39:29","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=634"},"modified":"2015-10-26T17:27:34","modified_gmt":"2015-10-26T16:27:34","slug":"3-weighted-automata","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/3-weighted-automata","title":{"rendered":"3. Weighted automata"},"content":{"rendered":"

In the following we write \"\field\" to denote any field, but of course the example of the real numbers is the most natural one. Fix the field \"\field\" for the rest of the lecture.<\/p>\n

A\u00a0weighted automaton<\/em>\u00a0consists of the following ingredients:
\n\u2022 an input alphabet, which is a set \"\Sigma\";
\n\u2022 a set \"Q\" of states, which is a vector space over \"\field\";
\n\u2022 an initial state \"q_0 \in Q\";
\n\u2022 for each letter \"a \in \Sigma\", a linear transition function<\/em> \"\delta_a : Q \to Q\";
\n\u2022 a linear output function<\/em> \"F : Q \to \field\".<\/p>\n

An automaton is called finite\u00a0<\/em>if the input alphabet has finitely many elements and the vector space has finite dimension.<\/p>\n

(One could consider a slightly more uniform and general definition, where the input alphabet is also a vector space, and the transition function is a linear map \"Q \times \Sigma \to Q\". The case of finite input alphabets would be recovered by viewing an input letter as one of the base vectors in the vector space \"\field^\Sigma\" of finite dimension.)<\/p>\n

The semantics if a weighted automaton is a function \"\Sigma^* \to \field\" defined as follows. When given an input word, the automaton<\/span>\u00a0begins in the initial state \"q_0\". Then for every new input letter \"a\", it applies the transition function \"\delta_a\" to the current state, yielding a new state. Finally, it applies the output function \"F\" to the state at the end, yielding an element of the underlying field.\u00a0<\/span><\/p>\n

Example.\u00a0<\/strong>A normal DFA with \"n\" states can be viewed as a special case of a weighted automaton. The set of stats will be \"\field^n\", and the reachable ones will only be vectors which have zero on all coordinates except the coordinate corresponding to the current state. \"\Box\"<\/p>\n

In this lecture, we make the following points:<\/p>\n

    \n
  1. Weighted automata admit minimisation;<\/a><\/li>\n
  2. For finite automata, some questions are decidable;<\/a><\/li>\n
  3. For finite automata, some questions are undecidable.<\/li>\n<\/ol>\n

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

    In the following we write to denote any field, but of course the example of the real numbers is the most natural one. Fix the field for the rest of the lecture. A\u00a0weighted automaton\u00a0consists of the following ingredients: \u2022 an input alphabet, which is a set ; \u2022 a set of states, which is a […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":535,"menu_order":3,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-634","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/634"}],"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=634"}],"version-history":[{"count":35,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/634\/revisions"}],"predecessor-version":[{"id":729,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/634\/revisions\/729"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/535"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=634"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}