{"id":1790273,"date":"2013-04-18T08:52:57","date_gmt":"2013-04-18T18:52:57","guid":{"rendered":"https:\/\/math.hawaii.edu\/wordpress\/?p=1790273"},"modified":"2025-10-15T22:13:46","modified_gmt":"2025-10-16T08:13:46","slug":"nondeterministic-finite-state-complexity","status":"publish","type":"post","link":"https:\/\/math.hawaii.edu\/wordpress\/nondeterministic-finite-state-complexity\/","title":{"rendered":"Nondeterministic finite state complexity"},"content":{"rendered":"<p><a href=\"http:\/\/math.hawaii.edu\/home\/board\/kayleigh-hyde.jpg\" rel=\"lightbox\"><img loading=\"lazy\" decoding=\"async\" class=\"alignright\" src=\"http:\/\/math.hawaii.edu\/home\/board\/kayleigh-hyde.jpg\" alt=\"\" width=\"100\" height=\"133\" \/><\/a><br \/>\nGraduate student <a href=\"http:\/\/math.hawaii.edu\/people\/kkhyde\/\">Kayleigh Hyde<\/a> will present her Master&#8217;s project on Monday April 22, 10:30am, in Shidler College of Business Room E201.<\/p>\n<p>Let $M$ be a nondeterministic finite automaton, having $q$ states and no $\\epsilon$-transitions. If there is exactly one path through $M$ of length $n$ leading to an accept state, and $x$ is the string read along that path, then we say that $A_N(x)\\le q$ (the NFS complexity of $x$ is at most $q$).<\/p>\n\n\n\n<!-- S0111V0 -->\n\n\nS0111V0\n\n<!-- S0111V1 -->\n\n\nS0111V1\n\n<!-- S0111V0&#45;&gt;S0111V1 -->\n0\n\n<!-- S0111V1&#45;&gt;S0111V1 -->\n1\n\n<!-- S0101V0 -->\n\n\nS0101V0\n\n<!-- S0101V1 -->\n\n\nS0101V1\n\n<!-- S0101V0&#45;&gt;S0101V1 -->\n0\n\n<!-- S0101V1&#45;&gt;S0101V0 -->\n1\n\n<!-- S0001V0 -->\n\n\nS0001V0\n\n<!-- S0001V0&#45;&gt;S0001V0 -->\n0\n\n<!-- S0001V1 -->\n\n\nS0001V1\n\n<!-- S0001V0&#45;&gt;S0001V1 -->\n1\n\n<!-- S0000V0 -->\n\n\nS0000V0\n\n<!-- S0000V0&#45;&gt;S0000V0 -->\n0\n\n\n\n\n","protected":false},"excerpt":{"rendered":"<p>Graduate student Kayleigh Hyde will present her Master&#8217;s project on Monday April 22, 10:30am, in Shidler College of Business Room E201. Let $M$ be a nondeterministic finite automaton, having $q$ states and no $\\epsilon$-transitions. If there is exactly one path through $M$ of length $n$ leading to an accept state, and $x$ is the string &hellip; <a href=\"https:\/\/math.hawaii.edu\/wordpress\/nondeterministic-finite-state-complexity\/\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Nondeterministic finite state complexity<\/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":[72],"tags":[],"class_list":["post-1790273","post","type-post","status-publish","format-standard","hentry","category-graduate-news"],"_links":{"self":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/posts\/1790273","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/comments?post=1790273"}],"version-history":[{"count":14,"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/posts\/1790273\/revisions"}],"predecessor-version":[{"id":5713440,"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/posts\/1790273\/revisions\/5713440"}],"wp:attachment":[{"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/media?parent=1790273"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/categories?post=1790273"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/math.hawaii.edu\/wordpress\/wp-json\/wp\/v2\/tags?post=1790273"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}