Recent Posts
- Principles of biological computation: from circadian clock to evolution
- The science and engineering of biological computation: from process to software to DNA-based neural networks
- Elements of biological computation & stochastic thermodynamics of life
- Rationality, the Bayesian mind and their limits
- Web of C-lief: conjectures vs. model assumptions vs. scientific beliefs
- Idealization vs abstraction for mathematical models of evolution
- Allegory of the replication crisis in algorithmic trading
- 668,215 views
Join 2,752 other subscribers
Contributing authors
-
Abel Molina
-
Alexandru Strimbu
-
Alexander Yartsev
-
Eric Bolo
-
David Robert Grimes
-
Forrest Barnum
-
Jill Gallaher
-
Julian Xue
-
Artem Kaznatcheev
-
Keven Poulin
-
Marcel Montrey
-
Matthew Wicker
-
Dan Nichol
-
Philip Gerlee
-
Piotr MigdaĆ
-
Robert Vander Velde
-
Rob Noble
-
Sergio Graziosi
-
Max Hartshorn
-
Thomas Shultz
-
Vincent Cannataro
-
Yunjun Yang
Minimizing finite state automata
September 18, 2013 by Artem Kaznatcheev 12 Comments
Computer science is a strange mix of engineering, science, and math. This is captured well by the historic roots of deterministic finite state automata (DFAs). The first ideas that can be recognized as a precursor to DFAs can be found with Gilberth & Gilberth (1921) introducing flow process charts into mechanical and industrial engineering. Independently, McCullock & Pitts (1943) used nerve-nets as a model of neural activity. This preceded Turing’s 1948 entry into brain science with B-type neural networks, and Rosenblatt’s perceptrons (1957). Unlike Turing and Rosenblatt, McCullock & Pitts model did not incorporate learning. However, the nerve nets went on to have a more profound effect on ratiocination because — as Kleene (1951) recognized — they became the modern form of DFAs. Although DFAs are now in less vogue than they were a few decades ago, they are an essential part of a standard computer science curriculum due to their centrality in computer science. Yesterday, I had the privilege of familiarizing students with the importance of DFAs by giving a lecture of Prakash Panangaden’s COMP 330 course. Since Prakash already introduced the students to the theory of DFAs, regular expressions, and languages, I was tasked with explaining the more practical task of DFA minimization.
Read more of this post
Filed under Commentary, Technical Tagged with cstheory, finite state automata