A Hitchhiker's Guide to descriptional complexity through analytic combinatorics

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

Authors

Sabine Broda (Author) FCUP; Antonio Machiavelo (Author) FCUP; Nelma Moreira (Author) FCUP; Rogerio Reis (Author) FCUP

Journal

Title: Theoretical Computer Science

Vol. 528

Pages: 85-100

ISSN: 0304-3975

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 15 Citations

Scopus - 19 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-009-750

DOI: 10.1016/j.tcs.2014.02.013

Abstract (EN): Nowadays, increasing attention is being given to the study of the descriptional complexity in the average case. Although the underlying theory for such a study seems intimidating, one can obtain interesting results in this area without too much effort. In this gentle introduction we take the reader on a journey through the basic analytical tools of that theory, giving some illustrative examples using regular expressions. Additionally, new asymptotic average-case results for several epsilon-NFA constructions are presented, in a unified framework. It turns out that, asymptotically, and in the average case, the complexity gap between the several constructions is significantly larger than in the worst case. Furthermore, one of the epsilon-NFA constructions approaches the corresponding epsilon-free NFA construction, asymptotically and on average.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 16