skip to main content
Department of Computer Science University of Colorado Boulder
cu: home | engineering | mycuinfo | about | cu a-z | search cu | contact cu cs: about | calendar | directory | catalog | schedules | mobile | contact cs
home · events · bactac · 2006-2007 · 

BACTAC - Crumly

ECOT 831

Definite Finite Automata Models and Computation
Daniel L. 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.

BACTAC, the Beverage And Chips Tuesday Afternoon Colloquium, is a weekly forum run by graduate students. The goal is provide an informal setting in which anyone can (basically) present anything. In the past, we have had practice talks for conferences and job interviews, research reports, juggle lessons (!), student representative reports, internship discussions, an introduction to ergonomics, and "pay attention to this when you are going to look for job" discussions.

BACTAC is meant to be an informal and social event to promote the interaction among graduate students. BACTAC is typically held every Tuesday, at 3:30pm, in room ECOT 831. Free munchies and drinks are provided.

Please email Caleb Phillips for more information or if you want to be a speaker.

See also:
Department of Computer Science
College of Engineering and Applied Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
Send email to

Engineering Center Office Tower
ECOT 717
FAX +1-303-492-2844
XHTML 1.0/CSS2 ©2012 Regents of the University of Colorado
Privacy · Legal · Trademarks
May 5, 2012 (13:44)