Universidade do Minho  

Mapa do Site
Average-case Complexity of Regular Languages

Resumo: The worst-case complexity of the conversions between different representations of regular languages is well studied. However, for practical purposes, the average-case complexity of such conversions is much more relevant than its worst-case complexity, which is often due to some particular and rarely occurring cases. Still, the average-case analysis is, in general, a difficult task. One approach is to consider uniform random generators and to perform statistically significant experiments. Another approach is the use of asymptotic methods. In this presentation, we discuss asymptotic average-case results on the size of non-deterministic finite automata obtained from regular expressions, using the symbolic method and the framework of analytic combinatorics. This is a joint work with Sabine Broda, António Machiavelo and Rogério Reis.
  © 2024 Universidade do Minho  - Termos Legais  - actualizado por CMAT Símbolo de Acessibilidade na Web D.