A Hitchhiker's Guide to descriptional complexity through analytic combinatorics

被引：15

作者：

Broda, Sabine ^{[1
]}

Machiavelo, Antonio ^{[1
]}

Moreira, Nelma ^{[1
]}

Reis, Rogerio ^{[1
]}

机构：

[1] Univ Porto, Fac Ciencias, CMUP, P-4169007 Oporto, Portugal

来源：

THEORETICAL COMPUTER SCIENCE | 2014年 / 528卷

关键词：

Descriptional complexity; Average-case complexity; Analytic combinatorics; Regular expressions; Finite automata; AVERAGE STATE COMPLEXITY; ENUMERATION; GENERATION; AUTOMATA; SIZE;

D O I：

10.1016/j.tcs.2014.02.013

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

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. (C) 2014 Elsevier B.V. All rights reserved.

引用

页码：85 / 100

页数：16

共 35 条

[1]

Aho A. V., 1974, The design and analysis of computer algorithms

[2] Enumeration and generation with a string automata representation [J].