home · mobile · calendar · bactac · 2006-2007 · 

BACTAC - Crumly

Definite Finite Automata Models and Computation
Daniel Crumly
Graduate Student

The finite automaton is often left behind when it comes to solving computational problems -- instead it is resigned to recognizing regular expressions. In the following, the finite automaton is reintroduced as a computational device and a few simple computations are performed, both using the output capabilities of the Moore and Mealy machines as well as the simple acceptance or lack thereof of the classical model.

To delve into more complex problems, two new models are introduced, each with an arbitrarily long, but bounded, work tape. These new models are shown to be equivalent to the classical model in computing power, but vastly superior in succinctness measures. The models are also shown to be intuitively useful in modeling and as reference models for useful programming constructs and design patterns.

This talk is based on the speaker's Masters thesis.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:24)