by Rogério Reis, UPorto-DCC & CMUP
On June 17th, at 2:00 PM in room FC6 029 of the DCC-FCUP, Rogério Reis will give a lecture entitled "Elegantly Obtaining Average Values for Complicated Objects."
The lecture is organized by the DCC-FCUP.
Abstract
For a large set of problems, it is more informative to have an average estimate than the same estimate for the worst case. However, the usual way to obtain average estimates is through the collection of experimental data, with the result always being an approximation, no matter how large the sample size used. In the field of formal languages, the size of the smallest model representing a language is a good measure of its complexity. The study of the effect of various operations on this measure of complexity has seen growing interest in recent decades, a testament to the importance of its applications, from formal program verification to pattern recognition to speech processing. But beyond studying this complexity in the worst case, it is important to obtain average results, which, although much more difficult, have much greater practical importance. In this introduction, in addition to presenting the fundamental concepts involved, it will be shown how the techniques of Analytical Combinatorics can contribute to solving some difficult problems in this area, without any recourse to experimentation.