
eCommons@Cornell >
Cornell University Graduate School >
Cornell Theses and Dissertations >
Please use this identifier to cite or link to this item:
http://hdl.handle.net/1813/14061
Title:  Automata, Representations, And Proofs 
Authors:  Worthington, James 
Keywords:  Automata 
Issue Date:  14Oct2009 
Abstract:  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 central 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 observation 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 finalobjects. These final objects can be used to minimize deterministic automata. Let K be a commutative semiring. To express nondeterminism in our framework, we must first take an algebraic detour and show that the category of Ksemimodules and Klinear maps is a monoidal category. We then define Kalgebras as monoids in this category. We call the corresponding automata Klinear automata. These automata are related to, but distinct from, weighted automata. A Klinear automaton with input Kalgebra A defines an element of Lin(A, K). In certain cases, elements of Lin(A, K) correspond to Klinear extensions of formal power series. In the Klinear case, there is an addition defined on both the states and the inputs. Addition of states can be used to represent nondeterminism. Addi tion of inputs is needed to define comultiplication. Comultiplication defines a Kalgebra structure on Lin(A, K). That is, comultiplication of inputs corresponds to multiplication of "languages". If multiplication and comultiplication satisfy certain "compatibility conditions", the input elements form a structure known as a Kbialgebra. Part of this dissertation is the development of the numerous parallels between the theory of bialgebras and the theory of automata and formal languages. These parallels demonstrate that comultiplication is a "hidden parameter" in many standard constructions involving automata and formal languages. In certain cases, a category of Klinear automata is related to a category of (generalized) deterministic automata by an adjunction. We show that the standard subset construction used to determinize automata can be generalized as a forgetful functor; determinization is essentially forgetting the Ksemimodule structure on the states of a Klinear automaton. Using this adjunction, we can construct a sequence of Klinear automata and morphisms thereof which witnesses the fact that two Klinear automata define the same element of Lin(A, K). With appropriate restrictions, this witness can be efficiently verified. Furthermore, we can use this witnessing sequence as the basis for a proof system for the equational theory of Kleene algebra. We also show that such proofs can be generated by a P SP ACE transducer. Finally, we discuss alternating automata in relation to our framework, and provide a determinizing functor. 
URI:  http://hdl.handle.net/1813/14061 
Appears in Collections:  Cornell Theses and Dissertations

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.
