2nd Annual SURE Symposium 2019

SURE: Summer Undergraduate Research Experience

will feature two projects mentored by Prof. Kjos-Hanssen:

VC-dimensions of nondeterministic finite automata for words of equal length

*Davin Takahashi and Ethan Lamb*

Ishigami and Tani studied VC-dimensions of finite automata. We show that their results apply to a new notion, lower VC-dimension, where all sets (instead of some set) of a given cardinality must be shattered. We also relate the VC-dimension to the Separating Words problem.

Savings from word powers in automatic complexity

*Sun Young Kim and Clyde Felix*

The automatic complexity of a word was introduced by Shallit and Wang in 2001 and studied further by Kjos-Hanssen since 2013. In this work we develop an implementation of a lower bound on the complexity involving occurrences of powers of words, such as the occurrence of “humu” twice in “humuhumunukunukuapua’a”.

Lei Liu completed her Master’s degree with the project title *Complexity of Options* in 2017.

An extension to monotone options (pictured) was presented at

ALH-2018. The new paper is called **The number of languages with maximum state complexity** and has been accepted for TAMC 2019.

Some of the 168 monotone Boolean functions of 4 variables

Kaui Yogi completed his Master project in Spring 2018. With Achilles Beros we have a new paper on *Planar digraphs for automatic complexity* based in part on Yogi’s project work and accepted at TAMC 2019.

Spring 2017 saw the last MATH 373 class ever, as we transitioned to MATH 372 combining MATH 371 (probability) and 373 (statistics).

Final cohort MATH 373 students Tiffany Eulalio and Jake Koki’s term paper on apartment rental prices in Honolulu has been accepted for publication in undergraduate journal Manoa Horizons volume II.

2014 M.A. graduate Malihe Alikhani completed her Master’s project on *American option pricing and optimal stopping for success runs*. She participated in the Cornell Summer School in Probability 2014.

Her project constitutes one of the parts of the new paper *Pricing Complexity Options*, which appeared in

Algorithmic Finance, 2015.

Entry at IOS Press

The best version of the paper is at arxiv.org

The ideas are implemented in the Complexity Option Game!

Kayleigh Hyde presented our joint paper on nondeterministic automatic complexity at

COCOON 2014.

In 2015, the paper appeared in Electronic Journal of Combinatorics.

The ideas are implemented in the Complexity Guessing Game!

The Department of Mathematics at University of Hawaii at Manoa has long had an informal graduate program in logic, lattice theory, and universal algebra going back to Alfred Tarski’s student William Hanf.

Starting in 2016, things are getting a little more formal.

We intend the following course rotation (repeating after two years):

Semester |
Course number |
Course title |

Fall 2015 |
MATH 649B |
Graduate Seminar |

Spring 2016 |
MATH 649* |
Applied Model Theory |

Fall 2016 |
MATH 654* |
Graduate Introduction to Logic |

Spring 2017 |
MATH 657 |
Computability and Complexity |

*Actual course numbers may vary.

#### Faculty who may teach in the program

David A. Ross, Professor

Bjørn Kjos-Hanssen, Professor

Mushfeq Khan, Temporary Assistant Professor 2014-2017

Achilles Beros, Temporary Assistant Professor 2015-2017

Paul Kim Long Vu Nguyen defended his dissertation (final version, July 3, 2014) on May 23, 2014.

The commencement ceremony was held in the Stan Sheriff Center on May 17.

Left to right: Vice Chancellor Dasenbrock, 3 Board of Regents members, faculty marshall, Paul Nguyen, Bjørn Kjos-Hanssen.

## Professor of Mathematics, University of Hawaii at Manoa