{"id":719,"date":"2015-10-26T15:21:52","date_gmt":"2015-10-26T14:21:52","guid":{"rendered":"http:\/\/www.mimuw.edu.pl\/~bojan\/?page_id=719"},"modified":"2015-10-26T15:21:52","modified_gmt":"2015-10-26T14:21:52","slug":"syntactic-weighted-automata","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20152016-2\/jezyki-automaty-i-obliczenia-2\/3-weighted-automata\/syntactic-weighted-automata","title":{"rendered":"Syntactic weighted automata"},"content":{"rendered":"

In this part of the lecture, we prove a Myhill-Nerode style theorem for weighted automata, which says that for every weighted automaton, there is a canonical one that recognises the same language, and is minimal in a certain sense. One way of stating the minimality condition\u00a0is to use\u00a0homomorphisms of weighted automata, as defined below.<\/p>\n

 <\/p>\n

\n

 <\/p>\n

 <\/p>\n

Homomorphisms of weighted automata. <\/b>Suppose that we have two weighted automata \"\Aa\" and \"\Aa'\"\u00a0over the same input alphabet \"\Sigma\". A homomorphism\u00a0<\/em>from \"\Aa\" to \"\Aa'\" is defined to be a linear function \"h\" from the state space of \"\Aa\", call it \"Q\", to the state space of \"\Aa'\", call it \"Q'\", which is consistent with the structure of the two automata, in the following sense. The initial state of \"\Aa\" is mapped to the initial state of \"\Aa'\", and \u00a0the following diagrams commute for every \"a \in \Sigma\"<\/p>\n

  <\/span>   <\/span>\"\[\xymatrix{ Q \ar[dr]^{F} \ar[d]_h \\ Q' \ar[r]_{F'} & \field}<\/p>\n

where \"F,F'\" are the output functions of the respective automata, and \"\delta_a,\delta'_a\" are the transition functions.<\/p>\n

If there is such a homomorphism, then the functions computed by the two automata are the same, as can be shown by induction on the length of the input word. An\u00a0isomorphism\u00a0<\/em>is a homomorphism whose inverse is also a homomorphism. It is not difficult to show that if a homomorphism is a bijection, as a function on state spaces, then it is an isomorphism.<\/p>\n

\n

 <\/p>\n

We now state the minimisation theorem for weighted automata. Call an automaton\u00a0reachable\u00a0<\/em>if every state in its state space is a finite linear combination of reachable states, i.e. states that can be reached by reading input words.<\/p>\n

Theorem.\u00a0<\/strong>Let \"f : \Sigma^* \to \field\" be a function computed by a weighted automaton. There exists a weighted automaton, called the\u00a0syntactic automaton of \"f\", <\/em>which computes \"f\" and\u00a0such that every reachable weighted automaton computing \"f\" admits a homomorphism into the syntactic automaton.<\/p>\n

Proof. \u00a0<\/strong>The proof is essentially the same as for the classical Myhill-Nerode theorem.<\/p>\n

Define the continuation\u00a0<\/em>of a word \"w \in \Sigma^*\" to be the function <\/p>\n

  <\/span>   <\/span>\"\[v \mapsto f(wv),\]\"<\/p>\n

which we will denote by \"[w]\". \u00a0Before defining the syntactic automaton, we define a bigger automaton, called the continuation automaton. <\/em>States of the continuation automaton are\u00a0vectors in \"\Sigma^* \to \field\", which is a vector space, albeit of infinite dimension.\u00a0 The initial state is the continuation of the empty word. The output function maps a state to its value on the empty word. The transition function <\/p>\n

  <\/span>   <\/span>\"\[\delta_a : \field^{\Sigma^*} \to \field^{\Sigma^*}\]\"<\/p>\n

is simply a permutation of coordinates:<\/p>\n

  <\/span>   <\/span>\"\[\delta_a (q) (v) = q(av)\]\"<\/p>\n

It is easy to see that this function is linear, and that it maps a continuation \"[w]\" to the continuation \"[wa]\". Note how the choice of the function \"f\" only plays a role in the definition of the initial state of the automaton.<\/p>\n

Define the syntactic automaton\u00a0<\/em>to be the continuation automaton with the state space restricted to finite linear combinations of continuations. We need to show that this automaton is well-defined, i.e. the transition functions stay within the state space. This is because the transition functions are linear, and they map continuations to continuations.<\/p>\n

We now show that every reachable weighted automaton recognising \"f\" admits a homomorphism into the syntactic automaton. Let \"\Aa\" be be such a weighted automaton, and let \"Q\" be its states. We first show that there is a homomorphism into the continuation automaton, and then we show that the image of the homomorphism is actually the syntactic automaton. Define a function <\/p>\n

  <\/span>   <\/span>\"\[h : Q \to \field^{\Sigma^*}\]\"<\/p>\n

which maps a state \"q\" to the function that maps \"w\" to the value of the automaton \"\Aa\" after reading \"w\", assuming that the initial state was changed to \"q\". This is clearly a linear function, and it is not difficult to see that it is a homomorphism.<\/p>\n

It remains to show that the image of \"h\" is actually the syntactic automaton. Since any homomorphism maps reachable states\u00a0to\u00a0reachable states, it follows that the image of \"h\" is included in the states of the syntactic automaton (because of the assumption that \"\Aa\" was reachable). Finally, the homomorphism \"h\" has the property that if \"w\" is an input word, then the state of \"\Aa\" after reading \"w\" is mapped to the continuation \"[w]\", and therefore \"h\" is surjective. \"\Box\"<\/p>\n","protected":false},"excerpt":{"rendered":"

In this part of the lecture, we prove a Myhill-Nerode style theorem for weighted automata, which says that for every weighted automaton, there is a canonical one that recognises the same language, and is minimal in a certain sense. One way of stating the minimality condition\u00a0is to use\u00a0homomorphisms of weighted automata, as defined below.   […]<\/p>\n","protected":false},"author":1,"featured_media":0,"parent":634,"menu_order":0,"comment_status":"open","ping_status":"open","template":"","meta":{"_acf_changed":false,"inline_featured_image":false,"footnotes":""},"class_list":["post-719","page","type-page","status-publish","hentry"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/719"}],"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=719"}],"version-history":[{"count":6,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/719\/revisions"}],"predecessor-version":[{"id":726,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/719\/revisions\/726"}],"up":[{"embeddable":true,"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/pages\/634"}],"wp:attachment":[{"href":"https:\/\/www.mimuw.edu.pl\/~bojan\/wp-json\/wp\/v2\/media?parent=719"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}