Objectives

This UCTF aims

This UCTF aims

- to present some recent research work in descriptional complexity of regular languages and to consider some open problems.

• to present some other automata models and see how the classical theory extends to them.

• to present recent applications of automata theory to other computer science areas, such as specification and verification of reactive systems, cryptography, XML processing, computational linguistics, etc.

Learning Outcomes

- To understand the several representations for regular languages and operations, and their relative descriptional and computational complexity.

• To understand the several types of automata (alternating, weighted, timed, Büchi, over trees,etc ) and how known algorithms for finite automata can be adapted.

• To understand the basic concepts of transducers and their applications.

• To understand the several connections between logics and automata, specially

• monadic, temporal and modal logics.

• To understand the diversity of applications of automata and the gain of having common algorithms to apply to very different areas.

• To understand the importance and elegance of cellular automata as models of computation for discrete systems.