Semester

Fall

Date of Graduation

2018

Document Type

Dissertation

Degree Type

PhD

College

Eberly College of Arts and Sciences

Department

Mathematics

Committee Chair

Jerzy Wojciechowski

Committee Co-Chair

John Goldwasser

Committee Member

John Goldwasser

Committee Member

Rong Luo

Committee Member

Elaine Eschen

Committee Member

C.Q.Zhang

Abstract

In this dissertation, we investigate new automata, we call it stationary automata or ST-automata. This concept is based on the definition of TF-automaton by Wojciechowski [Woj2]. What is new in our approach is that we incorporate stationary subsets of limit ordinals of uncountable cofinality. The first objective of the thesis is to motivate the new construction of automata. This concept of ST-automata allows us to make a connection with infinite graph theory. Aharoni, Nash-Williams, and Shelah [AhNaSh] formulated a condition that is necessary and sufficient for a bipartite graph to have a matching. For a bipartite graph G=( M,W,E ) , we define a language over the alphabet { M,W } . We construct an ST-automaton such that for each bipartite graph G, the automaton accepts an element of if and only if G has no matching. The theorem of Aharoni, Nash-Williams, and Shelah [AhNaSh] is used to prove that has the above property. The second objective is to compare the new ST-automata to TF-automata defined by Wojciechowski [Woj2]. First, adding an extra condition, we define special ST-automata and prove that they are equivalent to TF-automata. Then we show that in general ST-automata are stronger. We give an example of a language accepted by an ST-automaton that is not accepted by any special ST-automaton. In chapter four, we define operations on ST-automata over a fixed alphabet I as union, intersection, concatenation, raising to the powers, ω , *, and #. We show that applying those operations to languages defined by ST-automata the obtained languages are also definable using ST-automata.

Download

Included in

Mathematics Commons

Share

COinS