[Colloq] Colloq: The Complexity of Infinite Words as Determined by Languages of their Prefixes

[Francoise Niang]

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) 


 ----- 

Thesis Proposal by Tim Smith 

Thursday, December 5, 8:00 am 
Location to be determined 

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 
Jay Aslam 
Juhani Karhumäki (external examiner, University of Turku)