
{"id":9095515,"date":"2015-06-12T19:56:15","date_gmt":"2015-06-13T05:56:15","guid":{"rendered":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/?p=9095515"},"modified":"2016-03-03T15:49:18","modified_gmt":"2016-03-04T01:49:18","slug":"documentation-for-the-structure-function-calculator","status":"publish","type":"post","link":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/documentation-for-the-structure-function-calculator\/","title":{"rendered":"Documentation for the structure function calculator"},"content":{"rendered":"<p>\t$h^*_x(m)=q$ means that in order to have at most $\\text{(alphabet size)}^{m}$ accepting paths of length $n=|x|$, we need $q$ states.<\/p>\n<h4>Rules<\/h4>\n<ul>\n<li>\n\t\tWe are considering single-run complexity where the automaton must proceed to a fresh state except<br \/>\n\t\tthat there is one state that may be repeated.\n\t<\/li>\n<li>\n\t\tThus: the automaton need not be deterministic; a run may be abandoned midway;\n\t<\/li>\n<li>\n\t\tthe run can start before we get to the run-state;\n\t<\/li>\n<li>runs that are of less than maximal length of their &#8220;flavor&#8221; (such as 322023 which is shorter than 20322023 in the given example) do count (they are in any case insignificant for statistical model selection purposes); runs of less than maximal length for their size-of-flavor (such as 2311322 for size 3) do count; in general any subrun of a run counts.\n<\/ul>\n<p>The provided example comes from a series of codons in part of a messenger RNA (mRNA) molecule whose genetic code is $$AUG\\, ACG\\, GAG\\, CUU\\, CGG\\, AGC\\, UAG$$<br \/>\nencoded as<br \/>\n$$x=012032202311322023102$$<br \/>\nwhich has length $n=21$ and is a string from the alphabet $\\{0,1,2,3\\}$ which has size $b=4$. There is a run of length $r=8$ from the subalphabet $j=\\{0,2,3\\}$, namely an occurrence of 20322023. The corresponding automaton has $q=n+1-r=21+1-8=14$ many states and accepts $|j|^r=3^8$ many strings of length $n$. When $3^8\\le b^m$ we can then assert that $h^*(m)\\le q$. Thus<br \/>\n$$<br \/>\n6561 = 3^8\\le 4^m<br \/>\n$$<br \/>\nNote<br \/>\n$$<br \/>\n(4^2,4^3,4^4,4^5,4^6,4^7)= (16, 64, 256, 1024, 4096, 16384)<br \/>\n$$<br \/>\nSo $h^*(7)\\le 14$.<\/p>\n<p>The longest unary ($|j|=1$) run is of length $r=2$. This gives $q=n+1-r=20$ and only one string is accepted so $h^*(m)\\le 20$ for all $m$.<\/p>\n<p>The longest binary ($|j|=2$) run is of length $r=4$. This gives $q=n+1-r=18$ and when $2^4\\le 4^m$ (i.e., $2\\le m$), we can assert $h^*(m)\\le q$. So $h^*(2)\\le 18$.<\/p>\n<p>What can we say about $h^*(6)$? $4^6=4096$ and<br \/>\n$(3^4,3^5,3^6,3^7,3^8)=(81, 243, 729, 2187, 6561)$. So<br \/>\n$$3^8\\le 4^7\\Longrightarrow h^*(7)\\le 22-8=14$$<br \/>\n$$3^7=2187\\le 4^6=4096\\Longrightarrow h^*(6)\\le 22-7=15$$<br \/>\n$$3^6= 729\\le 4^5 = 1024\\Longrightarrow h^*(5)\\le 22-6=16$$<br \/>\n$$3^5= 243\\le 4^4 = 256\\Longrightarrow h^*(4)\\le 22-5=17$$<br \/>\n$$3^4= 81 \\le 4^4 = 256(\\Longrightarrow h^*(4)\\le 22-4=18)$$<br \/>\n$$3^3= 27\\le  4^3 = 64\\Longrightarrow h^*(3)\\le 22-3=19$$<br \/>\nSo we cannot obtain $h^*(3)\\le 18$ by a partial ternary run, but we can obtain it because $h^*(2)\\le 18$ because of the binary run.<\/p>\n<p>Note<br \/>\n$$3^r\\le 4^1\\Longrightarrow r\\le 1$$<br \/>\n$$2^r\\le 4^1\\Longrightarrow r\\le 2$$<br \/>\nSo a binary run of length 2 narrows it down to $4^1$.<br \/>\nAnd this corresponds to<br \/>\n$$q=n+1-r=21+1-2=20,$$<br \/>\nso $h^*(1)\\le 20$.<\/p>\n<p>Some examples of &#8220;inversion&#8221; (different explanation for the string depending on whether the subalphabet, or the size of the subalphabet, is taken into account):<br \/>\n21112<br \/>\n212220<br \/>\n020001<br \/>\n211120<br \/>\n1333030<br \/>\n32322131<br \/>\n201011311<br \/>\n1010113303<br \/>\n01210312303<\/p>\n","protected":false},"excerpt":{"rendered":"<p>$h^*_x(m)=q$ means that in order to have at most $\\text{(alphabet size)}^{m}$ accepting paths of length $n=|x|$, we need $q$ states. Rules We are considering single-run complexity where the automaton must proceed to a fresh state except that there is one state that may be repeated. Thus: the automaton need not be deterministic; a run may &hellip; <a href=\"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/documentation-for-the-structure-function-calculator\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Documentation for the structure function calculator<\/span> <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5,7],"tags":[],"class_list":["post-9095515","post","type-post","status-publish","format-standard","hentry","category-research","category-web-designdevelopment"],"_links":{"self":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/9095515","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/comments?post=9095515"}],"version-history":[{"count":6,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/9095515\/revisions"}],"predecessor-version":[{"id":9095789,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/9095515\/revisions\/9095789"}],"wp:attachment":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/media?parent=9095515"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/categories?post=9095515"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/tags?post=9095515"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}