Back to search

West Virginia University

Stationary Automata

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
PhD
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematics

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Bidhan, Anaam Mutar

Subjects

dc:subject × 6

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
West Virginia University
Base URL
researchrepository.wvu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Bidhan, Anaam Mutar. Stationary Automata. Dissertation thesis, https://doi.org/10.33915/etd.3750