# Documentation for the structure function calculator

$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 be abandoned midway;
• the run can start before we get to the run-state;
• runs that are of less than maximal length of their “flavor” (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.

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$$
encoded as
$$x=012032202311322023102$$
which 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
$$6561 = 3^8\le 4^m$$
Note
$$(4^2,4^3,4^4,4^5,4^6,4^7)= (16, 64, 256, 1024, 4096, 16384)$$
So $h^*(7)\le 14$.

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$.

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$.

What can we say about $h^*(6)$? $4^6=4096$ and
$(3^4,3^5,3^6,3^7,3^8)=(81, 243, 729, 2187, 6561)$. So
$$3^8\le 4^7\Longrightarrow h^*(7)\le 22-8=14$$
$$3^7=2187\le 4^6=4096\Longrightarrow h^*(6)\le 22-7=15$$
$$3^6= 729\le 4^5 = 1024\Longrightarrow h^*(5)\le 22-6=16$$
$$3^5= 243\le 4^4 = 256\Longrightarrow h^*(4)\le 22-5=17$$
$$3^4= 81 \le 4^4 = 256(\Longrightarrow h^*(4)\le 22-4=18)$$
$$3^3= 27\le 4^3 = 64\Longrightarrow h^*(3)\le 22-3=19$$
So 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.

Note
$$3^r\le 4^1\Longrightarrow r\le 1$$
$$2^r\le 4^1\Longrightarrow r\le 2$$
So a binary run of length 2 narrows it down to $4^1$.
And this corresponds to
$$q=n+1-r=21+1-2=20,$$
so $h^*(1)\le 20$.

Some examples of “inversion” (different explanation for the string depending on whether the subalphabet, or the size of the subalphabet, is taken into account):
21112
212220
020001
211120
1333030
32322131
201011311
1010113303
01210312303

# WordPress theme

While working on the UH Manoa Mathematics Department web site I am developing the following WordPress theme.

### Hawaiian Elegance

This is based on Arcsin’s WordPress theme “Cerulean Elegance” licensed under a GPL License. You are free to use it under the terms of that same license. Some of the layout by Loren Swendsen is taken from the College of Natural Sciences pages.

##### Features

HTML5 semantic web doctype and tags

[test]

# Front-end heavy web sites

Sometimes it is necessary or preferable for a web site to be almost front-end only, i.e., to have no backend scripts written in PHP/Perl/Python/whatever, only server side includes. While this is not the case for the UH Manoa Mathematics web site, at some point it was. A snapshot of the site at the time is available on Google App Engine:

Since there is little backend one can mostly understand the setup just using View Source in the browser. (Actually in this example the SSI backend has been replicated/simulated using PHP for Google App Engine.)

You may notice that a rudimentary “database” system is used, namely the databases are JSON (Javascript object notation) files that are accessed using Ajax. Another approach is to just put the data in a .js file which can be included using a <script> tag.

# Top Ten pages

#### (unique pageviews)

Part of my faculty service assignment is to maintain the site math.hawaii.edu. Here are the top ten most visited pages within it during 2011 (some pages did not exist or were not tracked during part of the year). 2012 results further down the page.

Position 2011 2012 2013
1 / / /
2 /home/ /online-grapher/ /wordpress/placement-exam/

Analysis: the home page / will always be number one. In 2011 due to a temporary issue the home page was for a while redirected to /home/, so that got the number 2 spot. Number 3 was the now archaic-sounding /home/Placement.shtml. In 2012 the number 2 spot went to /online-grapher/ followed by /people/ at number 3. For 2013, due to a redesign the Online Grapher was split between wordpress/online-grapher and online-grapher thereby losing the number to slot to /wordpress/placement-exam/.

In summary, 2011 was dominated by plain server-side include and .shtml URLs, 2012 by introduction of URL rewriting rules, and 2013 by WordPress delivering some of the most visited pages.

1. /

This is the homepage, so it is to be expected that it’s number one.

2. /home/

This was the address of the homepage for a while due to a temporary configuration. Ideally this should not be on the list.

3. /home/Placement.shtml

This was the address of the page /placement/ for a long time. The page features exam sign-up, practice exams, and detailed rules regarding an exam taken by many undergraduates on campus.

4. /home/directory.shtml

This was the address of the page /people/ for a long time. A natural use of the site is to go to /people/, then /people/specificperson/, and then click on the link to the specific person’s home page, /~whateveritis/.

5. /?online-grapher

Somehow our department has the #1 hit for the search term “online grapher” on Google. This page is now called /online-grapher/.

6. /home/?directory

Another name for the /people/ page that was in use for a while.

7. /online-grapher/
8. /home/?Placement

Another name for the /placement/ page that was in use for a while.

9. /home/Courses.shtml

A name for the page /courses/ that was in use for a long time.

10. /?page=online-grapher

A name for /online-grapher/ that was in use for a while.

For 2012 the list was (again by Unique Pageviews):

Page Pageviews Unique Pageviews Avg. Time on Page Entrances Bounce Rate % Exit Page Value
1.
/
89,070 64,187 00:02:07 60,555 42.11% 38.72% \$0.00 2. /online-grapher/ 23,377 18,139 00:02:10 18,003 78.44% 75.01% \$0.00
3.
/people/
24,617 15,476 00:00:29 2,647 22.33% 8.30% \$0.00 4. /placement/ 22,607 15,156 00:03:45 10,486 63.85% 55.53% \$0.00
5.
/fortran/3/
14,732 13,581 00:03:56 12,663 91.66% 85.45% \$0.00 6. /fortran/1/ 7,843 6,698 00:03:06 5,384 84.66% 69.83% \$0.00
7.
/courses/
11,011 6,268 00:00:46 609 37.11% 13.70% \$0.00 8. /computer-lab/ 6,256 5,422 00:01:59 4,622 83.64% 71.08% \$0.00
9.
/wordpress/placement-exam-coming-up/
7,846 5,413 00:01:15 1,361 39.82% 27.43% \$0.00 10. /undergraduate/ 6,634 4,713 00:00:26 233 52.36% 12.10% \$0.00