Automata, Representations, And Proofs
James Worthington · eCommons (Cornell University) · 2009
In this dissertation, we study automata, languages, and functions between automata which preserve the language accepted. We examine them from the perspectives of representation theory, category theory, and proof theory. A cen-tral theme is that these perspectives interact in many useful, interesting ways. Let M be a monoid in a monoidal category. We view automata as objects of a category of representations of M, equipped with a start state and an observa-tion function. If M is a monoid in Set, this view yields a generalization of the standard notion of a deterministic automaton. In this generalization, the inputs to an automaton are elements of an arbitrary monoid. Omitting the requirement that automata have start states yields categories with final objects. These final objects can be used to minimize deterministic automata. Let K be a commutative semiring. To express nondeterminism in our frame-