Acima: Home Anterior: Home
Automata theory (AT) is one of the foundations of Computer Science and its applications extend to several areas of computer science. Among other recent areas of application of the Automata Theory are computational linguistics, bioinformatics, specification and verification of reactive systems, structured and semi-structured databases, network security, etc. Intensively studied during mid XX's, in the last decade there has been a growing and confluent interest in its theoretical and practical research: the exploration of specific new models and applications has at the same time stimulated a variety of new theoretical studies and formalizations.
In this seminar we will consider regular languages and its extensions to infinite words and regular trees. It is important to note that many algorithms and results for these models reduce or extend similar ones for classical finite automata.
Although regular languages are one of the simplest computer science structures and with widespread uses, several aspects of its descriptional complexity are unknown or not well understood. For instance, the non injective and non complexity preserving conversions between equivalent combinatorial representations and the descriptional complexity of generic languages operations. On the other hand, the enumeration of languages based on their model representations are useful for random generation and average-case analysis.
The first part of the seminar reviews the basics of finite automata over finite words with emphasis in the existence of normal forms, enumeration and conversions between equivalent language representations and their succinctness.
The second part considers automata over infinite words and trees and briefly presents the main results about conversions and decidability problems.
The third part focus in some recent applications of automata-theoretical approaches. Since the seminar 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.