
{"id":64,"date":"2012-05-26T22:41:13","date_gmt":"2012-05-27T08:41:13","guid":{"rendered":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/?p=64"},"modified":"2025-10-13T20:17:38","modified_gmt":"2025-10-14T06:17:38","slug":"deterministic-automaton-complexity-of-strings","status":"publish","type":"post","link":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/deterministic-automaton-complexity-of-strings\/","title":{"rendered":"Deterministic automaton complexity of strings"},"content":{"rendered":"<p>The <i>deterministic automaton complexity<\/i> of a finite binary string \\(x=x_1\\ldots x_k\\) is defined to be the least number \\(A(x)\\) of states of a finite state automaton \\(M\\) such that \\(x\\) is the only string of length \\(k\\) in the language accepted by \\(M\\). It was introduced by Shallit and Wang (2001).<\/p>\n<p>In a Discrete Mathematics class in Spring 2009, students <a href=\"http:\/\/www.jaxelson.com\/blog\/\">Jason Axelson<\/a>, <a href=\"http:\/\/hsfl.hawaii.edu\/\">Chris Ho<\/a> and <a href=\"http:\/\/mhslibraryupdates.blogspot.com\/2010\/11\/congratulatons-mr-kondo.html\">Aaron Kondo<\/a> wrote a C program that calculated the complexity of all strings of length at most 7.<\/p>\n<p>Results:<br \/>\n\\[A()=1,\\quad A(0)=2,\\]<br \/>\n\\[A(x_1\\ldots x_k)\\le k \\quad\\text{ for } k\\ge 2,\\]<br \/>\n\\[A(x_1\\ldots x_k)\\le k-1 \\quad\\text{ for } k\\ge 5.\\]<br \/>\n\\[A(x)\\le 5 \\quad\\text{ for } k=7.\\]<\/p>\n<p>The string \\(011100\\) is the only string (starting with a 0) of length 6 or less with the property that its complexity is increased when read backwards:<br \/>\n\\[A(011100)=4\\ne 5=A(001110).\\]<\/p>\n<p><a href=\"http:\/\/math.hawaii.edu\/~bjoern\/Teaching\/string011100.png\"><img loading=\"lazy\" decoding=\"async\" class=\"size-medium wp-image-23\" title=\"string011100\" src=\"http:\/\/math.hawaii.edu\/~bjoern\/Teaching\/string011100.png\" alt=\"String 011100\" width=\"300\" height=\"225\" \/><\/a><\/p>\n<p>A table of complexities is available:<\/p>\n<h4>Table of constants \\(c\\) with given property \\(\\forall x\\in\\{0,\\dots,b-1\\}^n\\)<\/h4>\n<p>In the large-alphabet limit, Kayleigh graphs apply and we upper bound is \\(\\lfloor n\/2\\rfloor + 2\\).<br \/>\nThe example \\(x=01\\) shows the deterministic \\(A(x)\\) is not well defined unless<br \/>\nwe also specify \\(b\\).<br \/>\n<em>http:\/\/math.hawaii.edu\/~bjoern\/dfa-complexity-of-01-as-3-ary<\/em><\/p>\n<table class=\"data_table\" style=\"float: left; width: 20px;\">\n<tbody>\n<tr>\n<th>Length \\(n\\)<\/th>\n<th>\\(b=1\\), \\(A(x)\\le cn + 1\\)<\/th>\n<th>\\(b=2\\), \\(A(x)\\le cn\\)<\/th>\n<th>\\(b=3\\), \\(A(x)\\le cn\\)<\/th>\n<th>\\(b=4\\), \\(A(x)\\le cn\\)<\/th>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>0<\/td>\n<td>\\(\\infty\\)<\/td>\n<td>\\(\\infty\\)<\/td>\n<td>\\(\\infty\\)<\/td>\n<\/tr>\n<tr>\n<td>1<\/td>\n<td><b>0<\/b><\/td>\n<td>2<\/td>\n<td>2<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>2<\/td>\n<td>0<\/td>\n<td><b>1<\/b><\/td>\n<td>3\/2?<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>3<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td><b>1<\/b><\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>4<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<td>1<\/td>\n<td><b>1<\/b><\/td>\n<\/tr>\n<tr>\n<td>5<\/td>\n<td>0<\/td>\n<td>0.8<\/td>\n<td>1<\/td>\n<td><b>1<b> <\/b><\/b><\/td>\n<\/tr>\n<tr>\n<td>6<\/td>\n<td>0<\/td>\n<td>0.83<\/td>\n<td>in progress<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>7<\/td>\n<td>0<\/td>\n<td>0.714285<\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>8<\/td>\n<td>0<\/td>\n<td><b>0.75<\/b><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>9<\/td>\n<td>0<\/td>\n<td>0.777 or 0.666<\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<div class=\"clearer\"><\/div>\n<p>News (September 6, 2015): For binary strings of length at most 8, you may view witnessing automata using the format<br \/>\n<a href=\"http:\/\/math.hawaii.edu\/~bjoern\/dfa-complexity-of-011\"><br \/>\nhttp:\/\/math.hawaii.edu\/~bjoern\/dfa-complexity-of-011<br \/>\n<\/a><\/p>\n<p>Thus, the following table is now partially obsolete.<\/p>\n<div class=\"clearer\"><\/div>\n<details>\n<summary>Complete table for binary strings of length \\(\\leq 7\\) and partial table for length \\(8\\)<\/summary>\n<p>In the following table we only consider strings starting with 0, since strings starting with 1 have the same complexity as the string obtained by flipping each bit (e.g., \\(K(001)=K(110)\\)).<\/p>\n<p>In the following table, \\(\\delta_i = 0102\\) means that \\((\\delta(0,i),\\delta(1,i),\\delta(2,i),\\delta(3,i)) = (0,1,0,2)\\)<br \/>\nin a witnessing DFA with 4 states, found by the MATH 301 students&#8217; program.<br \/>\nCuriously, note that below there are no instances of permutation automata (where \\(\\delta_i\\) is a bijection) except for the empty string.<\/p>\n<p>\\(A^-(x)\\) denotes incomplete DFA complexity, i.e., there is no requirement that the transition functions be total.<br \/>\nWe have \\(A_N(x)\\le A^-(x)\\le A(x).\\)<\/p>\n<table class=\"data_table\" style=\"float: left; width: 20px;\">\n<tbody>\n<tr>\n<th>String \\(x\\)<\/th>\n<th>Complexity \\(A(x)\\)<\/th>\n<th>\\(\\delta_0\\)<\/th>\n<th>\\(\\delta_1\\)<\/th>\n<th>\\(A^-(x)\\)<\/th>\n<\/tr>\n<tr>\n<td><\/td>\n<td>1<\/td>\n<td>0<\/td>\n<td>0<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>0<\/td>\n<td>2<\/td>\n<td>00<\/td>\n<td>10<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>00<\/td>\n<td>2<\/td>\n<td>01<\/td>\n<td>11<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>01<\/td>\n<td>2<\/td>\n<td>00<\/td>\n<td>10<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>000<\/td>\n<td>2<\/td>\n<td>01<\/td>\n<td>11<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>001<\/td>\n<td>3<\/td>\n<td>110<\/td>\n<td>200<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>010<\/td>\n<td>3<\/td>\n<td>100<\/td>\n<td>210<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>011<\/td>\n<td>3<\/td>\n<td>111<\/td>\n<td>220<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>0000<\/td>\n<td>2<\/td>\n<td>01<\/td>\n<td>11<\/td>\n<td>1<\/td>\n<\/tr>\n<tr>\n<td>0001<\/td>\n<td>3<\/td>\n<td>022<\/td>\n<td>122<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>0010<\/td>\n<td>4<\/td>\n<td>1120<\/td>\n<td>2321<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>0011<\/td>\n<td>3<\/td>\n<td>202<\/td>\n<td>100<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>0100<\/td>\n<td>4<\/td>\n<td>1130<\/td>\n<td>2211<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>0101<\/td>\n<td>3<\/td>\n<td>122<\/td>\n<td>202<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>0110<\/td>\n<td>4<\/td>\n<td>1110<\/td>\n<td>2231<\/td>\n<td>3<\/td>\n<\/tr>\n<tr>\n<td>0111<\/td>\n<td>3<\/td>\n<td>122<\/td>\n<td>212 (avoids 0)<\/td>\n<td>2<\/td>\n<\/tr>\n<tr>\n<td>00000<\/td>\n<td>2<\/td>\n<td>01<\/td>\n<td>11<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00001<\/td>\n<td>3<\/td>\n<td>022<\/td>\n<td>122<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00010<\/td>\n<td>4<\/td>\n<td>1120<\/td>\n<td>2322<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00011<\/td>\n<td>4<\/td>\n<td>1122<\/td>\n<td>2320<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100<\/td>\n<td>4<\/td>\n<td>1102<\/td>\n<td>2331<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101<\/td>\n<td>4<\/td>\n<td>1132<\/td>\n<td>2301<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110<\/td>\n<td>4<\/td>\n<td>1101<\/td>\n<td>2332<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111<\/td>\n<td>4<\/td>\n<td>1131<\/td>\n<td>2302<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000<\/td>\n<td>4<\/td>\n<td>1302<\/td>\n<td>2131<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001<\/td>\n<td>4<\/td>\n<td>1223<\/td>\n<td>2320<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010<\/td>\n<td>3<\/td>\n<td>122<\/td>\n<td>202<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011<\/td>\n<td>4<\/td>\n<td>1221<\/td>\n<td>2320<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100<\/td>\n<td>4<\/td>\n<td>1001<\/td>\n<td>2303<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101<\/td>\n<td>4<\/td>\n<td>1322<\/td>\n<td>2120<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110<\/td>\n<td>4<\/td>\n<td>1220<\/td>\n<td>2321<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111<\/td>\n<td>3<\/td>\n<td>122<\/td>\n<td>212 (avoids 0)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000000<\/td>\n<td>2<\/td>\n<td>01<\/td>\n<td>11<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000001<\/td>\n<td>3<\/td>\n<td>022<\/td>\n<td>122<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000010<\/td>\n<td>4<\/td>\n<td>0313<\/td>\n<td>2333<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000011<\/td>\n<td>4<\/td>\n<td>0333<\/td>\n<td>2313<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000100<\/td>\n<td>5<\/td>\n<td>11240<\/td>\n<td>23221<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000101<\/td>\n<td>5<\/td>\n<td>11241<\/td>\n<td>23220<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000110<\/td>\n<td>5<\/td>\n<td>11220<\/td>\n<td>23241<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>000111<\/td>\n<td>4<\/td>\n<td>2033<\/td>\n<td>1002<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>001000<\/td>\n<td>5<\/td>\n<td>13240<\/td>\n<td>22211<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>001001<\/td>\n<td>4<\/td>\n<td>1321<\/td>\n<td>2220<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>001010<\/td>\n<td>4<\/td>\n<td>2313<\/td>\n<td>1233 (avoids 0)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>001011<\/td>\n<td>4<\/td>\n<td>2032<\/td>\n<td>1003<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>001100<\/td>\n<td>4<\/td>\n<td>1320<\/td>\n<td>2223<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>001101<\/td>\n<td>5<\/td>\n<td>13241<\/td>\n<td>22230<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>001110<\/td>\n<td>5<\/td>\n<td>13220<\/td>\n<td>22243<\/td>\n<td>4 (\\(A_N=3\\))<\/td>\n<\/tr>\n<tr>\n<td>001111<\/td>\n<td>4<\/td>\n<td>2313<\/td>\n<td>3133<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010000<\/td>\n<td>4<\/td>\n<td>2133<\/td>\n<td>3313<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010001<\/td>\n<td>5<\/td>\n<td>12243<\/td>\n<td>23220<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010010<\/td>\n<td>4<\/td>\n<td>1220<\/td>\n<td>2321<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010011<\/td>\n<td>5<\/td>\n<td>12231<\/td>\n<td>23240<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010100<\/td>\n<td>4<\/td>\n<td>2313<\/td>\n<td>1303<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010101<\/td>\n<td>3<\/td>\n<td>122<\/td>\n<td>202<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010110<\/td>\n<td>5<\/td>\n<td>12210<\/td>\n<td>23241<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>010111<\/td>\n<td>5<\/td>\n<td>12211<\/td>\n<td>23240<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011000<\/td>\n<td>5<\/td>\n<td>13240<\/td>\n<td>21221<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011001<\/td>\n<td>4<\/td>\n<td>2002<\/td>\n<td>1033<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011010<\/td>\n<td>5<\/td>\n<td>13220<\/td>\n<td>21241<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011011<\/td>\n<td>4<\/td>\n<td>1221<\/td>\n<td>2320<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011100<\/td>\n<td>4<\/td>\n<td>1220<\/td>\n<td>2323<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011101<\/td>\n<td>5<\/td>\n<td>12241<\/td>\n<td>23210<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011110<\/td>\n<td>4<\/td>\n<td>2313<\/td>\n<td>1323 (avoids 0)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>011111<\/td>\n<td>3<\/td>\n<td>122<\/td>\n<td>212<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000000<\/td>\n<td>2<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000001<\/td>\n<td>3<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000010<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000011<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000100<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000101<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000110<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0000111<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001000<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001001<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001010<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001011<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001100<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001101<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001110<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0001111<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010000<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010001<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010010<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010011<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010100<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010101<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010110<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0010111<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011000<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011001<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011010<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011011<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011100<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011101<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011110<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0011111<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100000<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100001<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100010<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100011<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100100<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100101<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100110<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0100111<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101000<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101001<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101010<\/td>\n<td>3<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101011<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101100<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101101<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101110<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0101111<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110000<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110001<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110010<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110011<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110100<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110101<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110110<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0110111<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111000<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111001<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111010<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111011<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111100<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111101<\/td>\n<td>5<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111110<\/td>\n<td>4<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>0111111<\/td>\n<td>3<\/td>\n<td><\/td>\n<td><\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<table class=\"data_table\" style=\"float: left; width: 120px;\">\n<tbody>\n<tr>\n<th>String<\/th>\n<th>Complexity<\/th>\n<th>Witness<\/th>\n<\/tr>\n<tr>\n<td>00000000<\/td>\n<td>2<\/td>\n<td>\\(0^*\\)<\/td>\n<\/tr>\n<tr>\n<td>00000001<\/td>\n<td>3<\/td>\n<td>\\(0^* 1\\)<\/td>\n<\/tr>\n<tr>\n<td>00000010<\/td>\n<td>4<\/td>\n<td>\\(0^* 10\\)<\/td>\n<\/tr>\n<tr>\n<td>00000011<\/td>\n<td>4<\/td>\n<td>\\(0^* 11\\)<\/td>\n<\/tr>\n<tr>\n<td>00000100<\/td>\n<td>5<\/td>\n<td>\\(0^* 100\\)<\/td>\n<\/tr>\n<tr>\n<td>00000101<\/td>\n<td>5<\/td>\n<td>\\(0^* 101\\)<\/td>\n<\/tr>\n<tr>\n<td>00000110<\/td>\n<td>5<\/td>\n<td>\\(0^* 110\\)<\/td>\n<\/tr>\n<tr>\n<td>00000111<\/td>\n<td>5<\/td>\n<td>\\(0^* 111\\)<\/td>\n<\/tr>\n<tr>\n<td>00001000<\/td>\n<td>6<\/td>\n<td>\\(0^* 1000\\)<\/td>\n<\/tr>\n<tr>\n<td>00001001<\/td>\n<td>6<\/td>\n<td>\\(0^* 1001\\)<\/td>\n<\/tr>\n<tr>\n<td>00001010<\/td>\n<td>6<\/td>\n<td>\\(0^* 1010\\)<\/td>\n<\/tr>\n<tr>\n<td>00001011<\/td>\n<td>6<\/td>\n<td>\\(0^* 1011\\)<\/td>\n<\/tr>\n<tr>\n<td>00001100<\/td>\n<td>6<\/td>\n<td>\\(0^* 1100\\)<\/td>\n<\/tr>\n<tr>\n<td>00001101<\/td>\n<td>6<\/td>\n<td>\\(0^* 1101\\)<\/td>\n<\/tr>\n<tr>\n<td>00001110<\/td>\n<td>6<\/td>\n<td>\\(0^* 1110\\)<\/td>\n<\/tr>\n<tr>\n<td>00001111<\/td>\n<td>5<\/td>\n<td>d0: (1, 2, 3, 3, 0), d1: (4, 0, 1, 2, 0) better than \\(0^* 1111\\)<\/td>\n<\/tr>\n<tr>\n<td>00010000<\/td>\n<td>6<\/td>\n<td>\\(0001 0^*\\)<\/td>\n<\/tr>\n<tr>\n<td>00010001<\/td>\n<td>\\(\\le\\)5<\/td>\n<td>\\((0001)^*\\)<\/td>\n<\/tr>\n<tr>\n<td>00010010<\/td>\n<td>\\(\\le\\)6<\/td>\n<td>\\(0(001)^* 0\\)<\/td>\n<\/tr>\n<tr>\n<td>00010011<\/td>\n<td>\\(\\le\\)6<\/td>\n<td>\\(0(001)^* 1\\)<\/td>\n<\/tr>\n<tr>\n<td>00010100<\/td>\n<td>\\(\\le\\)6<\/td>\n<td>\\( 00 (01010&#8230;)00\\)<\/td>\n<\/tr>\n<tr>\n<td>00010101<\/td>\n<td>\\(\\le\\)5<\/td>\n<td>\\( 00 (01)*\\)<\/td>\n<\/tr>\n<tr>\n<td>00010110<\/td>\n<td>5<\/td>\n<td><a href=\"Teaching\/string00010110.svg\">witness (K-H)<\/a><\/td>\n<\/tr>\n<tr>\n<td>00010111<\/td>\n<td>5<\/td>\n<td>no trash<\/td>\n<\/tr>\n<tr>\n<td>00011000<\/td>\n<td>\\(\\le\\)6<\/td>\n<td>\\( 00011,00011,&#8230;\\)<\/td>\n<\/tr>\n<tr>\n<td>00011001<\/td>\n<td>\\(\\le\\)6<\/td>\n<td>\\( 0 (0011,0011,&#8230;)\\)<\/td>\n<\/tr>\n<tr>\n<td>00011010<\/td>\n<td>6<\/td>\n<td><a href=\"Teaching\/string00011010.svg\">witness (K-H)<\/a><\/td>\n<\/tr>\n<tr>\n<td>00011011<\/td>\n<td>\\(\\le\\)6<\/td>\n<td>\\( 00(011)^*\\)<\/td>\n<\/tr>\n<tr>\n<td>00011100<\/td>\n<td>5<\/td>\n<td><a href=\"Teaching\/string00011100.svg\">witness (K-H)<\/a><\/td>\n<\/tr>\n<tr>\n<td>00011101<\/td>\n<td>6<\/td>\n<td><a href=\"Teaching\/string00011101.svg\">witness (K-H)<\/a><\/td>\n<\/tr>\n<tr>\n<td>00011110<\/td>\n<td>\\(\\le 6\\) (Christina M) (Jiehua H)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00011111<\/td>\n<td>\\(\\le 5\\) (Jiehua H)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100000<\/td>\n<td>\\(\\le 5\\) (Christina M) (Jiehua H)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100001<\/td>\n<td>\\(\\le 6\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100010<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100011<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100100<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100101<\/td>\n<td>\\(\\le 5\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100110<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00100111<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101000<\/td>\n<td>\\(\\le 6\\): \\(a \\rightarrow_0 b \\rightarrow_0 c \\rightarrow_1 b\\) and \\(c \\rightarrow_0 d \\rightarrow_0 e\\) plus one thrash (Frank S)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101001<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101010<\/td>\n<td>\\(4\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101011<\/td>\n<td>5\\(\\le 7\\)<\/td>\n<td>d0: (1, 2, 1, 0, 4), d1: (3, 0, 4, 0, 2)<\/td>\n<\/tr>\n<tr>\n<td>00101100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101110<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00101111<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110000<\/td>\n<td>\\(\\le 6\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110001<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110010<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110011<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110110<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00110111<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111000<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111001<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111010<\/td>\n<td>\\(\\le 6\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111011<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111100<\/td>\n<td>\\(\\le 6\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111101<\/td>\n<td>\\(\\le 6\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111110<\/td>\n<td>\\(\\le 5\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>00111111<\/td>\n<td>\\(4\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000000<\/td>\n<td>\\(4\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000001<\/td>\n<td>\\(\\le 5\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000010<\/td>\n<td>\\(\\le 6\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000011<\/td>\n<td>\\(\\le 6\\) (Christina M) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000110<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01000111<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001000<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001001<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001010<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001011<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001110<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01001111<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010000<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010001<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010010<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010011<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010100<\/td>\n<td>4 \\(\\le 4\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010101<\/td>\n<td>3 (\\(\\le 4\\) Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010110<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01010111<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011000<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011001<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011010<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011011<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011110<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01011111<\/td>\n<td>\\(5\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100000<\/td>\n<td>\\(5\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100001<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100010<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100011<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100110<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01100111<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101000<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101001<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101010<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101011<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101110<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01101111<\/td>\n<td>\\(\\le 6\\)<\/td>\n<td>4 consecutive<\/td>\n<\/tr>\n<tr>\n<td>01110000<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110001<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110010<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110011<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110100<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110101<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110110<\/td>\n<td>\\(\\le 7\\)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01110111<\/td>\n<td>\\(5\\) (Jue W)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111000<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111001<\/td>\n<td>\\(\\le 6\\)<\/td>\n<td>4 consecutive<\/td>\n<\/tr>\n<tr>\n<td>01111010<\/td>\n<td>\\(\\le 6\\) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111011<\/td>\n<td>\\(\\le 6\\) (Chelsea T) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111100<\/td>\n<td>\\(5\\) (Chelsea T) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111101<\/td>\n<td>\\(5\\) (Chelsea T) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111110<\/td>\n<td>\\(4\\) (Chelsea T) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<tr>\n<td>01111111<\/td>\n<td>\\(3\\) (Chelsea T) (Christina M)<\/td>\n<td><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<\/details>\n","protected":false},"excerpt":{"rendered":"<p>The deterministic automaton complexity of a finite binary string \\(x=x_1\\ldots x_k\\) is defined to be the least number \\(A(x)\\) of states of a finite state automaton \\(M\\) such that \\(x\\) is the only string of length \\(k\\) in the language accepted by \\(M\\). It was introduced by Shallit and Wang (2001). In a Discrete Mathematics &hellip; <a href=\"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/deterministic-automaton-complexity-of-strings\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Deterministic automaton complexity of strings<\/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":[8,5,4],"tags":[],"class_list":["post-64","post","type-post","status-publish","format-standard","hentry","category-computability","category-research","category-teaching"],"_links":{"self":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/64","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=64"}],"version-history":[{"count":12,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/64\/revisions"}],"predecessor-version":[{"id":9098774,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/posts\/64\/revisions\/9098774"}],"wp:attachment":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/media?parent=64"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/categories?post=64"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/bjoern\/wp-json\/wp\/v2\/tags?post=64"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}