Rogério Reis


Err and err and err again, but less and less and less.


Objectives

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.