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

• Type: Article in International Scientific Journal
• Date: 2020

Authors

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

Journal

The Journal is awaiting validation by the Administrative Services.

Title: SIGACT News

Vol. 51

Pages: 38-56

ISSN: 0163-5700

Other information

Authenticus ID: 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>

Language: English

Type (Professor's evaluation): Scientific