[Colloq] Reminder: Thesis Proposal - Tim Smith - The Complexity of Infinite Words as Determined by Languages of their Prefixes

[Tim Smith]

Thesis Proposal by Tim Smith

Thursday, December 5, 8:00 am

110 WVH


Title:

The Complexity of Infinite Words as Determined by Languages of their
Prefixes

Abstract:

We explore a notion of complexity for infinite words relating them to
languages of their prefixes.  An infinite language L determines an infinite
word α if every string in L is a prefix of α.  If L is regular or
context-free, it is known that α must be ultimately periodic; conversely,
every ultimately periodic word is determined by some regular language.  We
propose to investigate other classes of languages and infinite words to see
what connections can be made among them within this framework.

The language classes we propose to investigate are defined by various types
of automata, grammars, and parallel rewriting systems. We will make
particular use of pumping lemmas as a tool for studying these classes and
their relationship to infinite words. If time permits, we would like to
extend this framework to address prediction of infinite words.

Committee:

Rajmohan Rajaraman (advisor)
Arnold Rosenberg
Ravi Sundaram
 Javed Aslam
Juhani Karhumäki (external examiner, University of Turku)