Automata and Applications (CC575)

2013-2014

Automata theory (AT) is one of the foundations of Computer Science and its applica- tions extend to several areas of computer science. Among other recent areas of application of on operations and conversions between equivalent language representations and their succinctness; descriptional complexity issues; and introduction to average case complexity. We also introduce weighted automata and transducers, and see how the standard finite automata algorithms are adapted.

The second part considers automata over infinite words and trees and briefly presents the main results about conversions and decidability problems, and its relation with logics.

The third part focuses on some recent applications of automata-theoretical approaches in four different areas. Since the seminal Büchi theorem relating finite automata with monadic second order logic, automata have been successfully applied in many different logical contexts and specially with modal and temporal logics. These logics are particularly adequate for automatic verification of reactive systems. Weighted automata approaches were successfully applied in speech recognition and image processing to deal with probabilistic reasoning. Tree automata and finite automata are theoretical bases for XML technologies such as schema, transformations and query languages. Due to their succinctness and decidability, finite automata have several applications to security protocols and cryptography.

Finally in the fourth part we introduce cellular automata which are a class of spatially and temporally discrete mathematical systems characterised by local interaction and synchronous dynamical evolution. In the 1990’s cellular automata were proposed for modelling cryptographic protocols and that will be the main application we will focus on.

The second part considers automata over infinite words and trees and briefly presents the main results about conversions and decidability problems, and its relation with logics.

The third part focuses on some recent applications of automata-theoretical approaches in four different areas. Since the seminal Büchi theorem relating finite automata with monadic second order logic, automata have been successfully applied in many different logical contexts and specially with modal and temporal logics. These logics are particularly adequate for automatic verification of reactive systems. Weighted automata approaches were successfully applied in speech recognition and image processing to deal with probabilistic reasoning. Tree automata and finite automata are theoretical bases for XML technologies such as schema, transformations and query languages. Due to their succinctness and decidability, finite automata have several applications to security protocols and cryptography.

Finally in the fourth part we introduce cellular automata which are a class of spatially and temporally discrete mathematical systems characterised by local interaction and synchronous dynamical evolution. In the 1990’s cellular automata were proposed for modelling cryptographic protocols and that will be the main application we will focus on.