{"id":208,"date":"2015-04-23T12:22:37","date_gmt":"2015-04-23T10:22:37","guid":{"rendered":"http:\/\/duch.mimuw.edu.pl\/~bojan\/podpunkt\/?page_id=208"},"modified":"2017-10-31T12:55:52","modified_gmt":"2017-10-31T11:55:52","slug":"4-factorisation-trees","status":"publish","type":"page","link":"https:\/\/www.mimuw.edu.pl\/~bojan\/20142015-2\/alg\/4-factorisation-trees","title":{"rendered":"4. Factorisation trees"},"content":{"rendered":"

In this part, it will be technically more convenient to talk about semigroups. A semigroup is like a monoid, except that it does not need to have an identity element. In other words, a semigroup is a set \"S\" equipped with a product operation \"S^+ \to S\" which is associative.<\/p>\n

Let \"S\" be a semigroup. Define an \"S\"-factorisation tree to be a\u00a0tree where nodes\u00a0are labelled by elements of \"S\", subject to the following restrictions:
\na)\u00a0if a node has children with labels \"s_1,\ldots,s_n\", read from left to right, then its label is the product \"s_1 \cdots s_n\";
\nb) if a node has more than two children, all of these children have the same label, and this label is an idempotent.
\nNodes with more than two children are called\u00a0idempotent\u00a0<\/em>nodes. We also assume that every non-leaf node has at least two children, and therefore children that have exactly two children are called\u00a0binary rules.<\/em><\/p>\n

Define the <\/span>yield\u00a0<\/em>of a tree to be the sequence of leaf labels read from left to right (this is a word in \"S^+\"). \u00a0<\/span>Define the height of a tree to be the biggest number of edges on a root-to-leaf path. We are interested in creating \"S\"-factorisation trees of small height. Clearly every word of length \"n\" is the yield of some \"S\"-factorisation tree of height at most \"\log n\", which does not use idempotent nodes, and is constructed by recursively splitting the word in two parts. As the following example shows, using idempotent nodes can decrease the height of a tree to a constant, e.g. at most 6 for the morphism which counts \"a\"‘s modulo two.<\/span><\/p>\n

Example. <\/strong>Consider the semigroup\u00a0\"\{0,1\}\" with addition modulo 2.<\/p>\n