A Hitchhiker's Guide to descriptional complexity through analytic combinatorics

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

Autores

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

Revista

Título: Theoretical Computer Science

Vol. 528

Páginas: 85-100

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 13 Citações

Scopus - 16 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

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

Idioma: Inglês

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

Nº de páginas: 16