Guest Column: Analytic Combinatorics and Descriptional Complexity of Regular Languages on Average

• Tipo: Artigo em Revista Científica Internacional
• Data: 2020

Autores

Broda, S (Autor) FCUP; António Machiavelo (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

A Revista está pendente de validação pelos Serviços Administrativos.

Título: SIGACT News

Vol. 51

Páginas: 38-56

ISSN: 0163-5700

Outras Informações

ID Authenticus: P-00V-B64

DOI: 10.1145/3388392.3388401

Abstract (EN): <jats:p>Average-case complexity results provide important information about computational models and methods, as worst-case scenarios usually occur for a negligible amount of cases. The framework of analytic combinatorics provides an elegant tool for that analysis, completely avoiding the use of statistical methods, by relating combinatorial objects to algebraic properties of complex analytic generating functions. We have previously used this framework to study the average size of di erent nondeterministic nite automata simulations of regular expressions. In some cases it was not feasible to obtain explicit expressions for the generating functions involved, and we had to resort to Puiseux expansions. This is particularly important when dealing with families of generating functions indexed by a parameter, e.g. the size of underlying alphabets, and when the corresponding generating functions are obtained by algebraic curves of degree higher than two. In this paper we expound our approach in a tutorial pace, providing sufficient details to make it available to the reader.</jats:p>

Idioma: Inglês

Tipo (Avaliação Docente): Científica