School Seminars and Colloquia

Cayley Graphs, Finite State Automata and Group Automata

Discrete Structures and Algorithms (Seminar)

by Dr Andrei Kelarev


Institution: School of Information Technology and Mathematical Sciences, University of Ballarat
Date: Tue 18th May 2010
Time: 2:15 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

Abstract: Cayley graphs are closely related to the concepts of finite state
automata and group automata. In particular, finite state automata
are generalisations of the Cayley graphs, since every Cayley graph
can be regarded as a finite state automaton. Group automata form
an important subclass of the class of all finite state automata. On the
other hand, Cayley graphs are capable of accomplishing all tasks
performed by the finite state automata. These relations lead to new
open questions concerning the influence of the theoretical
properties of the Cayley graphs on their possible applications in
directions where finite state automata have been used, including
such areas as bioinformatics, data mining, computer graphics, and
internet security.

A.V. Kelarev, C.E. Praeger,
On transitive Cayley graphs of groups and semigroups,
European J. Combinatorics 24(2003)(1), 59–72.

A. Kelarev, J. Ryan, J. Yearwood,
Cayley graphs as classifiers for data mining: The influence
of asymmetries, Discrete Mathematics 309(2009)(17),
5360–5369.

For More Information: contact: David Wood. email woodd@unimelb.edu.au