[Colloq] PhD Thesis Defense - Tim Smith - Infinite Words as Determined by Languages of their Prefixes - April 13, 10am - 366 WVH

[Fong, Andy]

PhD Thesis Defense

Tim Smith
Monday, April 13, 10:00 am
366 WVH

Title:

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, it is known that α must be ultimately periodic; conversely, every ultimately periodic word is determined by some regular language. In this dissertation, we investigate other classes of languages and infinite words to see what connections can be made among them within this framework. We make particular use of pumping lemmas as a tool for studying these classes and their relationship to infinite words.

First, we investigate infinite words determined by various types of automata. We consider finite automata, pushdown automata, a generalization of pushdown automata called stack automata, and multihead finite automata, and relate these classes to ultimately periodic words and to a class of infinite words which we call multilinear.

Second, we investigate infinite words determined by the parallel rewriting systems known as L systems. We show that certain infinite L systems necessarily have infinite subsets in other L systems, and use these relationships to categorize the infinite words determined by a hierarchy of these systems, showing that it collapses to just three distinct classes of infinite words.

Third, we investigate infinite words determined by indexed grammars, a generalization of context-free grammars in which nonterminals are augmented with stacks which can be pushed, popped, and copied to other nonterminals at the derivation proceeds. We prove a new pumping lemma for the languages generated by these grammars and use it to show that they determine exactly the class of morphic words.

Fourth, we extend our investigation of infinite words from determination to prediction. We formulate the notion of a prediction language which masters, or learns in the limit, some set of infinite words. Using this notion we explore the predictive capabilities of several types of automata, relating them to periodic and multilinear words. We also consider the number of guesses required to master infinite words of particular description sizes.

Committee:

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

Andrew W. Fong
Assistant Director for Graduate Admissions and Enrollment

Northeastern University
College of Computer and Information Science
360 Huntington Avenue
451 West Village H
Boston, MA 02115
617-373-8493
a.fong at neu.edu